2025 ICPC Asia EC 网络赛第一场

A. Who Can Win

模拟题，没啥好说的。

A. Who Can Win 示例代码

A. Who Can Win

#include <bits/stdc++.h>

using namespace std;

struct submit {
	string name; char prob; int tim; string state;
	inline void in() {
		cin >> name >> prob >> tim >> state;
	}
	bool operator < (const submit &rhs) {
		return tim < rhs.tim;
	}
};
const int N = 1e5 + 10;
pair<int, int> mx[N], mn[N];
vector<submit> ar[N];
string uid[N];

inline void solve() {
	int n; cin >> n;
	map<string, int> id; int cnt = 0;
	vector<submit> v(n);
	for(int i = 0; i < n; i ++) {
		v[i].in();
		if(!id.count(v[i].name)) {
			id[v[i].name] = ++cnt; 
			uid[cnt] = v[i].name;
		}
	}
	for(int i = 1; i <= cnt; i ++)
		mx[i] = {0, 0}, mn[i] = {0, 0};
	for(int i = 1; i <= cnt; i ++) ar[i].clear();
	for(int i = 0; i < n; i ++)
		ar[id[v[i].name]].push_back(v[i]);
	for(int i = 1; i <= cnt; i ++) {
		sort(ar[i].begin(), ar[i].end());
		bool ok[26];
		int siz[26];
		for(int j = 0; j < 26; j ++) 
			ok[j] = false, siz[j] = 0;
		for(auto x : ar[i]) {
			if(ok[x.prob - 'A']) continue;
			if(x.state == "Accepted") {
				ok[x.prob - 'A'] = true;
				mx[i].first ++, mn[i].first ++;
				mx[i].second += x.tim, mn[i].second += x.tim;
				mx[i].second += siz[x.prob - 'A'] * 20;
				mn[i].second += siz[x.prob - 'A'] * 20;
			} else if(x.state == "Rejected") {
				siz[x.prob - 'A'] ++;
			} else {
				int y = x.prob - 'A';
				mx[i].first ++, mx[i].second += x.tim;
				mx[i].second += siz[x.prob - 'A'] * 20;
				ok[y] = true;
			}
		}
	}
	sort(mn + 1, mn + cnt + 1, [&](pair<int, int> a, pair<int, int> b) {
		if(a.first != b.first) return a.first > b.first;
		return a.second < b.second;
	});
	vector<string> ans;
	for(int i = 1; i <= cnt; i ++) {
		if((mx[i].first > mn[1].first) || (mx[i].first == mn[1].first && mx[i].second <= mn[1].second)) {
			ans.push_back(uid[i]);
		}
	}
	sort(ans.begin(), ans.end());
	for(auto s : ans)
		cout << s << ' ';
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	int T; cin >> T;
	while(T --) solve();

	return 0;
}

B. Creating Chaos

结论：最终剩下连续的个数最优。

证明考虑原式等于

这是因为。

对于，我们可以以的代价先取遍到，之后，尽量选模意义下不同的数会优于选相同的数，因此直接选择留下是最优的（或者选其它长度为的连续段）。

B. Creating Chaos 示例代码

B. Creating Chaos

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	int n, k; cin >> n >> k;
	for(int i = 1; i <= k; i ++)
		cout << i << ' ';

	return 0;
}

C. Canvas Painting

贪心，从小到大依次考虑每个数是否可以变为前面的数使得最终答案减一。

为此，我们用一个小根堆维护可以覆盖当前考虑到的位置的区间的右端点，每次选择右端点最小的那个区间，用这个区间的操作改变当前位置即可，时间复杂度

C. Canvas Painting 示例代码

C. Canvas Painting

#include <bits/stdc++.h>

using namespace std;

