CUC2024区域赛重现#8

The 2022 ICPC Asia Nanjing Regional Contest

I. Perfect Palindrome (7)

1
2
3
4
5
6
7
8
9
10
void solve() {
    string s;
    cin >> s;

    array<int, 26> mp{};
    for (auto& c : s) {
        mp[c - 'a']++;
    }
    cout << s.size() - *max_element(mp.begin(), mp.end()) << '\n';
}

G. Inscryption (70 + 60)

维护一个序列，序列里一开始只有一个 11。处理 nn 个事件，事件可能有以下三种：

  • 往序列里添加一个 1。
  • 从序列里拿出两个数，加起来再放回去。
  • 从以上两种事件中自由选一个。

在每次都能从序列里拿出两个数的前提下，求序列平均值的最大值。

当时写的二分：

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
void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

    map<int, int> cnt;
	for (int i = 0; i < n; ++i) {
		++cnt[a[i]];
		if (cnt[-1] > cnt[0] + cnt[1]) {
			printf("-1\n");
			return;
		}
	}

	auto check = [&](int x) {
		int cnt11 = 0, cnt_11 = 0;
		for (int i = 0; i < n; ++i) {
			if (a[i] == 1) cnt11++;
			else if (a[i] == -1) cnt_11++;
			else if (x) {
				cnt11++;
				x--;
			} else {
				cnt_11++;
			}
			if (cnt11 < cnt_11) return 1; // ++1
		}
		return 0; // --1
	};


	int l = 0, r = cnt[0];
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}

	int p = 1 + cnt[1] + l;
	int q = 1 + (cnt[1] + l) - (cnt[-1] + (cnt[0] - l));
	int d = gcd(p, q);
	printf("%d %d\n", p / d, q / d);
}

本题的正解是反悔贪心：

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
void solve() {
    int n;
    cin >> n;

    int p = 1, q = 1, cnt = 0, ok = 1;
	for (int i = 0; i < n; ++i) {
		int x;
        cin >> x;

        if (x == 1) {
            p++, q++;
        } else if (x == -1) {
            if (q > 1) q--;
            else if (cnt) cnt--, p++, q++;
            else ok = 0;
        } else {
            if (q > 1) cnt++, q--;
            else p++, q++;
        }
    }

    if (!ok) cout << -1 << '\n';
    else {
        int d = gcd(p, q);
        cout << p / d << ' ' << q / d << '\n';
    }
}

M. Drain the Water Tank (158 + 40)

问多边形容器，至少打开几个顶点使水排空。「去重」后分情况讨论。

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
using T = int;
const double eps = 1e-9, pi = acos(-1.0);
int sign(T x) {
    return (fabs(x) <= eps) ? 0 : (x < 0 ? -1 : 1);
}

struct P {
    T x, y;
    P(T X = 0, T Y = 0) { x = X, y = Y; }
    P operator+(P o) { return P(x + o.x, y + o.y); }
    P operator-(P o) { return P(x - o.x, y - o.y); }
    T operator*(P o) { return x * o.y - y * o.x; }
};

T Area(P a, P b, P c) {
    return (b - a) * (c - a);
}

void solve() {
 	int n;
    cin >> n;

    vector<P> pt(n);
	for (int i = 0; i < n; ++i) {
		cin >> pt[i].x >> pt[i].y;
	}

    #define l(i) (i-1+n) % n
    #define r(i) (i+1) % n

    vector<P> p;
	for (int i = 0; i < n; ++i) {
		if (pt[i].y != pt[l(i)].y || pt[i].y != pt[r(i)].y) {
            p.push_back(pt[i]);
		}
	}
	n = p.size();

    int ans = 0;

	for (int i = 0; i < n; ++i) {
		if (Area(p[l(i)], p[i], p[r(i)]) > 0) {
			if (p[i].y < p[r(i)].y && p[i].y < p[l(i)].y) {
				++ans;
			}
            else if (p[i].y == p[r(i)].y && p[r(i)].y < p[r(r(i))].y && p[i].y < p[l(i)].y && Area(p[i], p[r(i)], p[r(r(i))]) > 0) {
				++ans;
			}
		}
	}

	cout << ans << '\n';
}

F. Triangles (250 + 340)

经典。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>

struct TRI {
	int x1, y1, x2, y2, x3, y3;
};

