A. AVL tree
题意：给你一棵二叉树，你每次可以删除一个点，或者对于一个缺少了某个左右儿子的节点补充一个子节点。求变成\(AVL\)树的最少操作。\(AVL\)树是指任意一个节点都有左右儿子高度差小于等于\(1\)。节点高度为左右儿子最大高度加一。空节点高度为\(0\)。
考虑一颗高度为\(h\)的\(AVL\)树最少要几个节点，那么左右儿子一个高度为\(h-2\)，一个为\(h-1\)，则\(cnt_h = cnt_{h-1} + cnt_{h-2} + 1\)。容易发现这个式子增长的很快。因为有一个解是删除所有\(n\)个点，所以答案不会劣于\(n\)，所以最后树的高度不会很大，我们设个\(30\)。
那么记\(f[u][i]\)表示\(u\)这棵子树高度为\(i\)的最少操作次数，转移就是讨论一下，两个子树高度差小于等于\(1\)，一定有一个子树高度为\(i-1\)。如果 \(i=1\)那么意味着把\(u\)着棵子树除了\(u\)都删掉。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> l(n), r(n);for (int i = 0; i < n; ++ i) { std::cin >> l[i] >> r[i];-- l[i];-- r[i];}std::vector<i64> f(40);f[0] = 0; f[1] = 1;for (int i = 2; i <= 30; ++ i) {f[i] = f[i - 1] + f[i - 2] + 1;}std::vector<int> size(n);std::vector dp(n, std::array<i64, 31>{});const i64 inf = 1e9;auto dfs = [&](auto & self, int u) -> void {size[u] = 1;dp[u].fill(inf);if (l[u] == -1 && r[u] == -1) {for (int i = 1; i <= 30; ++ i) {dp[u][i] = f[i] - 1;}} else if (l[u] == -1) {self(self, r[u]);size[u] += size[r[u]];dp[u][1] = size[u] - 1;for (int i = 2; i <= 30; ++ i) {dp[u][i] = std::min(dp[u][i], dp[r[u]][i - 1] + f[std::max(0, i - 2)]);dp[u][i] = std::min(dp[u][i], dp[r[u]][std::max(0, i - 2)] + f[i - 1]);}} else if (r[u] == -1) {self(self, l[u]);size[u] += size[l[u]];dp[u][1] = size[u] - 1;for (int i = 2; i <= 30; ++ i) {dp[u][i] = std::min(dp[u][i], dp[l[u]][i - 1] + f[std::max(0, i - 2)]);dp[u][i] = std::min(dp[u][i], dp[l[u]][std::max(0, i - 2)] + f[i - 1]);}} else {self(self, l[u]);self(self, r[u]);size[u] += size[l[u]] + size[r[u]];dp[u][1] = size[u] - 1;for (int i = 2; i <= 30; ++ i) {for (int j = i - 1; j >= std::max(0, i - 2); -- j) {for (int k = i - 1; k >= std::max(0, i - 2); -- k) {if (std::max(j, k) == i - 1 && std::abs(j - k) <= 1) {dp[u][i] = std::min(dp[u][i], dp[l[u]][j] + dp[r[u]][k]);}}}}}};dfs(dfs, 0);i64 ans = n;for (int i = 0; i <= std::min(30, n); ++ i) {ans = std::min(ans, dp[0][i]);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Epoch-making
题意：给你一个有向无环图，每个点有点权。你每次可以选择一部分点，只要其中每个点的后继边的点都被选择过了，代价为这些的点最大点权。求选完所有点的最小代价。\(n\leq 24\)。
一个比较暴力的做法是，先预处理每个点集的代价，然后枚举每个集合的子集，从这些子集转移过来。这样是\(3^n\)的。
继续观察性质，考虑哪些选法一定不是最优，因为是取最大值，那么如果选择了一个点，对于其它能选的点且点权小于等于这个点的，都选上不会导致答案变差。那么把每个点按点权从小到大排序，然后枚举集合，每次尝试扩展这个集合，那么应该对于这个集合能选的点里从小到大选一个前缀。
循环转移是\(n2^n\)，但有很多状态是非法的，可以用记忆化搜索通过。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<std::pair<int, int>> a(n);for (int i = 0; i < n; ++ i) {int w;std::cin >> w;a[i] = {w, i};}std::ranges::sort(a);std::vector<int> id(n), w(n);for (int i = 0; i < n; ++ i) {w[i] = a[i].first;id[a[i].second] = i;}std::vector<int> adj(n);for (int i = 0; i < m; ++ i) {int u, v;std::cin >> u >> v;-- u, -- v;u = id[u];v = id[v];adj[v] |= 1 << u;}constexpr int inf = 1e9;std::vector<int> f(1 << n, -1);auto dfs = [&](auto & self, int s) -> int {if (s == (1 << n) - 1) {return 0;}if (f[s] != -1) {return f[s];}int res = inf, cur = s;for (int i = 0; i < n; ++ i) {if ((~s >> i & 1) && (s & adj[i]) == adj[i]) {cur |= 1 << i;res = std::min(res, self(self, cur) + w[i]);}}return f[s] = res;};std::cout << dfs(dfs, 0) << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
F. Military Training
题意：两个长度为\(1\)的线段，你要通过每次让一个线段绕它的一个点旋转90$度来使得两个线段重合，求最少次数。
题解是直接求中点然后转换为曼哈顿距离，代码就几行。
赛时分类讨论调了半天，我的做法是先把线段都变成竖着的或者横着的。然后一个点可以通过两次旋转使得横纵坐标都变化\(1\)，这些操作先使得两个线段处在一条直线上，然后在旋转过去。然后还要讨论一下哪个点对应哪个点。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;struct P {i64 x, y;
};i64 get(P a, P b, P c, P d) {i64 t = std::min(std::abs(b.x - d.x), std::abs(b.y - d.y));i64 ans = t * 2;t = std::max(std::abs(b.x - d.x), std::abs(b.y - d.y)) - t;ans += t / 2 * 4;t %= 2;ans += t * 2;return ans;
}void solve() {P a, b, c, d;std::cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;if (a.x > b.x || a.y > b.y) {std::swap(a, b);}if (c.x > d.x || c.y > d.y) {std::swap(c, d);}i64 ans = 1e18;if ((a.x == b.x) != (c.x == d.x)) { if (a.x == b.x) {auto x = a;auto y = a;x.x -= 1; y.x += 1;ans = std::min({ans, get(x, a, c, d) + 1, get(a, y, c, d) + 1});x = b;y = b;x.x -= 1; y.x += 1;ans = std::min({ans, get(x, b, c, d) + 1, get(b, y, c, d) + 1});} else {auto x = a;auto y = a;x.y -= 1; y.y += 1;ans = std::min({ans, get(x, a, c, d) + 1, get(a, y, c, d) + 1});x = b;y = b;x.y -= 1; y.y += 1;ans = std::min({ans, get(x, b, c, d) + 1, get(b, y, c, d) + 1});}} else {ans = get(a, b, c, d);} std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
J. Too many catgirls nya
题意：每一行的输入后面加上\(nya\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::cout << n << " nya\n";getchar();for (int i = 0; i < n; ++ i) {std::string s;char c;while ((c = getchar()) != '\n') {s += c;}std::cout << s;std::cout << " nya\n";}
}int main() {// std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
L. Ping Pong
题意：\(n\)个人打擂台，每个人有一个值，从前往后，一开始第一个人站在擂台上，然后依次和后面的人比，值小的排到最后，值大的留下。如果一个人连续赢了\(n-1\)轮，则第\(n\)轮这个人必败。求\(k\)轮后每个人打过几次擂台。每个人的值两两不同。
因为值两两不同，可以看作一个排列，考虑这样一个排列：\(n, 1, 2, ... ,n - 1\)，如果此时\(n\)已经赢过一次了，你会发现\(2n - 2\)轮后又回到了这个状态，这个轮回中\(n\)和\(n-1\)打了\(n\)次，其它都打了\(2\)次。
然后打表发现，每个初始状态最后都会变成这个状态，这个状态就是循环节。
因为每次小的数会排到后面，有点排序的味道。所以想达到循环应该不需要很多轮操作。那么可以先把循环节模拟出来，然后就可以直接计算贡献。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::vector<int> ans(n);int K = std::min(4 * n, k);std::queue<int> q;for (int i = 1; i < n; ++ i) {q.push(i);}int cur = 0, cnt = 0;while (K -- ) {k -- ;int x = q.front(); q.pop();++ ans[cur]; ++ ans[x];++ cnt;if (cnt == n || a[x] > a[cur]) {q.push(cur);cur = x;cnt = 1;} else {q.push(x);}}int max = std::ranges::max(a);int p = 0;while (k) {k -- ;int x = q.front(); q.pop();++ ans[cur]; ++ ans[x];++ cnt;if (cnt == n || a[x] > a[cur]) {if (a[x] == max) {p = cur;q.push(cur);cur = x;cnt = 1;break;}q.push(cur);cur = x;cnt = 1;} else {q.push(x);}}int t = k / (2 * n - 2);k -= t * (2 * n - 2);for (int i = 0; i < n; ++ i) {if (a[i] == max || i == p) {ans[i] += t * n;} else {ans[i] += t * 2;}}while (k -- ) {int x = q.front(); q.pop();++ ans[cur]; ++ ans[x];++ cnt;if (cnt == n || a[x] > a[cur]) {q.push(cur);cur = x;cnt = 1;} else {q.push(x);}}for (int i = 0; i < n; ++ i) {std::cout << ans[i] << " \n"[i == n - 1];}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
M. Digit Sum
题意：记\(S(n)\)为\(n\)的数位和，给出\(n\)，求有没有一个\(a\)使得\(S(na) = aS(n)\)。
\(n\leq 10^9\)，最大数位和不超过\(81\)，所以\(a\)也不会很大。枚举到\(100\)就行。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {i64 n;std::cin >> n;auto S = [&](i64 n) -> int {int res = 0;while (n) {res += n % 10;n /= 10;}return res;};for (int a = 1; a <= 100; ++ a) {if (S(n * a) == n * S(a)) {std::cout << a << "\n";return;}}std::cout << -1 << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}