inline void solve() {
	int m, n; cin >> m >> n;
	map<int, vector<int>> Map;
	for(int i = 0; i < m; i ++) {
		int l, r; cin >> l >> r;
		if(l < r) Map[l].push_back(r);
	}
	auto it = Map.begin(); int pos = 1, ans = n;
	priority_queue<int, vector<int>, greater<int>> Q;
	while(pos < n) {
		if(Map.count(pos)) {for(int r : Map[pos]) Q.push(r); }
		while(!Q.empty() && Q.top() <= pos) Q.pop();
		if(Q.empty()) {
			while(it != Map.end() && it->first <= pos) ++it;
			if(it == Map.end()) break;
			else pos = it->first;
		} else Q.pop(), pos ++, ans --;
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	int T; cin >> T;
	while(T --) solve();

	return 0;
}

D. Min-Max Tree

引理1：存在一种最优的切分方式使得最终的每个连通块中，值最小、最大的点均是叶子。

这是因为如果不是叶子，将多余的部分分为另一个连通块一定不会更劣。

引理2：存在一种最优的切法使得最终每个连通块都是链。

和引理 1 类似，拎出最大、最小结点构成的那条链，剩下的部分可以切出去，白赚了一些连通块，不会更劣。

因此，我们可以直接钦定最终切出了一堆链，并且链的两端分别是最大、最小值。

引理3：最终每条链上的点的权值单调。

否则，不妨设链由两部分组成，它们的值域分别为与，其中，那么这条链的贡献为，不如拆为。

根据这个树形dp，设表示子树的答案，表示子树内有一条伸出子树的链，链的最大值已经算进贡献的答案，表示子树内有一条伸出子树的链，链的最小值已经算进贡献的答案，时间复杂度

D. Min-Max Tree 示例代码

D. Min-Max Tree

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int n, A[N];
vector<int> G[N];

long long f[N], g[N], h[N];
// f: 闭合
// g: 作为左端点
// h: 作为右端点
void dfs(int u, int fa) {
	long long sum = 0;
	for(int v : G[u]) {
		if(v == fa) continue;
		dfs(v, u);
		sum += f[v];
	}
	f[u] = sum, g[u] = A[u] + sum, h[u] = -A[u] + sum;
	vector<long long> v_h, v_g;
	for(int v : G[u]) {
		if(v == fa) continue;
		if(A[u] > A[v]) {
			f[u] = max(f[u], sum - f[v] + A[u] + h[v]);
			v_h.push_back(-f[v] + h[v]);
			h[u] = max(h[u], sum - f[v] + h[v]);
		}
		if(A[u] < A[v]) {
			f[u] = max(f[u], sum - f[v] - A[u] + g[v]);
			g[u] = max(g[u], sum - f[v] + g[v]);
			v_g.push_back(-f[v] + g[v]);
		}
	}
	if(!v_h.empty() && !v_g.empty()) {
		sort(v_h.begin(), v_h.end(), greater<long long>());
		sort(v_g.begin(), v_g.end(), greater<long long>());
		f[u] = max(f[u], sum + v_h[0] + v_g[0]);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> A[i];
	for(int i = 1; i < n; i ++) {
		int a, b; cin >> a >> b;
		G[a].push_back(b), G[b].push_back(a);
	}
	dfs(1, 0);
	cout << f[1] << '\n';

	return 0;
}

F. Robot

策略：先堵上一个角，，，然后尽量隔填，即尽可能如图所示地堵：

将机器人困在这个矩形内后，不断堵它脚下即可。

优先级为：

优先堵边界
边界上，优先堵图中所示的X和机器人一步可以走到的位置（否则机器人就跑出去了）
边界上优先级的第二个关键字为它到机器人的曼哈顿距离

这样，机器人无论如何也走不出这个矩形。

F. Robot 示例代码

F. Robot

#include <bits/stdc++.h>

using namespace std;
int x, y;
bool vis[50][50];
inline void mark(int a, int b) {
	vis[a][b] = true;
	cout << a << ' ' << b << endl;
	cin >> x >> y;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	int B = 28;
	cin >> x >> y;
	mark(B, B), mark(B - 1, B), mark(B, B - 1);
	while(x || y) {
		array<int, 3> A = {1000, x, y};
		for(int i = 1; i <= B; i ++) {
			if(!vis[B][i]) {
				array<int, 3> T = {((abs(B - x) > 1 || abs(i - y) > 1) && (i % 3 == 2)) * 500 + abs(B - x) + abs(i - y),
									B, i};
				A = min(A, T);
			}
			if(!vis[i][B]) {
				array<int, 3> T = {((abs(i - x) > 1 || abs(B - y) > 1) && (i % 3 == 2)) * 500 + abs(i - x) + abs(B - y),
									i, B};
				A = min(A, T);
			}
		}
		mark(A[1], A[2]);
	}

	return 0;
}

G. Sorting

答案为Yes当且仅当存在1 2，2 3,……，n-1 n。

首先，如果这些都存在的话，答案一定为Yes，否则，如果不存在i i+1，构造序列1 2 3 ... i-1 i+1 i i+2 ... n，它无法被正确排序。

G. Sorting 示例代码

G. Sorting

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	int n, m; cin >> n >> m;
	vector<int> ok(n + 1, 0);
	for(int i = 0; i < m; i ++) {
		int a, b; cin >> a >> b;
		if(b == a + 1) ok[a] = 1;
	}
	int ans = 0;
	for(int i = 1; i < n; i ++) ans += ok[i];
	cout << (ans == n - 1 ? "Yes" : "No") << '\n';

	return 0;
}

I. Knapsack Problem

把边反向，以为起点跑Dijkstra即可，距离为一个二元组，包含已用的背包数和当前背包所用的容量。

I. Knapsack Problem 示例代码

I. Knapsack Problem

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, V, S;
vector<pair<int, int>> G[N];

pair<int, int> dist[N];
bool vis[N];
inline void Dijkstra() {
	for(int i = 1; i <= n; i ++)
		dist[i] = {INF, 0};
	dist[S] = {1, 0};
	priority_queue<pair<pii, int>, vector<pair<pii, int>>, greater<pair<pii, int>>> Q;
	Q.push({dist[S], S});
	while(!Q.empty()) {
		int u = Q.top().second; Q.pop();
		if(vis[u]) continue; vis[u] = true;
		for(auto [v, w] : G[u]) {
			pii x = dist[u];
			if(x.second + w <= V) x.second += w;
			else x.first ++, x.second = w;
			if(x < dist[v]) {
				dist[v] = x, Q.push({dist[v], v});
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> m >> V >> S;
	for(int i = 0; i < m; i ++) {
		int a, b, c; cin >> a >> b >> c;
		if(c > V) continue;
		G[b].push_back({a, c});
		G[a].push_back({b, c});
	}
	Dijkstra();
	for(int i = 1; i <= n; i ++) 
		cout << (dist[i].first == INF ? -1 : dist[i].first) << " \n"[i == n];

	return 0;
}

J. Moving on the Plane

曼哈顿转切比雪夫，即将坐标变为，每次移动会变为，两维独立。

原作标下的曼哈顿距离等于新坐标下的切比雪夫距离，因此现在要求对于任意两点和，满足

也就是并且，两维独立，分别做后乘法原理即可。

现在的问题转化为，数轴上给定初始的个点，每个点可以走步，每步，要数最终这些点处于一个长度不超过的区间内的方案数。

枚举长度为的区间的起点并钦定左端点至少存在一个点，再算出每个点最终落在这个区间的方案数即可，总时间复杂度，其中是值域。

J. Moving on the Plane 示例代码

Moving on the Plane

#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 1e5 + 10, K = 15;
const int P = 998244353;
inline int Plus(int a, int b) {return a + b >= P ? a + b - P : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + P : a - b; }
inline int ksm(long long a, int b) {
	long long r = 1;
	for(; b; b >>= 1, a = a * a % P)
		if(b & 1) r = r * a % P;
	return r;
}
int fac[M], ifac[M];
inline int binom(int a, int b) {
	if(a >= b) return 1ll * fac[a] * ifac[b] % P * ifac[a - b] % P;
	else return 0;
}
int n, m, k, x[N], y[N];

inline int calc(vector<int> v) {
	int ans = 0;
	for(int l = -100000 - m; l <= 100000 + m; l ++) {
		int r = l + k;
		long long add = 1, sub = 1;
		for(int x : v) {
			int A = 0, B = 0;
			for(int p = l; p <= r; p ++) {
				int d = p - x;
				if(abs(d) > m || (m + d) % 2) continue;
				int y = binom(m, (m + d) / 2);
				A = Plus(A, y); if(p > l) B = Plus(B, y);
			}
			add = add * A % P, sub = sub * B % P;
		}
		ans = Plus(ans, add), ans = Minus(ans, sub);
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> m >> k;
	fac[0] = 1;
	for(int i = 1; i <= m; i ++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[m] = ksm(fac[m], P - 2);
	for(int i = m; i >= 1; i --) ifac[i - 1] = 1ll * ifac[i] * i % P;
	for(int i = 1; i <= n; i ++) {
		int a, b; cin >> a >> b;
		x[i] = a + b, y[i] = a - b;
	}
	vector<int> a(x + 1, x + n + 1), b(y + 1, y + n + 1);
	cout << 1ll * calc(a) * calc(b) % P << '\n';

	return 0;
}

K. Counting

设表示个点的无标号有根树中，恰有个点有恰个儿子的方案数，那么

拉反，由于，于是的复合逆为，拉反得到

推推式子，有

于是

接着大力展开，这个东西等于

熟知，于是答案即为

于是答案为

变换一下下标，化作

对于固定的，设，并设，其中，这是因为必须有，因此。

于是

对比待求式子，答案即为

答案不为的对只有个，枚举后每次NTT，时间复杂度。

注意当时会遇到的情况，所以需要将的情况特判掉。

K. Counting 示例代码

K. Counting

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> poly;

const int N = 1e6 + 10, P = 998244353;
inline int Plus(int a, int b) {return a + b >= P ? a + b - P : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + P : a - b; }
inline int ksm(long long a, int b) {
    long long r = 1;
    for(; b; b >>= 1, a = a * a % P)
        if(b & 1) r = r * a % P;
    return r;
}
int fac[N], ifac[N], inv[N], rev[N];

inline void make_rev(int n) {
    for(int i = 1; i < n; i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
}
inline void NTT(poly &A, int type) {
    static const int g = 3; // 原根
    int n = A.size();
    for(int i = 0; i < n; i ++)
        if(i < rev[i]) swap(A[i], A[rev[i]]);
    for(int h = 2; h <= n; h <<= 1) {
        long long step = ksm(g, (P - 1) / h);
        if(type == -1) step = ksm(step, P - 2);
        for(int i = 0; i < n; i += h) {
            long long mul = 1;
            for(int j = i; j < i + (h >> 1); j ++, mul = mul * step % P) {
                int u = A[j], v = A[j + (h >> 1)] * mul % P;
                A[j] = Plus(u, v), A[j + (h >> 1)] = Minus(u, v);
            }
        }
    }
    if(type == -1) {
        long long mul = ksm(n, P - 2);
        for(int i = 0; i < n; i ++)
            A[i] = A[i] * mul % P;
    }
}
poly operator * (poly A, poly B) {
    int h = 1, siz = (int)A.size() + (int)B.size() - 1;
    while(h < siz) h <<= 1;
    A.resize(h, 0), B.resize(h, 0);
    make_rev(h), NTT(A, 1), NTT(B, 1);
    for(int i = 0; i < h; i ++) A[i] = 1ll * A[i] * B[i] % P;
    NTT(A, -1); A.resize(siz); return A;
}
inline int binom(int a, int b) {
    return (a >= b ? 1ll * fac[a] * ifac[b] % P * ifac[a - b] % P : 0);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    fac[0] = 1;
    for(int i = 1; i < N; i ++) fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[N - 1] = ksm(fac[N - 1], P - 2);
    for(int i = N - 1; i >= 1; i --) ifac[i - 1] = 1ll * ifac[i] * i % P;
    for(int i = 1; i < N; i ++) inv[i] = 1ll * ifac[i] * fac[i - 1] % P;

    int n, q; cin >> n >> q;
    vector<vector<int>> ans(n + 1);
    for(int k = 0; k <= n; k ++) {
        int M = 0; while(M <= n && k * M <= n) M ++;
        M --; ans[k].resize(M + 1);
        poly A(M + 1), B(M + 1);
        for(int i = 0; i <= M; i ++) {
            A[i] = 1ll * fac[n] * ifac[n - i] % P * binom(2 * n - (k + 1) * i - 2, n - i - 1) % P;
            B[M - i] = (i & 1) ? Minus(0, ifac[i]) : ifac[i];
        }
        A = A * B;
        for(int m = 0; m <= M; m ++)
            ans[k][m] = 1ll * inv[n] * ifac[m] % P * A[M + m] % P;
    }
    if(n == 1) ans[0][1] = 1;
    while(q --) {
        int m, k; cin >> m >> k;
        if(m > n || k > n || 1ll * m * k > n) 
            cout << "0" << '\n';
        else 
            cout << ans[k][m] << '\n';
    }

    return 0;
}

M. Teleporter

首先最终的路径一定是：走树边、传送、走树边、传送交替进行。

考虑按升序求出每个答案，设表示此时到的最短距离，每次处理出之后只需要遍历每个传送边并更新即可多走一个传送边，这部分的复杂度是。考虑用树边更新最短路的方式，一定是先向上走若干步，再向下走到某个结点，更新最短路，因此可以分两步进行，这部分的时间复杂度为。

两部分合起来即可，总时间复杂度。

M. Teleporter 示例代码

M. Teleporter

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m; vector<pair<int, int>> G[N];

vector<array<int, 3>> up, down;
void dfs(int u, int fa) {
	for(auto [v, w] : G[u]) {
		if(v == fa) continue;
		down.push_back({u, v, w});
		dfs(v, u);
		up.push_back({v, u, w});
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> m;
	for(int i = 1; i < n; i ++) {
		int a, b, c; cin >> a >> b >> c;
		G[a].push_back({b, c}), G[b].push_back({a, c});
	}
	vector<pair<int, int>> tel(m);
	for(int i = 0; i < m; i ++) cin >> tel[i].first >> tel[i].second;
	dfs(1, 0);

	vector<long long> dp(n + 1, INF);
	dp[1] = 0;
	for(int k = 0; k <= n; k ++) {
		for(auto [u, v, w] : up)
			dp[v] = min(dp[v], dp[u] + w);
		for(auto [u, v, w] : down)
			dp[v] = min(dp[v], dp[u] + w);
		long long ans = 0;
		for(int i = 1; i <= n; i ++)
			ans += dp[i];
		cout << ans << '\n';
		vector<long long> new_dp = dp;
		for(auto [u, v] : tel) {
			new_dp[u] = min(new_dp[u], dp[v]);
			new_dp[v] = min(new_dp[v], dp[u]);
		}
		dp = new_dp;
	}

	return 0;
}