void print(TRI t) {
	printf("%d %d %d %d %d %d\n", t.x1, t.y1, t.x2, t.y2, t.x3, t.y3);
}

void solve(TRI t, int n) {
	if (n == 0) {
		print(t);
		return;
	}
	TRI a = { t.x1,t.y1,   (t.x1 + t.x2) / 2,(t.y1 + t.y2) / 2,    (t.x1 + t.x3) / 2,(t.y1 + t.y3) / 2 };
	TRI b = { t.x2,t.y2,   (t.x2 + t.x3) / 2,(t.y2 + t.y3) / 2,    (t.x2 + t.x1) / 2,(t.y2 + t.y1) / 2 };
	TRI c = { t.x3,t.y3,   (t.x3 + t.x1) / 2,(t.y3 + t.y1) / 2,    (t.x3 + t.x2) / 2,(t.y3 + t.y2) / 2 };
	TRI d = { (t.x3 + t.x1) / 2,(t.y3 + t.y1) / 2,    (t.x3 + t.x2) / 2,(t.y3 + t.y2) / 2,  (t.x2 + t.x1) / 2,(t.y2 + t.y1) / 2 };

	print(b);
	print(c);
	print(d);
	solve(a, n - 3);
}

int main() {
	int n;
	scanf("%d", &n);
	if (n < 8) {
		printf("No\n");
		return 0;
	}

	printf("Yes\n");
	if (n % 3 == 2) {
		TRI tri[] = {
			{ 0,0,  450000000,800000000,  0,1000000000 },
			{ 0,0,  450000000,800000000,  500000000,0 },
			{ 0,1000000000,  500000000,1000000000,  450000000,800000000 },
			{ 500000000,0,  450000000,800000000,  550000000,800000000 },
			{ 500000000,0,  1000000000,0,  550000000,800000000 },
			{ 1000000000,1000000000,  1000000000,0,  550000000,800000000 },
			{ 1000000000,1000000000,  500000000,1000000000,  550000000,800000000 },
			{  550000000,800000000, 500000000,1000000000,  450000000,800000000  },
		};

		if (n >= 44) {
			for (int i = 3; i < 8; ++i) {
				print(tri[i]);
			}
			solve(tri[0], 12);
			solve(tri[1], 12);
			solve(tri[2], n - 12 - 12 - 8);
		} else if (n >= 32) {
			for (int i = 2; i < 8; ++i) {
				print(tri[i]);
			}
			solve(tri[0], 12);
			solve(tri[1], n - 20);
		} else {
			for (int i = 1; i < 8; ++i) {
				print(tri[i]);
			}
			solve(tri[0], n - 8);

		}
	}
	if (n % 3 == 0) {
		TRI tri[] = {
			{         0, 1000000000,  1000000000, 1000000000,  850000000, 200000000  },
			{         0, 1000000000,    850000000, 200000000,   0,0 },
			{  784557000,         0,    765000000, 180000000,   0,0 },
			{ 1000000000, 1000000000,  1000000000, 176901000,   850000000, 200000000  },
			{  850000000, 200000000,   1000000000, 176901000,   865600000, 125700000  },
			{  865600000, 125700000,   1000000000, 176901000,  1000000000, 0  },
			{  865600000, 125700000,    784557000,         0,  1000000000, 0  },
			{  865600000, 125700000,    784557000,         0,   765000000, 180000000 },
			{  865600000, 125700000,    850000000, 200000000,   765000000, 180000000 },
		};

		if (n >= 45) {
			for (int i = 4; i < 9; ++i) {
				print(tri[i]);
			}
			solve(tri[0], 12);
			solve(tri[1], 12);
			solve(tri[2], 6);
			solve(tri[3], n - 12 - 6 - 12 - 9);
		} else if (n >= 33) {
			for (int i = 2; i < 9; ++i) {
				print(tri[i]);
			}
			solve(tri[0], 12);
			solve(tri[1], n - 21);
		} else {
			for (int i = 1; i < 9; ++i) {
				print(tri[i]);
			}
			solve(tri[0], n - 9);
		}

	}
	if (n % 3 == 1) {
		TRI tri[] = {
			{   1000000000, 1000000000,  500000000, 800000000,  1000000000, 0  },
			{            0, 1000000000,  500000000, 800000000,  0,0  },
			{            0,          0,  500000000, 800000000,  1000000000, 0  },
			{            0, 1000000000,  420000000,1000000000,   400000000, 840000000  },
			{    500000000,  900000000,  420000000,1000000000,   400000000, 840000000  },
			{    500000000,  900000000,  420000000,1000000000,   580000000,1000000000  },
			{    500000000,  900000000,  600000000, 840000000,   580000000,1000000000  },
			{    500000000,  900000000,  600000000, 840000000,   500000000, 800000000  },
			{    500000000,  900000000,  400000000, 840000000,   500000000, 800000000  },
			{   1000000000, 1000000000,  600000000, 840000000,   580000000,1000000000  },
		};

		if (n >= 34) {
			for (int i = 3; i < 10; ++i) {
				print(tri[i]);
			}
			solve(tri[0], 12);
			solve(tri[1], 12);
			solve(tri[2], n - 12 - 12 - 10);
		} else {
			for (int i = 1; i < 10; ++i) {
				print(tri[i]);
			}
			solve(tri[0], n - 10);
		}
	}
	
	return 0;
}

