图片来源
1901 字
10 分钟
ICPC Asia EC Online 2025(I)
其实很早之前就补的差不多了，可以看到 16 号就打算写了，后来一直拖，拖到了现在。
这场我们打的挺好的，我只写了一道大模拟，然后队友已经切完了，最后做交互题没调出来。
A. Who Can Win
这就是一道大模拟，逻辑上没有难度，代码不在我这个机子上，没存也不想再写一遍了，记得当时有三个东西没初始化挂掉了（当时没有立刻发现），然后电脑让出去了，浪费了好长时间。
B. Creating Chaos
当时说是隔几个取一个来着，后来发现直接取前 k 个就行。
#include <iostream>
using namespace std;
int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) printf("%d ", i); printf("\n"); return 0;}C. Canvas Painting
用贪心的思想，维护一个候选集合，枚举位置，加入的时候先取左端点最小的，取出的时候优先取右端点最小的，补题的时候挂了好几次。
#include <iostream>#include <queue>#include <algorithm>
using namespace std;typedef pair<int, int> PII;const int N = 200010;PII a[N];
int main() { int T; scanf("%d", &T); while (T--) { priority_queue<int, vector<int>, greater<int>> q; int n, m, cur = 0; scanf("%d%d", &m, &n); for (int i = 1; i <= m; ++i) { scanf("%d%d", &a[i].first, &a[i].second); } sort(a + 1, a + m + 1); int res = n, j = 0; while (cur <= n && j < m) { while (j < m && cur > a[j + 1].first) q.push(a[++j].second); while (!q.empty() && cur > q.top()) q.pop(); if (!q.empty()) cur++, q.pop(), res--; else cur = a[j + 1].first + 1; } while (!q.empty()) { if (cur <= q.top()) cur++, res--; q.pop(); } printf("%d\n", res); } return 0;}D. Min-Max Tree
这道是树形 dp，关键就是不能被题目描述带着走，不能从怎么删这个角度考虑，应该考虑在树中取 k 个正值，k 个负值，一个连通块只能有一个正和一个负，权值和最大，把合法状态空间扩大了，但是最优解一定还是原问题的最优解。对于一个连通块只有三种情况，平衡，正，负，考虑状态转移，一个块最多只能有一个正和一个负，正向反向线性 dp 维护一下只有一个正，只有一个负，全是 0 的前后缀，枚举分界点向根合并。这道题补的时候没有调很久。
#include <iostream>
using namespace std;typedef long long LL;const int N = 1000010;int ver[N * 2], ne[N * 2], head[N], tot;LL a[N], f[N][3]; // 0 配对 1 正 2 负LL pre[N][3], suf[N][3];int idx[N];
void add(int x, int y) { ver[++tot] = y; ne[tot] = head[x]; head[x] = tot;}
void dp(int x, int fa) { for (int i = head[x]; i; i = ne[i]) { int y = ver[i]; if (y == fa) continue; dp(y, x); } int l = 0; for (int i = head[x]; i; i = ne[i]) { if (ver[i] == fa) continue; idx[++l] = ver[i]; } if (!l) { f[x][1] = a[x], f[x][2] = -a[x]; return; } idx[0] = idx[l + 1] = 0; pre[0][1] = pre[0][2] = suf[l + 1][1] = suf[l + 1][2] = -2000000000; pre[0][0] = suf[l + 1][0] = 0; for (int i = 1; i <= l; ++i) { int y = idx[i]; pre[i][0] = pre[i - 1][0] + f[y][0]; pre[i][1] = max(pre[i - 1][0] + f[y][1], pre[i - 1][1] + f[y][0]); pre[i][2] = max(pre[i - 1][0] + f[y][2], pre[i - 1][2] + f[y][0]); } for (int i = l; i; --i) { int y = idx[i]; suf[i][0] = suf[i + 1][0] + f[y][0]; suf[i][1] = max(suf[i + 1][0] + f[y][1], suf[i + 1][1] + f[y][0]); suf[i][2] = max(suf[i + 1][0] + f[y][2], suf[i + 1][2] + f[y][0]); } // if (x == 1) cout << suf[1][1] << " " << suf[1][2] << endl; f[x][0] = max(suf[1][0], max(suf[1][1] - a[x], suf[1][2] + a[x])); f[x][1] = max(suf[1][0] + a[x], suf[1][1]); f[x][2] = max(suf[1][0] - a[x], suf[1][2]); for (int i = 1; i < l; ++i) { f[x][0] = max(f[x][0], max(pre[i][1] + suf[i + 1][2], pre[i][2] + suf[i + 1][1])); }}
int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y), add(y, x); } dp(1, 0); // for (int i = 1; i <= n ;++i) { // cout << i << " : "; // for (int j = 0; j < 3; ++j) cout << f[i][j] << ' '; // cout << endl; // } printf("%lld\n", f[1][0]); return 0;}G. Sorting
签到题，我们当时被卡了会儿，不应该，举了一个错的例子卡了自己对的想法。
#include <iostream>
using namespace std;
const int N = 200010;bool f[N];
int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { int l, r; scanf("%d%d", &l, &r); if (l + 1 == r) f[l] = true; } for (int i = 1; i < n; ++i) { if (!f[i]) { printf("No\n"); return 0; } } printf("Yes\n"); return 0;}I. Knapsack Problem欠
J. Moving on the Plane补
感觉我们当时的思路就差一点就想出来了，我感觉确实是因为感觉排名够了，都不是很想努力了。
转成切比雪夫距离之后 x 反向和 y 方向就完全拆开了，对于每个坐标轴上分别做一次
- 枚举所有可以到达的长度为 k 的区间，算出来方案数，减去用相同做法做一遍长度为 k - 1 的区间的方案数（这是一个容斥的过程，他是相邻两段交叉，k - 1 的正好就是 k 多出来的重叠部分）。
两个维度的答案乘一下就是答案。
#include <iostream>
using namespace std;typedef long long LL;const int MOD = 998244353;const int N = 60, M = 100010, lim = 300000;int a[N], b[N];LL jc[M], inv[M];
LL power(LL n, LL p) { LL res = 1, base = n; while (p) { if (p & 1) res = res * base % MOD; base = base * base % MOD; p >>= 1; } return res;}
LL c(int n, int m) { if (m > n) return 0; return jc[n] * inv[m] % MOD * inv[n - m] % MOD;}
int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); jc[0] = 1; for (int i = 1; i <= m; ++i) { jc[i] = jc[i - 1] * i % MOD; } inv[0] = 1; inv[m] = power(jc[m], MOD - 2); for (int i = m - 1; i; --i) { inv[i] = inv[i + 1] * (i + 1) % MOD; } for (int i = 1; i <= n; ++i) { int x, y; scanf("%d%d", &x, &y); a[i] = x + y, b[i] = x - y; } LL res = 1, s; for (int T = 0; T < 2; ++T) { s = 0; for (int j = k, t = 1; j >= max(0, k - 1); --j, t *= -1) { // 长度 for (int i = -lim; i + j <= lim; ++i) { // 左端点 LL ts = 1; for (int p = 1; p <= n; ++p) { LL tt = 0; for (int l = 0; l <= j; ++l) { int len = abs(i + l - a[p]); if (m >= len && (m - len) % 2 == 0) tt = (tt + c(m, (m - len) / 2)) % MOD; } ts = (ts * tt) % MOD; if (!ts) break; } s = ((s + ts * t) % MOD + MOD) % MOD; } } res = res * s % MOD; swap(a, b); } printf("%lld\n", res); return 0;}M. Teleporter
当时我们分层图 Dijkstra 卡过了，补题的时候我也这么过的，但是这个 Dijkstra 应该比较多余，目测再从上到下扫一遍也能达成效果。
#include <iostream>#include <cstring>#include <queue>#include <tuple>using namespace std;typedef long long LL;const int N = 5010, M = 10010;
int head[N], ver[N * 2], ne[N * 2], w[N * 2], tot;pair<int, int> a[M];LL dis[N], b[N];bool vis[N];priority_queue<pair<LL, int>> q;
void add(int x, int y, int z) { ver[++tot] = y; ne[tot] = head[x]; head[x] = tot; w[tot] = z;}
void dijkstra() { memset(vis, 0, sizeof(vis)); while (!q.empty()) { auto [_, x] = q.top(); q.pop(); if (vis[x]) continue; vis[x] = true; for (int i = head[x]; i; i = ne[i]) { int y = ver[i]; if (dis[y] > dis[x] + w[i]) { dis[y] = dis[x] + w[i]; q.emplace(-dis[y], y); } } }}
int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i < n; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z), add(y, x, z); } for (int i = 1; i <= m; ++i) { scanf("%d%d", &a[i].first, &a[i].second); } memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; q.emplace(-dis[1], 1); for (int t = 0; t <= n; ++t) { dijkstra(); LL res = 0; for (int i = 1; i <= n; ++i) { res += dis[i]; } printf("%lld\n", res); memset(b, 0x3f, sizeof(b)); for (int i = 1; i <= m; ++i) { b[a[i].second] = min(b[a[i].second], min(dis[a[i].second], dis[a[i].first])); b[a[i].first] = min(b[a[i].first], min(dis[a[i].second], dis[a[i].first])); } for (int i = 1; i <= n; ++i) { dis[i] = min(dis[i], b[i]); q.emplace(-dis[i], i); } } return 0;}可怜的 Laffey 被卡了。
ICPC Asia EC Online 2025(I)
https://starlab.top/posts/25icpc-ol-1/ 部分信息可能已经过时
