「Codeforces」Round 556 (Div.2)【题解】

简要题解

A. Stock Arbitraging

贪心,用 max{b}\max \{ b \} 来换 min{s}\min \{ s \} 或者不换。

B. Tiling Challenge

贪心,从上到下枚举中心,能填就填。

C. Prefix Sum Primes

题目大意:给你一个长度为 nn 且只包含 1122 的序列,你需要重排这个序列,使得有尽可能多的前缀和是质数,输出方案。保证 n2×105n \leqslant 2 \times 10^5

贪心,从小到大枚举质数,能选就选,先放 22 后放 11

D. Three Religions

题目大意:给你一个长度为 nn 的母串,另外还有不断变化的三个字符串 s1,s2,s3s_1, s_2, s_3。判断 s1,s2,s3s_1, s_2, s_3 是否可以表示为母串的不相交子序列,可以参考下图。有 qq 个操作,每次会在 sis_i 的末尾加上字符 cc 或者删除 sis_i 的末尾状态 (i{1,2,3})(i \in \{ 1, 2, 3 \})。保证 n105,n \leqslant 10^5, q1000q \leqslant 1000,任意时刻 s1,s2,s3250\lvert s_1 \rvert, \lvert s_2 \rvert, \lvert s_3 \rvert \leqslant 250

示意图

f(i,j,k)f(i, j, k) 表示匹配到 s1s_1 的第 ii 个位置、s2s_2 的第 jj 个位置、s3s_3 的第 kk 个位置所用的母串的最短前缀的长度。为了实现 O(1)O(1) 转移,还需要预处理 nxt(i,c)\text{nxt}(i, c) 表示第 ii 个位置后的第一个字符 cc 所在的位置,枚举最后一个字符转移。

每次询问只新加状态,或者将旧状态置为 ++\infty,时间复杂度为 O(q×2502)O(q \times 250^2)

E. Tree Generator™ ()(\star)

题目大意:给你一个括号序列,表示一棵 nn 个结点的树。有 qq 个操作,每次交换括号序列的两个元素,并求出树的直径的长度。保证 n,q105n, q \leqslant 10^5 且任意时刻括号序列都对应一棵合法的树。

这里首先给出一个关于括号序列的结论,证明也非常显然:

两个点的距离 ((边权为 1)1) 是括号序列中对应的区间中,匹配后剩下的括号的个数 ((一定是 )))"+ (((("``)) \cdots )" +\ ``(( \cdots ((" 的形式))

设左括号权值为 11,右括号权值为 1-1,那么直径就是将这一段分成两段,等于 ``后面的权值和减前面的权值和"" 的最大值。

dd 值为这一段的最大值,那么需要在线段树上维护最大前缀和,最小后缀和、最大前 (()) 缀的 dd 值、整体 dd 值、权值和、答案。本题细节较多,具体实现请参考代码。

代码实现

A. Stock Arbitraging

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int n, m, r, s[35], b[35];

int main() {
scanf("%d %d %d", &n, &m, &r);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
}
sort(s + 1, s + n + 1);
sort(b + 1, b + m + 1);
if (s[1] < b[m]) printf("%d\n", r / s[1] * b[m] + r % s[1]);
else printf("%d\n", r);
return 0;
}

B. Tiling Challenge

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;
int n;
char s[maxn][maxn];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
}
for (int i = 2; i < n; i++) {
for (int j = 2; j < n; j++) {
if (s[i][j] == '.' && s[i - 1][j] == '.' && s[i + 1][j] == '.'
&& s[i][j - 1] == '.' && s[i][j + 1] == '.') {
s[i][j] = s[i - 1][j] = s[i + 1][j] = s[i][j - 1] = s[i][j + 1] = '#';
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i][j] == '.') printf("NO\n"), exit(0);
}
}
printf("YES\n");
return 0;
}

C. Prefix Sum Primes

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, cnt1, cnt2;
bool p[maxn << 1];
vector<int> V, ans;

int main() {
scanf("%d", &n);
for (int i = 2; i <= 400000; i++) if (!p[i]) {
for (int j = i + i; j <= 400000; j += i) p[j] = 1;
V.push_back(i);
}
for (int i = 1, a; i <= n; i++) {
scanf("%d", &a);
if (a == 1) cnt1++;
else cnt2++;
}
int lst = 0;
for (int x : V) {
int d = x - lst, mn = min(d >> 1, cnt2);
cnt2 -= mn, d -= (mn << 1);
while (mn--) ans.push_back(2);
if (cnt1 < d) break;
cnt1 -= d;
while (d--) ans.push_back(1);
lst = x;
}
while (cnt1--) ans.push_back(1);
while (cnt2--) ans.push_back(2);
for (int x : ans) printf("%d ", x);
return 0;
}

D. Three Religions

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010, maxm = 255;
int n, q, nxt[maxn][26];
int l1, l2, l3, f[maxm][maxm][maxm];
char op[2], c[2], s[maxn], s1[maxm], s2[maxm], s3[maxm];
void chk(int &x, int y) { if (x > y) x = y; }