A. Stop, Yesterday Please No More (UPSOLVE)

做个二维前缀和，不知道当时为什么不会做。

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
int n, m, k;
cin >> n >> m >> k;

string s;
cin >> s;

int x = 0, y = 0, D = 0, U = n, L = 0, R = m;
for (auto c : s) {
	if (c == 'D') y++;
	if (c == 'U') y--;
	if (c == 'L') x++;
	if (c == 'R') x--;
	D = max(D, y);
	U = min(U, n + y);
	L = max(L, x);
	R = min(R, m + x);
}

if (D >= U || L >= R) {
	cout << (k ? 0 : n * m) << '\n';

} else {
	k = (R - L) * (U - D) - k;  // died

	vector a(2 * m, vector<int>(2 * n));
	int x = m, y = n;
	a[x][y] = 1;
	for (auto c : s) {
		if (c == 'D') y++;
		if (c == 'U') y--;
		if (c == 'L') x++;
		if (c == 'R') x--;
		a[x][y] = 1;
	}

	// 二维前缀和
	vector s(2 * m + 1, vector<int>(2 * n + 1));
	for (int x = 0; x < 2 * m; ++x) {
		for (int y = 0; y < 2 * n; ++y) {
			s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y];
		}
	}
	auto get = [&](int x1, int y1, int x2, int y2) {
		return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1];
	};

	int ans = 0;
	for (int x = 0; x < m; ++x) {
		for (int y = 0; y < n; ++y) {
			if (get(m - x + L, n - y + D, m - x + R, n - y + U) == k) {
				ans++;
			}
		}
	}
	cout << ans << '\n';
}

D. Chat Program

完美满足那三个条件，故二分答案化 01 串。然后做个滑动窗口，每个11 只能是11，00 有可能先变成11 再回到00，找到这个分界，然后统计每一秒的情况，只要某一秒11 的数量⩾k\geqslant k 即可。

分界需要算一下，设初始为第00 秒，窗口在[0,m)[0,m)，于是在第tt 秒末，窗口在[t,m+t)[t,m+t)，am+ta_{m+t} 将增加c+(m−1)dc+(m-1)d，设在第t+st+s 秒末，am+t=am+t+(c+(m−1−s)d)<xa_{m+t}=a_{m+t}+(c+(m-1-s)d)<x，可以解出ss。

细节很多，WA 了nn 次，给两个 Hack 自己的数据：

6 2 2 20 50
0 0 0 0 0 0
expected: 20
wrong answer: 69		6 2 3 100 1
0 0 0 0 0 0
expected: 101
wrong answer: RE
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
void eachT() {
	int n, k, m, c, d;
	cin >> n >> k >> m >> c >> d;

	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	auto check = [&](ll x) {
		vector<int> b(n);
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			if (a[i] < x && a[i] + (c + 1ll * min(i, m - 1) * d) >= x) {
				++(i < m ? sum : b[i - m]);
				--b[i - (d ? max(0ll, (x - a[i] - c + d - 1) / d) : 0)];  // 这里要向上取整 而且不能小于0
			}
			else if (a[i] >= x) {
				sum++;
			}
		}
		for (int i = 0; i < n; ++i) {
			if (sum >= k) return true;
			sum += b[i];
		}
		return false;
	};
	
	ll l = 0, r = 1e15;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (!check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r - 1 << "\n";
}