2022-2023 ICPC Asia Nanjing Regional

Summary

比赛地址 ：Codeforces Gym 104128

官方题解 ：SUA Wiki

还没补完：CEFHKL

难度：IDGM - ABEJ - CHKL + F(??)

A - Stop, Yesterday Please No More

B - Ropeway

C - Fabulous Fungus Frenzy

D - Chat Program

给定一个长度为 \(n\) 的整数序列 \(a_1, a_2, · · · , a_n\) 和另外四个整数 \(k,m,c,d\) ，最大化序列中第 \(k\) 大的值。

操作至多一次：选择一个长度恰为 \(m\) 的区间，并将一个长度为 \(m\)，首项为 \(c\)，公差为 \(d\) 的等差序列加到对应位置上。

二分答案第 \(k\) 大值为 \(x\) ，那么每个位置如果要修改为 \(\ge x\) ，合法的操作起点一定在一个区间范围内。

所以找出能让最多的数字合法的位置开始操作即可，区间加 \(1\) 最后求最大值，差分即可，复杂度 \(O(n\log (a+c+md))\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007

int n, k, m, dlt[N];

ll c, d, a[N];

inline bool valid(ll x) {
	for (int i = 1; i <= n; ++i) dlt[i] = 0;
	auto add = [&](ll l, ll r) {
		l = max(l, 1ll);
		r = min(r, n - m + 1ll);
		if (r < l) return;
		++dlt[l];
		--dlt[r + 1];
	};
	for (int i = 1; i <= n; ++i) {
		if (a[i] >= x) ++dlt[1];
		else {
			if (x - a[i] <= c) add(i - m + 1, i);
			else if (d != 0) add(i - m + 1, i - ((x - a[i] - c + d - 1) / d));
		}
	}
	int mx = 0;
	for (int i = 1; i <= n; ++i) {
		dlt[i] += dlt[i - 1];
		mx = max(mx, dlt[i]);
	}
	return mx >= k;
}

int main() {
	n = rd(), k = rd(), m = rd();
	c = rd(), d = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	ll l = 0, r = 1e18;
	while (l < r) {
		ll mid = (l + r + 1) / 2;
		valid(mid) ? l = mid : r = mid - 1;
	}
	printf("%lld\n", l);
	return 0;
}

E - Color the Tree

F - Triangles

G - Inscryption

最后答案就是加入次数 / 剩余个数，显然减少剩余个数优先级更高。

因此能减就减，此外维护可反悔的机会次数，不够减少又必须减少，即需要反悔的时候反悔即可，复杂度 \(O(n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

inline void work() {
	bool fl = false;
	int n = rd(), cnt = 1, sum = 1, reg = 0;
	for (int i = 1; i <= n; ++i) {
		int x = rd();
		if (x == 1) {++cnt; ++sum;}
		else if (x == -1) {
			--cnt; 
			if (!cnt) {
				if (reg) {--reg; cnt += 2; sum += 1;}
				else fl = true;
			}
		} else {
			if (cnt > 1) {--cnt; ++reg;}
			else {++cnt; ++sum;}
		}
	}
	if (fl) {puts("-1"); return;}
	int g = gcd(sum, cnt);
	printf("%d %d\n", sum / g, cnt / g);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

（赛时脑子抽了还写了个dp维护后缀允许的最多减法次数。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1000007

int f[N], a[N];

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

inline void work() {
	int n = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	f[n + 1] = 0;
	for (int i = n; i; --i) 
		if (a[i] == 0) f[i] = f[i + 1];
		else if (a[i] == -1) f[i] = f[i + 1] + 1;
		else f[i] = max(0, f[i + 1] - 1);
	int nw = 1, sum = 1;
	for (int i = 1; i <= n; ++i)
		if (a[i] == -1) {--nw; if (!nw) {puts("-1"); return;}}
		else if (a[i] == 1) {++nw; ++sum;}
		else {
			if (nw <= f[i] + 1) {++nw; ++sum;}
			else --nw;
		}
	int g = gcd(nw, sum);
	printf("%d %d\n", sum / g, nw / g);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

H - Factories Once More

I - Perfect Palindrome

由定义所有字符必须都相同，保留出现次数最多的字符，复杂度 \(O(n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

int cnt[27];

char s[100007];

inline void work() {
	scanf("%s", s + 1);
	for (int i = strlen(s + 1); i; --i) ++cnt[s[i] - 'a'];
	int ans = 0;
	for (int i = 0; i < 26; ++i) {
		ans = max(ans, cnt[i]); cnt[i] = 0;
	}
	printf("%d\n", (int)strlen(s + 1) - ans);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

*J - Perfect Matching

给定 \(n\) 个数 \(a_1, a_2, \dots, a_n\) 如果 \(|a_i-a_j| =|i-j|\) 那么 \(i\) 和 \(j\) 就可以匹配。

每个点只能用来匹配一次，问是否存在完美匹配（全部用上）。

整理绝对值得到 \(a_i+i=a_j+j\) 或 \(a_i-i=a_j-j\) ，那么可以构造一个二分图。

左侧的点代表所有的 \(a_i+i\) ，右侧代表 \(a_i-i\) ，如果两个位置某一侧共用同一个点即可匹配。

因此就是一个边匹配，也就是线图是否存在完美匹配。线图的最大匹配算法是经典的，复杂度 \(O(n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr first
#define sc second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define lowbit(x)    ((x) & -(x))
#define all(x)       (x).begin(), (x).end()
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline T rd() {
	T x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007

int tot, hd[N], a[N];

struct edge {int to, nxt;} e[N];

inline void add(int u, int v) {
	e[++tot] = {v, hd[u]}; hd[u] = tot;
	e[++tot] = {u, hd[v]}; hd[v] = tot;
}

bool vis[N], used[N];

vector<pii> ans;

void dfs(int u, int fa) {
	vis[u] = true;
	int faid = 0;
	for (int i = hd[u], v; i; i = e[i].nxt)
		if (!vis[v = e[i].to]) dfs(v, u); 
		else if (v == fa) faid = (i >> 1);
	int lst = 0;
	for (int i = hd[u], v, id; i; i = e[i].nxt)
		if ((v = e[i].to) != fa && !used[id = (i >> 1)]) {
			if (lst) {
				used[lst] = used[id] = true;
				ans.eb(lst, id); lst = 0;
			} else lst = id; 
		} 
	if (lst && faid) {
		used[lst] = used[faid] = true;
		ans.eb(lst, faid);
	}
}

vector<int> L, R;

inline void work() {

	int m = rd();
	L.clear(); R.clear(); ans.clear();
	rep (i, 1, m) {a[i] = rd(); L.pb(a[i] + i); R.pb(a[i] - i);}
	sort(all(L)); L.erase(unique(all(L)), L.end());
	sort(all(R)); R.erase(unique(all(R)), R.end());
	auto lid = [&](int x) {return lower_bound(all(L), x) - L.begin() + 1;};
	auto rid = [&](int x) {return lower_bound(all(R), x) - R.begin() + 1 + L.size();};

	tot = 1;
	int n = L.size() + R.size();
	rep(i, 1, n) {hd[i] = 0; vis[i] = false;}
	rep(i, 1, m) {used[i] = false; add(lid(a[i] + i), rid(a[i] - i));}
	rep(i, 1, n) if (!vis[i]) dfs(i, i);
	if (ans.size() * 2 != m) {puts("No"); return;}
	puts("Yes");
	for (auto [x, y] : ans) printf("%d %d\n", x, y);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

K - NaN in a Heap

L - Proposition Composition

*M - Drain the Water Tank

给一个简单多边形水箱，问把内部的水全部放干最少需要在多少个顶点开口（重力沿 \(y\) 轴向下）。

显然每个下表面最低处都要开一个口（即两侧都向上）。

因此就需要找出来左右都比当前高的点（包括一段平台），然后判断是否是水箱的下表面。

  • 如果是一个单点，可以用两个向量的叉积符号判断。
  • 如果是一段平台，只需用平台内点的方向即可（给出点按逆时针，因此下表面应当从左到右出现）

复杂度 \(O(n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 

inline T rd() {
	T x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define letp const P // P for Point

struct P {
    T x, y;
    P (T x = 0, T y = 0) : x(x), y(y) {}
    P operator - (letp &p) const {return {x - p.x, y - p.y};}
    T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
    T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross
    // left(counterclockwise) = 1 | on = 0 | right(clockwise) = -1
    int ori(letp &p) const {T t = (*this) ^ p; return (t > 0) - (t < 0);}
};

int main() {
	int n = rd();
	vector<P> p(n);
	for (int i = 0; i < n; ++i) {p[i].x = rd(); p[i].y = rd();}
	auto nxt = [&](const int i) {return i == p.size() - 1 ? 0 : i + 1;};
    auto pre = [&](const int i) {return i == 0 ? p.size() - 1 : i - 1;};
    
    int l, r, L = 0, ans = 0;
    for (; p[L].y == p[pre(L)].y; L = pre(L));
    l = r = L;
	do {
		while (p[r].y == p[nxt(r)].y) r = nxt(r);
		if (p[pre(l)].y > p[l].y && p[nxt(r)].y > p[r].y) {
			if (l == r) ans += ((p[l] - p[pre(l)]).ori(p[nxt(l)] - p[l]) > 0);
			else ans += (p[nxt(l)].x > p[l].x); 
		}
		l = r = nxt(r);
	} while (l != L);
	printf("%d\n", ans);
	return 0;
}

为什么数据范围要给可以想 \(n^2\) 的做法呢。。。

当时一眼以为判断上下表面要用点在多边形内，复杂度恰好是 \(n^2\) ，各种爆精度挂了 \(4\) 发才过。。。