int main() {
scanf("%d %d %s", &n, &q, s + 1);
memset(nxt, 0x3f, sizeof(nxt));
for (int i = n; i; i--) {
for (int j = 0; j < 26; j++) {
if (s[i] == j + 'a') nxt[i][j] = i;
else nxt[i][j] = nxt[i + 1][j];
}
}
memset(f, 0x3f, sizeof(f)), f[0][0][0] = 0;
for (int i = 1, j; i <= q; i++) {
scanf("%s %d", op, &j);
if (op[0] == '+') {
scanf("%s", c);
if (j == 1) {
s1[++l1] = c[0];
for (int j = 0; j <= l2; j++) {
for (int k = 0; k <= l3; k++) {
if (f[l1 - 1][j][k] < 1e9) chk(f[l1][j][k], nxt[f[l1 - 1][j][k] + 1][c[0] - 'a']);
if (j && f[l1][j - 1][k] < 1e9) chk(f[l1][j][k], nxt[f[l1][j - 1][k] + 1][s2[j] - 'a']);
if (k && f[l1][j][k - 1] < 1e9) chk(f[l1][j][k], nxt[f[l1][j][k - 1] + 1][s3[k] - 'a']);
}
}
}
if (j == 2) {
s2[++l2] = c[0];
for (int j = 0; j <= l1; j++) {
for (int k = 0; k <= l3; k++) {
if (f[j][l2 - 1][k] < 1e9) chk(f[j][l2][k], nxt[f[j][l2 - 1][k] + 1][c[0] - 'a']);
if (j && f[j - 1][l2][k] < 1e9) chk(f[j][l2][k], nxt[f[j - 1][l2][k] + 1][s1[j] - 'a']);
if (k && f[j][l2][k - 1] < 1e9) chk(f[j][l2][k], nxt[f[j][l2][k - 1] + 1][s3[k] - 'a']);
}
}
}
if (j == 3) {
s3[++l3] = c[0];
for (int j = 0; j <= l1; j++) {
for (int k = 0; k <= l2; k++) {
if (f[j][k][l3 - 1] < 1e9) chk(f[j][k][l3], nxt[f[j][k][l3 - 1] + 1][c[0] - 'a']);
if (j && f[j - 1][k][l3] < 1e9) chk(f[j][k][l3], nxt[f[j - 1][k][l3] + 1][s1[j] - 'a']);
if (k && f[j][k - 1][l3] < 1e9) chk(f[j][k][l3], nxt[f[j][k - 1][l3] + 1][s2[k] - 'a']);
}
}
}
} else {
if (j == 1) {
for (int j = 0; j <= l2; j++) {
for (int k = 0; k <= l3; k++) {
f[l1][j][k] = 0x3f3f3f3f;
}
}
l1--;
}
if (j == 2) {
for (int j = 0; j <= l1; j++) {
for (int k = 0; k <= l3; k++) {
f[j][l2][k] = 0x3f3f3f3f;
}
}
l2--;
}
if (j == 3) {
for (int j = 0; j <= l1; j++) {
for (int k = 0; k <= l2; k++) {
f[j][k][l3] = 0x3f3f3f3f;
}
}
l3--;
}
}
printf("%s\n", f[l1][l2][l3] <= n ? "YES" : "NO");
}
return 0;
}

E. Tree Generator™

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 mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

const int maxn = 200010;
int n, q; char s[maxn];
struct node { int lmx, rmn, d, ld, rd, s, ans; } L, R, t[maxn << 2];

void upd(node &c, node &a, node &b) {
c.lmx = max(a.lmx, a.s + b.lmx), c.rmn = min(b.rmn, a.rmn + b.s);
c.d = max(b.d - a.s, a.d + b.s), c.s = a.s + b.s;
c.ld = max({a.ld, b.ld - a.s, a.d + b.lmx});
c.rd = max({b.rd, a.rd + b.s, b.d - a.rmn});
c.ans = max({a.ans, b.ans, b.ld - a.rmn, a.rd + b.lmx});
}

void build(int k, int l, int r) {
if (l == r) { t[k] = s[l] == '(' ? L : R; return; }
build(ls, l, mid), build(rs, mid + 1, r), upd(t[k], t[ls], t[rs]);
}

void modify(int k, int l, int r, int p) {
if (l == r) { t[k] = s[l] == '(' ? L : R; return; }
mid >= p ? modify(ls, l, mid, p) : modify(rs, mid + 1, r, p);
upd(t[k], t[ls], t[rs]);
}

int main() {
L = (node){1, 0, 1, 1, 1, 1, 1}, R = (node){0, -1, 1, 1, 1, -1, 1};
scanf("%d %d %s", &n, &q, s + 1), n = (n - 1) << 1;
build(1, 1, n), printf("%d\n", t[1].ans);
for (int i = 1, a, b; i <= q; i++) {
scanf("%d %d", &a, &b), swap(s[a], s[b]);
modify(1, 1, n, a), modify(1, 1, n, b);
printf("%d\n", t[1].ans);
}
return 0;
}