The 2024 ICPC Asia Nanjing Regional Contest
外榜 https://board.xcpcio.com/icpc/49th/nanjing
铜线: 3题406-137 ~ 4题607
银线: 4题606-357 ~ 5题650
金线: 5题645-467 6题+
难度(个人感觉):
纯签: E
半签: J
Easy: K
Mid: GB
E
题意
一个字符串循环左移(第一个放到最后)最多\(k\)次，求包含子串"nanjing"的最大数量。
思路
水题，暴力即可。
代码
void solve() {int n, k;cin >> n >> k;string s;cin >> s;auto find = [&] (string s) -> int {int ans = 0;for (int i = 6; i < n; i++) {string str = s.substr(i - 6, 7);if (str == "nanjing") {ans++;}}return ans;};int ans = find(s);for (int i = 0; i < std::min(7, k); i++) {char x = s[0];std::reverse(all(s));s.pop_back();std::reverse(all(s));s.push_back(x);ans = std::max(ans, find(s));}cout << ans << "\n";
}
J
题意
一共\(k\)个人，你与\(n\)个是好友。
有\(m\)条消息，每条消息和某两个人相关，如果你和这两个人都是好友，就能看到这条消息。
最多可以添加两个新好友，求能看到的最多的消息数量。
思路
要么选两个之间有消息的，要么直接选两个相关消息最多的。
代码
void solve() {int n, m, k;cin >> n >> m >> k;vector<bool> a(k + 1);for (int i = 0; i < n; i++) {int x;cin >> x;a[x] = 1;}vector<int> cnt(k + 1);int ans = 0;std::map<std::pair<int, int>, int> mp;for (int i = 0; i < m; i++) {int x, y;cin >> x >> y;if (a[x] && a[y]) {ans++;} else if (a[x]) {cnt[y]++;} else if (a[y]) {cnt[x]++;} else {if (x == y) {cnt[x]++;} else if (x > y) {std::swap(x, y);}mp[{x, y}]++;}}int add = 0;for (auto [o, s] : mp) {auto [x, y] = o;add = std::max(add, s + (x != y) * (cnt[x] + cnt[y]));}std::sort(all(cnt), std::greater<>() );add = std::max(add, cnt[0] + cnt[1]);cout << ans + add << "\n";
}
K
题意
一共\(w \le 10^9\)个格子，其中\(n\)个红色，\(m\)个黑色，其他都是白色。
使用长度为\(k\)的带子覆盖所有红色，且不能覆盖到黑色，每个格子最多覆盖一次。
求需要的最少带子的数量，或者不存在方案。
思路
用黑色把w个格子分成若干个区间，在每个区间内去覆盖，带子不能超出区间。
对于每个区间，先以最左端的红色为起点，依次向右覆盖，最后一个超出区间，就需要向左移，和前一个重叠了，前一个也需要向左移，依此类推，如果最左端的也超出区间，则不存在方案。
算是个模拟吧。
代码
void solve() {int n, m, k, w;cin >> n >> m >> k >> w;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> b(m);for (int i = 0; i < m; i++) {cin >> b[i];}b.push_back(0);b.push_back(w + 1);std::sort(all(a));std::sort(all(b));std::vector<std::pair<int, int>> seg;for (int i = 1; i < b.size(); i++) {seg.push_back({b[i - 1] + 1, b[i] - 1});}int ans = 0;vector<int> res;for (auto [l, r] : seg) {int x = std::lower_bound(all(a), l) - a.begin();int y = std::lower_bound(all(a), r + 1) - a.begin() - 1;if (x >= n || x > y) {continue;}if (r - l + 1 < k) {cout << -1 << "\n";return;}vector<std::pair<int, int>> seg2;int tail;for (int i = x; i <= y; i++) {if (i == x) {tail = a[i] + k - 1;seg2.push_back({a[i], tail});} else if (a[i] > tail) {tail = a[i] + k - 1;seg2.push_back({a[i], tail});}}if (seg2.back().second > r) {auto &[L, R] = seg2.back();int del = R - r;L -= del, R -= del;for (int i = seg2.size() - 2; i >= 0; i--) {if (seg2[i].second >= seg2[i + 1].first) {int del = seg2[i].second - seg2[i + 1].first + 1;seg2[i].first -= del;seg2[i].second -= del;}}if (seg2[0].first < l) {cout << -1 << "\n";return;}}for (auto [L, R] : seg2) {res.push_back(L);}ans += seg2.size();}cout << ans << "\n";for (auto i : res) {cout << i << " ";}cout << "\n";
}
G
题意
- 交互
一棵\(n\)节点的二叉树，最多可以\(p\)次询问，\(2^p \le n\)。找出一个事先设定的特殊点。
int query(int u, int v) { // 每次询问两个节点std::cout << "? " << u << " " << v << std::endl;int t;std::cin >> t;// t = 0 特殊点离 u 近// t = 1 特殊点与 u v 的距离相等// t = 2 特殊点离 v 近// 距离表示简单路径上的边数return t;
}
思路
\(log_2n\)次查询，明显二分。vp时写了2小时二分，写了一坨没做出来。
看官方题解发现，要以树的重心为分界点走分支。每次查询重心子树最大的两个子节点，离重心近则分离两个子树，否则分离除了离得近的子树的所有节点。
代码
void solve() {int n;cin >> n;vector<vector<int>> e(n + 1);for (int i = 1; i <= n; i++) {int x, y;cin >> x >> y;if (x) {e[i].push_back(x);e[x].push_back(i);}if (y) {e[i].push_back(y);e[y].push_back(i);}}auto query = [&] (int u, int v) -> int {cout << "? " << u << " " << v << std::endl;int t;cin >> t;return t;};vector<bool> del(n + 1);vector<int> size(n + 1), max(n + 1);auto dfs = [&] (auto &&dfs, int root) -> void {int g;auto find = [&] (auto &&find, int x, int fa) -> void {size[x] = 1;max[x] = 0;for (auto u : e[x]) {if (u != fa && !del[u]) {find(find, u, x);size[x] += size[u];max[x] = std::max(max[x], size[u]);}}max[x] = std::max(max[x], n - size[x]);if (max[x] <= n / 2) {g = x;}};find(find, root, 0);find(find, g, 0);vector<std::pair<int, int>> son;for (auto u : e[g]) {if (!del[u]) {son.push_back({size[u], u});}}std::sort(all(son), std::greater<> ());if (son.empty()) {cout << "! " << g << std::endl;return;}int u = g, v = 0;if (son.size() == 1) {v = son[0].second;int t = query(u, v);if (t == 0) {cout << "! " << u << std::endl;} else {cout << "! " << v << std::endl;}} else {u = son[0].second, v = son[1].second;int t = query(u, v);if (t == 0) {del[g] = 1;n = size[u];dfs(dfs, u);} else if (t == 2) {del[g] = 1;n = size[v];dfs(dfs, v);} else {del[u] = del[v] = 1;n -= size[u] + size[v];dfs(dfs, g);}}};dfs(dfs, 1);
}
B
题意
一个包含\(012\)三种字符的字符串，可以执行任意次操作，每次操作，可以将某个\(2\)改为\(0\)或\(1\)，或者选择相邻的两个\(0\)或\(1\)删掉并拼接字符串。求字符串可以达到的最短长度。
思路
神秘题目。
若删除两个字符，一定是删除一个奇数位一个偶数位，且每个字符下标的奇偶性不会变。
将所有偶数位取反，那么删除操作就变成了删除相邻两个不同的，则最终字符串一定是全\(0\)或全\(1\)。
所以\(2\)就可以每次修改成当前数量少的那一个。
代码
void solve() {string s;cin >> s;for (int i = 1; i < s.size(); i += 2) {if (s[i] == '0') {s[i] = '1';} else if (s[i] == '1') {s[i] = '0';}}int s0 = std::count(all(s), '0');int s1 = std::count(all(s), '1');int s2 = std::count(all(s), '2');if (s0 + s2 < s1) {cout << s1 - (s0 + s2) << "\n";} else if (s1 + s2 < s0) {cout << s0 - (s1 + s2) << "\n";} else {cout << ((s0 + s1 + s2) & 1) << "\n";}
}