The 2021 ICPC Asia Shenyang Regional Contest

---

---

B - Bitwise Exclusive-OR Sequence

题意

\(n\)个数，\(m\)个关系，每个关系形如 \(a_u⊕a_v=w\)，表示第\(u\)个数与第\(v\)数的异或运算结果为\(w\)。求是否有这样的\(n\)个数满足所有关系要求，如果没有输出\(-1\)，如果有输出所有满足要求的方案中，所有数字的和的最小值。

思路

建图，处理每个连通块，选取源点赋值为\(0\)(因为要求最小)，途中出现矛盾直接输出\(-1\)，否则从低位到高位统计每一位上\(0\)和\(1\)的出现次数，最后相加计算最小值。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int mxn = 1e6 + 5;int n, m, idx;
int to[mxn], nxt[mxn], head[mxn], edge[mxn], point[mxn], pre[mxn], sz[mxn];void add(int u, int v, int w)
{to[++idx] = v;edge[idx] = w;nxt[idx] = head[u];head[u] = idx;
}void init()
{fill(point, point + n, -1);fill(sz, sz + n, 1);iota(pre, pre + n, 0);
}int find(int x)
{return (x == pre[x] ? x : pre[x] = find(pre[x]));
}void join(int u, int v)
{int fu = find(u);int fv = find(v);if (fu != fv){pre[fu] = fv;sz[fv] += sz[fu];}
}void solve()
{cin >> n >> m;init();if (!m){cout << 0 << endl;return;}for (int i = 0; i < m; i++){int u, v, w;cin >> u >> v >> w;u--, v--;add(u, v, w);add(v, u, w);join(u, v);}int ans = 0;for (int i = 0; i < n; i++){if (find(i) != i){continue;}vector<int> cnt(30);queue<int> q;q.push(i);point[i] = 0;while (q.size()){int u = q.front();q.pop();for (int j = head[u]; j; j = nxt[j]){int v = to[j];if (point[v] == -1){point[v] = (point[u] ^ edge[j]);q.push(v);for (int k = 0; k < 30; k++){cnt[k] += ((point[v] >> k) & 1); // 统计1的个数}}else{if ((point[u] ^ point[v]) != edge[j]) // 前后矛盾{cout << -1 << endl;return;}}}}for (int j = 0; j < 30; j++){ans += (1LL << j) * min(cnt[j], sz[i] - cnt[j]); // 二进制加法，cnt是1的个数，sz-cnt是0的个数，min(cnt[j], sz[i] - cnt[j])其实是当前连通快中第j位的贡献}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--){solve();}return 0;
}

---

E - Edward Gaming, the Champion

题意

给个字符串，找有几个"edgnb"。

思路

模拟。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{string s;cin >> s;if (s.size() < 5){cout << 0 << endl;return;}int ans = 0;for (int i = 0; i <= s.size() - 5; i++){if (s[i] == 'e' && s[i + 1] == 'd' && s[i + 2] == 'g' && s[i + 3] == 'n' && s[i + 4] == 'b'){ans++;}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--){solve();}return 0;
}

---

F - Encoded Strings I

题意

给定一个长度为\(n(n≤1000)\)的字符串\(s\)，定义函数\(Fs:Fs(c)=chr(G(c, S))\)，表示将\(S\)中的每个字符\(c\)转换为\(chr(G(c, S))\)，其中\(G(c, S)\)表示\(S\)中最后一次出现\(c\)之后的后缀中不同的字符个数，\(chr(i)\)表示第\(i\)个字符(第个\(0\)字符是 \(a\)，第\(1\)个是\(b\)…)。要求你对\(s\)的每个非空前缀代入到函数中，得到\(n\)个字符串，输出按照字典序排序的最大字符串。

思路

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long longconst int mxn = 1e3 + 5;unordered_map<char, int> cnt[mxn];void solve()
{int n;string s;cin >> n >> s;for (int i = n; i >= 1; i--){int cntt = 0;unordered_set<char> vis;for (int j = i - 1; j >= 0; j--){if (!vis.count(s[j])){vis.insert(s[j]);cnt[i][s[j]] = cntt++;}}}set<string, greater<string>> ans;for (int i = n; i >= 1; i--){string t = s.substr(0, i);for (int j = i - 1; j >= 0; j--){t[j] = cnt[i][t[j]] + 'a';}ans.insert(t);}cout << *ans.begin() << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--){solve();}return 0;
}

---

J - Luggage Lock

题意

四位密码锁，每次能把一位或连续的几位向上或向下转动一个单位。现给两个密码\(A\)和\(B\)，求从\(A\)到\(B\)的最少操作数。

思路

\(T\)挺大，一个个来铁超时，直接从\(0000\)开始用\(bfs\)打表，查的时候就可以等价于查\(0000\)\(A\)和\(B\)之间的差值，即查\(1234\)到\(4689\)相当于查\(0000\)到\(3455\)。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long longtypedef pair<string, int> pii;map<string, int> ans;
set<string> vis;string cmd[] = { "1000","0100", "0010", "0001", "1100",   "0110", "0011", "1110","0111", "1111", "2000","0200", "0020", "0002", "2200",  "0220",  "0022", "2220", "0222", "2222" }; // 1代表+，2代表-string change(string s, int idx)
{string res = s;for (int i = 0; i < 4; i++){if (cmd[idx][i] == '1'){res[i]++;if (res[i] > '9'){res[i] = '0';}}else if (cmd[idx][i] == '2'){res[i]--;if (res[i] < '0'){res[i] = '9';}}}return res;
}void bfs()
{queue<pii> q;q.push({ "0000", 0 });vis.insert("0000");while (q.size()){string cur = q.front().first;int cnt = q.front().second;q.pop();for (int i = 0; i < 20; i++) // 把cur的全部情况都存了{string t = change(cur, i);if (!vis.count(t)){vis.insert(t);ans[t] = cnt + 1;q.push({ t, cnt + 1 });}}}
}void solve()
{string a, b;cin >> a >> b;if (a == b){cout << 0 << endl;return;}string t = "";for (int i = 0; i < 4; i++){t.push_back((b[i] - a[i] + 10) % 10 + '0');}cout << ans[t] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;bfs();while (T--){solve();}return 0;
}

---

---

比赛链接 https://codeforces.com/gym/103427