fsy's blog

燃峥嵘岁月，烈日终破云。

Educational Codeforces Round 94 (Rated for Div. 2) 题解

发表于 更新于
本文字数： 8.2k 阅读时长 ≈ 7 分钟

This contest has been weird-order-forces, greedyforces, and WA on Pretest 2-forces.

F、G 待填坑

【A】 String Similarity

注意到 $S[n]$ 一定会在每个子串中出现。

全部输出 $S[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>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 120;
int t, n;
char s[maxN]; 
int main() {
	read(t);
	while(t--) {
		read(n);
		scanf("%s", s + 1);
		_rep(i, 1, n) putchar(s[n]);
		putchar('\n');
	}
	return 0;
}

【B】 RPG Protagonist

先考虑只有一个人的情况，那肯定是优先选重量小的，如果空间还够，再选重量大的。

再考虑两个人的情况，可以枚举第一个人选的剑的个数，那第一个人最多能选的战斧数量也可以计算出来。然后就退化成了一个人的情况。

时间复杂度 $\mathcal{O}(\sum cnt_s)$。

代码：

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
#include <bits/stdc++.h>
#define int long long
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
int t, p, f, cs, cw, s, w;
signed main() {
	read(t);
	while(t--) {
		read(p, f, cs, cw, s, w);
		int max_ans = 0;
		_rep(i, 0, cs) {
			int ans = 0;
			if(1ll * i * s > 1ll * p) continue;
			ans += i;
			int waraxes = std::min((p - 1ll * i * s) / w, 1ll * cw);
			ans += waraxes;
			if(s > w) {
				LL q = std::min(f / w, cw - waraxes);
				ans += q;
				if(f / w >= cw - waraxes) {
					LL remain = f - 1ll * w * (cw - waraxes);
					ans += std::min(remain / s, 1ll * cs - i);;
				}
				max_ans = std::max(max_ans, ans);
			} else {
				LL q = std::min(f / s, cs - i);
				ans += q;
				if(f / s >= cs - i) {
					LL remain = f - 1ll * s * (cs - i);
					ans += std::min(remain / w, 1ll * cw - waraxes);
				}
				max_ans = std::max(max_ans, ans);
			}
		} 
		std::cout << max_ans << "\n";
	}
	return 0;
}

【C】 Binary String Reconstruction

C 题 比 B 题 简 单.jpg

首先，我们可以确定原字符串中 0 的位置：将给定字符串扫一遍，遇到第 $i$ 位为 0 就将原字符串中 $i-x$，$i+x$ 位更新为 0。

然后检查 1，如果有一个 1 位置两边都已经赋值成了 0，那么无解。

如果有解就把剩下空的位置赋值成 1 即可，正确性显然。

时间复杂度 $\mathcal{O}(\sum |s|)$。

代码：

代码写的烦了一点….

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
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10;
int t, n;
char str[maxN], c[maxN];
int x;
int main() {
	read(t);
	while(t--) {
		scanf("%s", str + 1); read(x);
		n = strlen(str + 1);
		_rep(i, 1, n) c[i] = 'Z';
		_rep(i, 1, n) {
			if(str[i] == '0') {
				if(i - x >= 1) c[i - x] = '-';
				if(i + x <= n) c[i + x] = '-';
			}
		}
		int flg = 1;
		_rep(i, 1, n) {
			if(str[i] == '1') {
				if(i - x >= 1 && c[i - x] != '-') {
					c[i - x] = '+';
				} else if(i + x <= n && c[i + x] != '-') {
					c[i + x] = '+';
				} else {
					flg = 0; break;
				}
			}
		}
		if(flg == 0) puts("-1");
		else {
			_rep(i, 1, n) {
				putchar(c[i] == '-' ? '0' : '1');
			}
			putchar('\n');
		}
	}
	return 0;
}

【D】 Zigzags

考虑枚举 $i, k$，问题就转化为有多少对 $(a_j, a_l)$ 满足 $j \in [i+1,k-1], l \in [k+1, n], a_j=a_l$。

如果暴力枚举 $a_j$，则单次复杂度为 $\mathcal{O}(n^3)$，无法承受。

于是我们可以考虑类似 滑动窗口 的思想：固定 $i$，滑动 $k$ 的同时更新贡献。由于每次滑动只会让一个元素进入 $[i+1,k-1]$，一个元素离开 $[k+1,n]$，每次贡献的差是相当好维护的。

单次时间复杂度 $\mathcal{O}(n^2)$。

代码：

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>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 3002;
int t, n, a[maxN], buk[maxN][maxN];
int main() {
	read(t);
	while(t--) {
		read(n);
		_rep(i, 1, n) read(a[i]);
		memset(buk, 0, sizeof(buk));
		_rep(i, 1, n) buk[i][a[i]]++;
		_rep(j, 1, 3000) {
			_rep(i, 1, n) buk[i][j] = buk[i][j] + buk[i - 1][j];
		}
		LL ans = 0;
		_rep(i, 1, n - 3) {
			LL contrib = 0;
		//	contrib = 1ll * (buk[n][a[i + 1]] - buk[i + 2][a[i + 1]]);
			_rep(k, i + 2, n - 1) {
				contrib = contrib + 1ll * (buk[n][a[k - 1]] - buk[k - 1][a[k - 1]]);
				contrib = contrib - 1ll * (buk[k - 1][a[k]] - buk[i][a[k]]);
				if(a[i] != a[k]) continue;
				ans = ans + 1ll * contrib;
				//std::cout << i << " " << k << " " << ans << " " << contrib << "\n";
			}
		}
		writesp(ans, '\n');
	}
	return 0;
}

【E】 Clear the Multiset

震惊！CF 竟然出 CF 原题！

首先可以证明：我们可以随便调整操作的顺序，答案是不会变的。

于是我们可以考虑先做第一种操作。

先找到 $[1,n]$ 区间内最小的数，将 $[1,n]$ 区间内所有数都减去这个最小的数。于是就出现了 $0$，于是这段区间分裂成了两个小区间，分治处理即可。

再考虑第二种操作，答案明显等于区间中的非零数。

时间复杂度 $\mathcal{O}(n \log n)$，最坏时间复杂度 $\mathcal{O}(n^2)$，可以通过此题。

代码：

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
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
	x = 0; T f = (T) 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
	for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...);
}
template <typename T>
inline void write(T x) {
	if(x < 0) {x = -x; putchar('-');}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 5010;
int n, a[maxN];
int dc(int l, int r) {
//	std::cout << l << " " << r << std::endl;
	if(l == r) return (a[l] != 0);
	if(l > r) return 0;
	int minn = 1e9 + 7, des = l;
	_rep(i, l, r) {
		if(a[i] < minn) {
			minn = a[i]; des = i;
		}
	}
	_rep(i, l, r) a[i] -= minn;
	return std::min(r - l + 1, minn + dc(l, des - 1) + dc(des + 1, r)); 
}
int main() {
	read(n);
	_rep(i, 1, n) read(a[i]);
	int ans = 0; 
	std::cout << dc(1, n) << std::endl; 
	return 0;
}

【F】 x-prime Substrings

首先需要注意到一个性质：x-prime Substring 的数量与长度和都不大。

在 $x=19$ 时，x-prime Substring 的数量达到最劣，此时共有 $2399$ 个 19-prime Substring，总长度为 $13739$。

于是我们可以生成出所有 x-prime Substring 并插入 AC 自动机中。则问题转化为：最少要删多少个字符，才能使这个字符串中不存在 x-prime Substring？

考虑一个 naive 的动态规划：设 $dp_{i,j}$ 为

1

【G】 Mercenaries