这次比赛做得乱七八糟,事实上一共只做出来两道题,结果rating还涨了一点点,看来确实有点难。。

1117A

题目来源:https://codeforces.com/contest/1117/problem/A

提交次数:1/1

题意

给定一个数组,问数组中满足平均数最大的前提下长度最长的子数列。

分析

就是找到最大值然后计算最大值最多连续出现了多少次而已。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int n;
int a[100005];
int main() {
int maxn = -1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
maxn = max(maxn, a[i]);
}
int ans = 0, l = 1;
for (int i = 1; i <= n; i++) {
if (i == n || a[i] != a[i - 1]) {
if (a[i - 1] == maxn) ans = max(l, ans);
l = 1;
}
else l++;
}
cout << ans << endl;
return 0;
}

1117B

题目来源:https://codeforces.com/contest/1117/problem/B

提交次数:1/1

题意

给定n个emote,每个emote可以将对手的快乐值增加a[i],你可以使用一些emote共m次,相同的emote最多连续使用k次,问最多能增加多少快乐值?

分析

找出值最大和值次大的emote,连续用最大的emotek次,用一次次大的emote,再接着用最大的emote,以此类推,直到一共用了m次为止。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, m, k;
LL a[200005];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
LL cnt = m / (k + 1);
LL ans = cnt * (a[n-1] * k + a[n-2]) + (m - (k + 1) * cnt) * a[n-1];
cout << ans << endl;
return 0;
}

1117C

题目来源:https://codeforces.com/contest/1117/problem/C

提交次数:1/4

题意

你在(x1, y1)处有一艘船,每天可以向上或下、左、右移动1格。每天的移动效果会和天气效果叠加,天气效果会使得船根据风向往上或下、左、右移动一格。给定m天的天气,之后的天气是循环的,问最少需要几天,船才能到达(x2, y2)处?

分析

比赛的时候我意识到走完一个天气循环之后,能到的位置是一个菱形了(或者说是一个尖朝上的正方形);但很可惜我没有意识到这件事的本质,还打算拿计算几何来做(??)。显然,这件事的本质是这样的:把天气推船走的路和船自己走的路分开,可以得出一个结论:天气在一个循环内推船走的路是固定的,不妨记为(dx, dy);船自己可以在这个点周围走出一个菱形,或者说是所有满足|x-dx|+|y-dy|<=n的点。所以对天数二分查找就好了。当然,还是需要重视一下二分查找的前提:只要x天能到,那么y>=x天也能到。(大不了不动)[1]

除此之外就是注意上界。显然如果能到达(x2, y2),每个天气循环至少要向这个方向前进1格(曼哈顿距离),所以上界是(|x2-x1| + |y2-y1|)*n。如果走了这么多还没到,说明到不了了。

代码

因为long long int的使用错了好多次……

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL x1, y1, x2, y2;
int n;
char s[100005];
pair<LL, LL> pos[100005];
LL fx, fy;
// U, R, D, L
int mx[4] = {0, 1, 0, -1};
int my[4] = {1, 0, -1, 0};

bool isOk(LL days) {
LL sx = (days / n) * fx, sy = (days / n) * fy;
sx += pos[days % n].first, sy += pos[days % n].second;
return abs(x2 - sx) + abs(y2 - sy) <= days;
}

int main() {
cin >> x1 >> y1 >> x2 >> y2;
x2 -= x1;
y2 -= y1;
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++) {
int d;
if (s[i-1] == 'U') d = 0;
else if (s[i-1] == 'R') d = 1;
else if (s[i-1] == 'D') d = 2;
else if (s[i-1] == 'L') d = 3;
pos[i].first = pos[i-1].first + mx[d];
pos[i].second = pos[i-1].second + my[d];
}
fx = pos[n].first, fy = pos[n].second;

LL l = 0, r = (abs(x2) + abs(y2)) * n;
while (l < r) {
LL m = (l + r) / 2;
if (isOk(m)) r = m;
else l = m + 1;
}
if (!isOk(l)) cout << -1 << endl;
else cout << l << endl;
return 0;
}

1117D

题目来源:https://codeforces.com/contest/1117/problem/D

提交次数:1/1

题意

一颗魔法宝石可以分裂成M颗普通宝石,问有多少种选择魔法宝石的方法,使得分裂后总的宝石数量是N?不同的魔法宝石数量和不同index的分裂被认为是不同的方法。N<=10^18M<=100

分析

比赛的时候我努力推了一个公式出来:

$$\sum_{i=0}^{\lfloor N/M \rfloor} \binom{N-(M-1)i}{i}$$

但是肯定不能这么算,因为N太大了。我心想:用动态规划估计也不行。

事实上得用到动态规划递推的思路,看到NM的大小,我早该想到是矩阵快速幂才对。

f[n]表示N=n时的方法数量。显然有两种方法进行递推:一种是加上一块不分裂的宝石(f[n-1]);另一种是加上一块分裂的宝石(f[n-M])。(虽然第二维看起来没有什么意义……)考虑到递推的本质,不需要乘新加的宝石的位置,因此:

1
f[n] = f[n-1] + f[n-M]

现在就可以造一个矩阵乘法迭代公式了:

1
2
3
4
5
| f[n-M]  f[n-M+1]  ...  f[n-1] | * | 0 0 0 ... 0 1 | = | f[n-M+1] |
| 1 0 0 ... 0 0 | | f[n-M+2] |
| 0 1 0 ... 0 0 | | ... |
| 0 0 1 ... 0 0 | | f[n-1] |
| 0 0 0 ... 1 1 | | f[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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
LL N;
int M;

const LL P = 1000000007;

struct Matrix {
int n, m;
LL a[105][105];

Matrix(int _n, int _m) {
memset(a, 0, sizeof(a));
n = _n;
m = _m;
}

friend Matrix operator * (const Matrix& m1, const Matrix& m2) {
Matrix m3(m1.n, m2.m);
for (int i = 1; i <= m1.n; i++)
for (int j = 1; j <= m1.m; j++)
for (int k = 1; k <= m2.m; k++)
m3.a[i][k] = (m3.a[i][k] + m1.a[i][j] * m2.a[j][k]) % P;
return m3;
}

void print() {
cout << n << ' ' << m << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
};

Matrix getIdentity(int n) {
Matrix mat(n, n);
for (int i = 1; i <= n; i++)
mat.a[i][i] = 1;
return mat;
}

int main() {
cin >> N >> M;
if (N < M) {
cout << 1 << endl;
return 0;
}
Matrix v(1, M);
for (int i = 1; i < M; i++)
v.a[1][i] = 1;
v.a[1][M] = 2;

Matrix x(M, M);
for (int i = 2; i <= M; i++)
x.a[i][i - 1] = 1;
x.a[1][M] = x.a[M][M] = 1;

LL delta = N - M;
Matrix pow = x;
Matrix ans = getIdentity(M);
while (delta > 0) {
if (delta & 1) ans = ans * pow;
delta >>= 1;
pow = pow * pow;
}
v = v * ans;
cout << v.a[1][M] << endl;
return 0;
}

1117E

题目来源:https://codeforces.com/contest/1117/problem/E

提交次数:1/1

题意

这是一道交互题。给定一个字符串,已知对它进行了<=n次swap操作;你可以拿出一个新的和它长度一样的字符串,然后得到对这个字符串进行相同的swap之后的结果。你最多可以提交三次字符串。问原来的字符串是多少?

分析

比赛的时候,我看了看这道题……觉得很有趣,但应该想半天也做不出来吧。(我从来没在比赛里做对过交互题)这道题的一种解法是这样的:既然每次提交的字符串的swap操作是一样的,不妨把提交的三次字符串看成是一个字符串,它的每个位置是由三个字符组成的一个“超字符”。这样我们就可以认为每个位置的“超字符”是两两不等的了!因为26^3 = 17576 >= 1e4,这是可行的。

然后就可以立即得到每个输入位置到输出位置的映射了,倒过来对原来的字符串重新做一遍就行了。

评论区里还出现了用中国剩余定理的做法,我没细看。[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
#include <iostream>
#include <cstring>
using namespace std;

char s[10005];
char q[3][10005];
char a[3][10005];
int mapping[10005];
int n;

int main() {
cin >> s;
n = strlen(s);
int m = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
q[0][m] = i + 'a';
q[1][m] = j + 'a';
q[2][m] = k + 'a';
m++;
if (m >= n) break;
}
if (m >= n) break;
}
if (m >= n) break;
}
for (int i = 0; i < 3; i++) {
cout << "? " << q[i] << endl;
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int idx = (a[0][i] - 'a') * 26 * 26 + (a[1][i] - 'a') * 26 + (a[2][i] - 'a');
mapping[idx] = i;
}
cout << "! ";
for (int i = 0; i < n; i++)
cout << s[mapping[i]];
cout << endl;
return 0;
}

1117F

题目来源:https://codeforces.com/contest/1117/problem/F

提交次数:?/?

题意

还没看懂,感觉有点难度。

111G

题目来源:https://codeforces.com/contest/1117/problem/G

提交次数:?/?

题意

给定一个由1到n的全排列组成的数组,记m[l, r]范围内的最大元素index,定义函数

1
2
f(l, r) = (r - l + 1) + f(l, m - 1) + f(m + 1, r) (l <= r)
f(l, r) = 0 (l > r)

给定q个询问,请给定f的值。

1 <= n, q <= 1e6

分析

这道题我比赛的时候自然是不会做的。比赛完了,看看题解,发现也晦涩难懂。[1]

首先需要把f分解成两个函数,flfr

1
2
3
fl(l, r) = (m - l) + fl(l, m-1) + fl(m+1, r)
fr(l, r) = (r - m) + fr(l, m-1) + fr(m+1, r)
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)

可以用数学归纳法简单地证明这个分解的正确性(虽然我可不知道为什么要这样分解……):

1
2
3
4
5
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)
= (r - l + 1) + fl(l, m-1) + fl(m+1, r) + (m - l)
+ fr(l, m-1) + fr(m+1, r) + (r - m)
= (r - l + 1) + f(l, m-1) - (m-1 - l + 1) + f(m+1, r) - (r - (m+1) + 1) + (r - l)
= (r - l + 1) + f(l, m-1) + f(m+1, r)

然后不妨举一个例子来看看fl是怎么算出来的:

fl的例子

(显然fl(i, i) = fr(i,i) = 0

把这些式子全部展开,就会变成:

1
2
3
4
fl(1, 6) = (3-1) + fl(1, 2) + fl(4, 6)
= (3-1) + (1-1) + fl(2, 2) + (4-4) + fl(5, 6)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + fl(5, 5)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + (5, 5)

可以看出,fl其实是由6项组成的,而且每一项都是某个l <= i <= r与它左边最近的比它小的元素(或者l)之间的距离。这么想其实很合理。记i左边离它最近的比它大的元素为lf[i],可以看出,它对fl(l, r)产生贡献当且仅当它被作为最大元素选中了,且贡献大小为min(i - l, i - lf[i] - 1)


  1. Educational Codeforces Round 60 Editorial

  2. saeed_odak's comment for 1117E

因为写总结和做题实在太艰难了,我决定以后CF每场比赛只写一篇总结……

1110A

题目来源:https://codeforces.com/contest/1110/problem/A

提交次数:1/1

题意

分析

代码

1110D

题目来源:https://codeforces.com/contest/1110/problem/D

提交次数:1/1

题意

给定若干个1和m之间的整数,定义triplet为形如(x, x, x)(x, x+1, x+2)的元组,问这些整数最多一共能组成多少个triplet?

分析

这道题有一个非常必要的观察:如果有大于等于三个的形如[x, x+1, x+2]的triplet,那么完全可以把其中的三个替换成[x, x, x][x+1, x+1, x+1][x+2, x+2, x+2]。这也就意味着对于每一个x,形如[x-2, x-1, x]的triplet最多只有2个。[1]

然后我就想了一种错漏百出的方法,调了一个下午,终于调出来了。

f[i][x][y]表示考虑前i-1个数组成的triplet,a[i-1]还剩x个,a[i-2]还剩y个时的triplet总数。我心想:既然连续的triplet最多只有2个,那么xy的上限就都是2。(后来事实证明这很离谱)于是列出向后的转移方程:

1
2
3
4
5
6
7
8
9
10
11
12
// 不组成形如(i-2, i-1, i)的triplet
if (a[i] >= 0)
f[i+1][(a[i] - 0) % 3][x - 0] =
max(f[i+1][(a[i]- 0) % 3][x - 0], f[i][x][y] + 0 + (a[i] - 0) / 3);
// 组成一个形如(i-2, i-1, i)的triplet
if (a[i] >= 1 && x >= 1 && y >= 1)
f[i+1][(a[i] - 1) % 3][x - 1] =
max(f[i+1][(a[i] - 1) % 3][x - 1], f[i][x][y] + 1 + (a[i] - 1) / 3);
// 组成两个形如(i-2, i-1, i)的triplet
if (a[i] >= 2 && x >= 2 && y >= 2)
f[i+1][(a[i] - 2) % 3][x - 2] =
max(f[i+1][(a[i] - 2) % 3][x - 2], f[i][x][y] + 2 + (a[i] - 2) / 3);

跑一下看看,发现错得离谱。思考了一段时间之后,发觉这个转移方程“太准确了”。比如说,a[4]=2时,f[4][2][2]可以转移到f[5][1][1],但也应该可以转移到f[5][0][1]f[5][1][0](丢掉一些4和3也是可以的)。于是把转移方程修改如下,加入了后面两维的更多可能性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if (a[i] >= 0) {
for (int k = 0; k <= min(a[i], 2); k++) {
for (int j = 0; j <= x - 0; j++) {
f[i+1][k][j] =
max(f[i+1][k][j], f[i][x][y] + 0 + (a[i] - k) / 3);
}
}
}
if (a[i] >= 1 && x >= 1 && y >= 1) {
for (int k = 0; k <= min(a[i] - 1, 2); k++) {
for (int j = 0; j <= x - 1; j++) {
f[i+1][k][j] =
max(f[i+1][k][j], f[i][x][y] + 1 + (a[i] - k - 1) / 3);
}
}
}
if (a[i] >= 2 && x >= 2 && y >= 2) {
for (int k = 0; k <= min(a[i] - 2, 2); k++) {
f[i+1][k][x - 2] =
max(f[i+1][k][x - 2], f[i][x][y] + 2 + (a[i] - k - 2) / 3);
}
}

结果还是不对。经过更加漫长的debug,我意识到这种做法里的上限不能是2,因为它表示的是整体剩下的上限,而不是一共有多少个以它结尾的triplet。于是我直接把上限改成了6(既然有三种triplet的可能性),然后就过了(虽然耗时非常长)。

代码

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 <iostream>
#include <cstring>
using namespace std;
int n, m;
int cnt[1000005];
int f[1000005][7][7];
int main() {
cin >> n >> m;
int *a = cnt + 1; // 处理i-2的边缘情况
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x]++;
}
int ans = 0;
for (int i = 1; i <= m + 1; i++) {
for (int x = 0; x <= min(6, a[i-1]); x++)
for (int y = 0; y <= min(6, a[i-2]); y++) {
if (a[i] >= 0) {
for (int k = 0; k <= min(a[i], 6); k++) {
for (int j = 0; j <= x - 0; j++) {
f[i+1][k][j] =
max(f[i+1][k][j], f[i][x][y] + 0 + (a[i] - k) / 3);
}
}
}
if (a[i] >= 1 && x >= 1 && y >= 1) {
for (int k = 0; k <= min(a[i] - 1, 6); k++) {
for (int j = 0; j <= x - 1; j++) {
f[i+1][k][j] =
max(f[i+1][k][j], f[i][x][y] + 1 + (a[i] - k - 1) / 3);
}
}
}
if (a[i] >= 2 && x >= 2 && y >= 2) {
for (int k = 0; k <= min(a[i] - 2, 6); k++) {
f[i+1][k][x - 2] =
max(f[i+1][k][x - 2], f[i][x][y] + 2 + (a[i] - k - 2) / 3);
}
}
}
}
for (int x = 0; x <= 6; x++)
for (int y = 0; y <= 6; y++)
ans = max(ans, f[m + 2][x][y]);
cout << ans << endl;
return 0;
}

1110F

题目来源:https://codeforces.com/contest/1110/problem/F

提交次数:1/1

题意

给定一棵带权树,所有结点按DFS遍历顺序从1到n编号,回答q次询问:给定整数v、l和r,找到从结点v到编号在l和r之间的叶结点之间的最短距离。

分析

题解里给出了一种很类似于可持久化线段树的离线方法:对根结点记录它到每个叶子的距离,然后从根结点走到需要查询的结点v,同时根据边权更新它到叶子的距离。不过并不是很详细。[1]

另一种方法是使用重心剖分(centroid decomposition,我就简称CD了)。首先对树进行重心剖分。对于每个叶结点,将它存储在它在重心剖分树的每个祖先结点中,也就是对重心剖分树中的每个结点,维护它子树中的叶结点的一个list,包括编号和(到该结点的)距离。需要回答询问时,对于结点v在重心剖分树中的每个祖先结点,查询该结点对应的叶结点中,编号在l和r之间的叶结点中的最短距离。这一步可以用线段树。[2]

不妨举个例子。这是CF上的第五个测试数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
10 10
1 12
2 89
3 20
3 37
3 15
2 43
7 8
8 31
1 52
8 8 9
1 1 8
7 7 10
4 3 4
9 3 8
7 7 9
6 7 10
2 3 7
6 8 10
7 1 4

左侧是原树,右侧是重心剖分树,以及子树中叶结点到当前结点的距离

真的去写的时候,照例遇到了一万个问题,不过幸好这次有一份写得相当不错的代码[3]可以参照,省了很多时间。重心剖分的模板每次都背错这种愚蠢的事情就不说了,不过仍然会遇到如何组织树的这个问题。之前已经说过了,其实用修正过写法的setvector加上删除标志都可以接受;但这次需要存边权,换成map听起来有点不太像一棵树。(倒不如说是我觉得这样遍历太麻烦了)所以换成了vector<pair<int, long long>>

除了重心剖分以外,为了计算距离,当然LCA也是需要的。这次我虽然基本没有背错LCA模板,但我忘记这是棵带权树了。当然改起来很容易,把深度改成到根结点的距离就行。

初始化的部分倒是挺好写的——如果某个结点是叶子,那么就把它加到它在CD树的所有祖先(包括自己)的叶结点list中,同时计算距离。在这一步(或者不如说是下一步)中,我没有意识到这个list可能是空的,因为CD树的叶结点不一定是原树中的叶结点,所以仍然花了一些debug的时间。

所以下面得给每个结点都建一棵线段树。还采用自顶向下的那种方法就实在太冗长了,于是我直接抄了[3]中的zkw_cf线段树,这个东西是对zkw线段树的改进,不仅是自底向上的,而且只需要使用2*n的空间,不需要和2的幂对齐了。不过我还没太搞明白这是怎么做到的,就直接抄了。。。

下面这个问题花了我很久去debug,听起来十分愚蠢,但事实就是这样的……CD树上每个叶结点的线段树都是做了离散化的,只包含有的叶结点的编号。所以需要查的时候,显然需要找到编号的index。所以下面的问题是:对于排好序的pair<int, LL> a[n]l <= r,如何找到最左边的满足a[i].first >= li和最右边的满足a[i].first <= ri?答案当然是二分查找,但是过程相当tricky……总之我最后也是又抄代码了。

最后一个问题很傻逼。我又忘记在CD树中从下向上查时,两个结点的距离不能用它们到中间结点的距离的和来推导了,这只能重新直接在原树中算……

总的来说这算法比较慢。我现在懒得去分析复杂度了……

代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
int q, n;
vector<pair<int, LL>> tree[500005];
bool deleted[500005];
int cd_father[500005];
int father[500005][30];
LL dist[500005];
int level[500005];
int subSize[500005];

// 抄来的zkw_cf线段树
struct TreeNode {
vector<pair<int, LL>> leaves;
vector<LL> tree;
int n;

void init() {
n = leaves.size();
sort(leaves.begin(), leaves.end());
tree.resize(2 * n);
for (int i = 0; i < n; i++)
tree[n + i] = leaves[i].second;
for (int i = n - 1; i > 0; i--)
tree[i] = min(tree[2 * i], tree[2 * i + 1]);
}

LL query(int l, int r, bool convert = false) {

if (leaves.size() == 0 || r < leaves.front().first || leaves.back().first < l) return 1e16;
if (convert) {
// 抄的代码(注意r是开区间,这是这种线段树写法的要求)
l = lower_bound(leaves.begin(), leaves.end(), make_pair(l, (LL) -1)) - leaves.begin();
r = lower_bound(leaves.begin(), leaves.end(), make_pair(r + 1, (LL) -1)) - leaves.begin();
}
LL ans = 1e16;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) ans = min(ans, tree[l++]);
if (r & 1) ans = min(ans, tree[--r]);
}
return ans;
}

} segTree[500005];

void dfs(int cur, int parent, LL d, int l) {
dist[cur] = d;
level[cur] = l;
father[cur][0] = parent == -1 ? cur : parent;
for (int i = 0; i < tree[cur].size(); i++)
if (tree[cur][i].first != parent)
dfs(tree[cur][i].first, cur, d + tree[cur][i].second, l + 1);
}

void lca_init() {
for (int dep = 1; dep < 30; dep++)
for (int i = 1; i <= n; i++)
father[i][dep] = father[father[i][dep-1]][dep-1];
}

int get_lca(int x, int y) {
if (level[x] < level[y]) swap(x, y);
int d = level[x] - level[y];
for (int i = 0; i < 30; i++)
if (d & (1 << i))
x = father[x][i];
if (x == y) return x;
for (int i = 29; i >= 0; i--)
if (father[x][i] != father[y][i])
x = father[x][i], y = father[y][i];
return father[x][0];
}

LL get_dist(int x, int y) {
return dist[x] + dist[y] - 2 * dist[get_lca(x, y)];
}

int dfs_sub_size(int cur, int parent) {
subSize[cur] = 1;
for (int i = 0; i < tree[cur].size(); i++) {
int u = tree[cur][i].first;
if (u != parent && !deleted[u])
subSize[cur] += dfs_sub_size(u, cur);
}
return subSize[cur];
}

int get_centroid(int cur, int parent, int n) {
for (int i = 0; i < tree[cur].size(); i++)
if (tree[cur][i].first != parent && !deleted[tree[cur][i].first]
&& subSize[tree[cur][i].first] > n / 2)
return get_centroid(tree[cur][i].first, cur, n);
return cur;
}

void centroid_decomposition(int cur, int parent) {
int n = dfs_sub_size(cur, parent);
int centroid = get_centroid(cur, parent, n);
cd_father[centroid] = parent;
deleted[centroid] = true;
for (int i = 0; i < tree[centroid].size(); i++) {
int u = tree[centroid][i].first;
if (u != parent && !deleted[u])
centroid_decomposition(u, centroid);
}
}

void init() {
dfs(1, -1, 0, 0);
lca_init();
centroid_decomposition(1, -1);

for (int i = 2; i <= n; i++) {
if (tree[i].size() != 1) continue;
// 是叶子
int cur = i;
while (cur != -1) {
segTree[cur].leaves.emplace_back(i, get_dist(i, cur));
cur = cd_father[cur];
}
}
for (int i = 1; i <= n; i++) {
segTree[i].init();
}
}

LL query(int v, int l, int r) {
LL ans = 1e18;
int p = v;
while (p != -1) {
// upDist并不是累加的!(某个bug曾经出现的位置)
ans = min(ans, segTree[p].query(l, r, true) + get_dist(v, p));
p = cd_father[p];
}
return ans;
}

int main() {
scanf("%d %d", &n, &q);
for (int i = 2; i <= n; i++) {
int p, w;
scanf("%d %d", &p, &w);
tree[i].emplace_back(p, w);
tree[p].emplace_back(i, w);
}

init();

int v, l, r;
for (int i = 0; i < q; i++) {
scanf("%d %d %d", &v, &l, &r);
printf("%lld\n", query(v, l, r));
}
return 0;
}

  1. The Editorial of the First Codeforces Global Round

  2. Codeforces - comment of gaurav172

  3. tfg's solution for 1110F

题目来源:https://codeforces.com/contest/1107/problem/E

提交次数:1/1

题意

给定一个长度为n的只包含0和1的字符串,将该串中连续i个相同字符消去将得到a[i]的收益,问消去整个字符串能得到的最大收益是多少?

分析

在不会做的三道题上鸽了好久,最后还是觉得DP最好写……


这个题解[soln1]特别简明扼要,大概抓住了问题的本质,不过我可能还没有完全理解它:

  • 每一个状态都可以用[start, end, prefix]表示,其中startend是字符串中的起始和结束index(不妨假设两端都是闭区间)(不是也行),prefix是字符串前面附加的和s[start]相等的字符的数量(包括s[start])(不包括大概也行)
  • 每一个状态都有两种递推方法:
    • 第一种是直接消去字符串前面附加的字符:dp[start, end, prefix] = a[prefix] + dp[start + 1, end, 1]
    • 第二种是在字符串其他位置找到一个和s[start]相同的字符,然后消去中间的字符,获得一个更大的前缀:dp[start, end, prefix] = max(dp[start+1, i-1, 1] + dp[i, end, prefix+1]) (start < i <= end, s[i] == s[start])

虽然这个做法看起来很有道理,但其实我会有几个疑问。比如说,一些状态看起来其实是等价的:对于字符串"0001"dp[0, 3, 1]dp[2, 3, 3]表示的都是整个字符串。显然我们在递推过程中更容易得到前一种(没有被简化的)状态。那这两种状态有什么关系呢?是否需要手动简化?事实上,并不需要手动简化,dp[0, 3, 1]在递推中会自动得到dp[1, 3, 2]这个状态,并且进一步得到dp[2, 3, 3]。所以,与其说后一种状态是“简化之后的”,不如说是另一种对状态的看法,而且是一种一般化的表示。

至于递推的顺序,大概是得end - start从小到大,且prefix从小到大。这听起来有点麻烦(而且可能会增加复杂度),不如就写成递归形式算了。

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

代码

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long int LL;
int n;
bool s[105];
LL a[105];
LL f[105][105][105];

LL calc(int start, int end, int p) {
if (f[start][end][p] != -1) return f[start][end][p];
if (start > end) return 0;
if (start == end) {
f[start][end][p] = a[p];
return f[start][end][p];
}
f[start][end][p] = a[p] + calc(start + 1, end, 1);
for (int i = start + 1; i <= end; i++) {
if (s[i] != s[start]) continue;
f[start][end][p] = max(f[start][end][p], calc(start + 1, i - 1, 1) + calc(i, end, p + 1));
}
return f[start][end][p];
}

int main() {
cin >> n;
for (int i = 0; i < n; i++) {
char ch;
cin >> ch;
s[i] = ch - '0';
}
for (int i = 1; i <= n; i++)
cin >> a[i];

memset(f, -1, sizeof(f));
cout << calc(0, n-1, 1) << endl;
}

题目来源:https://codeforces.com/contest/1107/problem/D

提交次数:2/2

题意

给定一个n*n的01矩阵A,定义A的x-压缩矩阵Bn/x * n/x大小的矩阵,且对于$i \in [1, n], , j \in [1, n]$,有

$$A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$$

显然必须要求x整除n,且A中映射到B中同一位置的不同元素必须相等。问x的最大值是多少。

分析

这道题我比赛的时候看错题了。不过其实它并不是很难。显然有

$$B[i][j] = A[(i-1)x + 1...x][(j-1)x + 1...x]$$

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

比较简单的解法1

显然每个B[i][j]都对应A中的一块矩形区域。那么就直接查看A中的这些矩形区域是否都为0或者都为1。但是这样做的话,每个x需要的复杂度是n^2,很可能太慢了。(事实上并不慢,因为x的总数是$\sigma(n)$,它的一个显然的上界是$\sqrt{n}$。)

不过还是可以做点优化的,求出包含A中左上元素的每个矩形的面积,然后就可以用它们加加减减来求出任何矩形的面积了。然后就可以直接判断每个矩形是否为全0或全1了……

矩形面积示意图

上图中:

Area(x1, y1, x2, y2) = S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]

对于每个x,一共有$(n/x)^2$个矩形需要考虑。由于

$$\sum_{x | n} (n/x)^2 = n^2 \sum_{x | n} 1/x^2 < n^2 \sum_{x=1}^{+\infty}1/x^2 = n^2 \pi^2/6$$

因此这个方法的复杂度是O(n^2)。[soln1]

更复杂一些的解法2

这种方法更巧妙(不过大概也更难想到)。

  • 找出矩形中每一行中所有连续的0或1线段的长度的最大公约数
  • 对矩形的每一列同样求最大公约数
  • 则该最大公约数就是所求x

如果矩形能被压缩,则显然上述条件是满足的。从上述条件推出能被压缩也是比较简单的:首先将每一行压缩成n/x个点,然后再对列进行压缩即可。[soln2]

代码

解法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
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
using namespace std;
bool matrix[5205][5205];
int colSum[5205][5205];
int sum[5205][5205];
int n;

// 求左上角坐标为(lr, lc),右下角坐标为(rr, rc)的矩形和
int getSum(int lr, int lc, int rr, int rc) {
int s11 = sum[lr-1][lc-1];
int s12 = sum[lr-1][rc] - s11;
return sum[rr][rc] - s12 - sum[rr][lc-1];
}

int main() {
cin >> n;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n / 4; j++) {
scanf(" %c", &c);
int x = '0' <= c && c <= '9' ? c - '0' : c - 'A' + 10;
matrix[i][j*4 + 1] = (x & 8) > 0;
matrix[i][j*4 + 2] = (x & 4) > 0;
matrix[i][j*4 + 3] = (x & 2) > 0;
matrix[i][j*4 + 4] = (x & 1) > 0;
}
}
// 求和
// sum[i][j]:右下端点为(i, j)的矩形的和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
colSum[i][j] = colSum[i-1][j] + matrix[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i][j-1] + colSum[i][j];
}
}
for (int x = n; x >= 1; x--) {
if (n % x != 0) continue;
bool ok = true;
for (int i = 1; i <= n; i += x) {
for (int j = 1; j <= n; j += x) {
int s = getSum(i, j, i + x - 1, j + x - 1);
if (!(s == 0 || s == x * x)) {
ok = false;
break;
}
}
if (!ok) break;
}
if (ok) {
cout << x << endl;
return 0;
}
}
return 0;
}

解法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
#include <iostream>
#include <cstdio>
using namespace std;
bool matrix[5205][5205];
int n;

int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}

int main() {
cin >> n;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n / 4; j++) {
scanf(" %c", &c);
int x = '0' <= c && c <= '9' ? c - '0' : c - 'A' + 10;
matrix[i][j*4 + 1] = (x & 8) > 0;
matrix[i][j*4 + 2] = (x & 4) > 0;
matrix[i][j*4 + 3] = (x & 2) > 0;
matrix[i][j*4 + 4] = (x & 1) > 0;
}
}
int ans = n;
for (int i = 1; i <= n; i++) {
int start = 1;
for (int j = 2; j <= n + 1; j++) {
if (j > n || matrix[i][j] != matrix[i][j-1]) {
ans = gcd(ans, j - start);
start = j;
}
}
}
for (int i = 1; i <= n; i++) {
int start = 1;
for (int j = 2; j <= n + 1; j++) {
if (j > n || matrix[j][i] != matrix[j-1][i]) {
ans = gcd(ans, j - start);
start = j;
}
}
}
cout << ans << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1107/problem/C

提交次数:1/1

题意

给定n个英文小写字符和对应的n个值,按某个字符就可以得到对应的值,不能连续按某个字符超过k次,问得到的值的总和最大是多少。

分析

这次比赛我做得乱七八糟。从提交数量来看,C应该是道很简单的题,但是我却做不出来。事后我发现我看错题了。

PS. 我决定以后CF比赛中我能做出来的题就不写题解了。不然题目实在太多了。。。


对于一串连续的字符,如果它的长度超过了k,那么从里面挑k个最大值就行。没了!

(比赛的时候我以为是要把这个串分割成若干个长度小于k的串。)

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int k, n;
LL a[200005];
char s[200005];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> s;
LL ans = 0;
int start = 0;
for (int i = 1; i <= n; i++) {
if (i == n || s[i] != s[i-1]) {
if (i - start > k)
sort(a + start, a + i);
for (int j = 0; j < k && i-j-1 >= start; j++)
ans += a[i - j - 1];
start = i;
}
}
cout << ans << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/F

提交次数:2/3

题意

给定一个n1<=n<=16)行m列的矩阵,重新排列矩阵的各行,使得逐列遍历矩阵时相邻两个数之差绝对值的最小值最大。

分析

还是一道状态压缩DP。首先计算出每两行之间的距离(注意第一行和最后一行的距离)。

然后对于每种状态,枚举可能的起始结点,最大化路径上边权重的最小值。状态总数是n * 2^n(末尾结点*状态总数),枚举起始结点的代价为O(n),枚举上一个结点的代价是O(n),总计算复杂度是O(n^3 * 2^n)。如果不用递归还要多一个O(n),不知道有没有解决这个问题的方法。

另一种比较神奇的方法是二分答案,然后在图上寻找回路。题解里的具体方法是这样的:枚举起始点i,对于每个点j,寻找一条从ij的经过了所有结点的路径,然后再判断ji是否有路径。题解[1]里这种方法的复杂度是O(n^2 * log(MAXN) * 2^n)。但是我并不会题解里的写法,所以我写出来的还是平凡的O(n^3 * 2^n)的求哈密顿回路法……

代码

迭代写法的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
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
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][16][1 << 16];
int n, m, k;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

int ans = 0;
// 枚举路径长度
for (int len = 1; len <= n; len++) {
for (int status = 0; status < (1 << n); status++) {
if (__builtin_popcount(status) != len) continue;
for (int first = 0; first < n; first++) {
if (!(status & (1 << first))) continue;
if (len == 1) {
f[first][first][status] = 1e9;
continue;
}
for (int cur = 0; cur < n; cur++) {
if (!(status & (1 << cur)) || first == cur) continue;
f[first][cur][status] = 0;
for (int last = 0; last < n; last++) {
if (!(status & (1 << last)) || cur == last) continue;
int x = min(f[first][last][status ^ (1 << cur)], nextOk[last][cur]);
if (len == n) x = min(x, firstLastOk[first][cur]);
f[first][cur][status] = max(f[first][cur][status], x);
}
if (len == n) ans = max(f[first][cur][status], ans);
}
}
}
}
cout << ans << endl;
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
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
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][1 << 16];
bool g[16][16];
int n, m, k;

int calc(int x, int state) {
if (f[x][state] != -1) return f[x][state];
f[x][state] = 0;
for (int i = 0; i < n; i++) {
if (i != x && (state & (1 << i)) && g[i][x] && calc(i, state ^ (1 << x))) {
f[x][state] = 1;
break;
}
}
return f[x][state];
}

bool isOk(int thres) {
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && nextOk[i][j] >= thres)
g[i][j] = true;
}
}

for (int i = 0; i < n; i++) {
memset(f, -1, sizeof(f)); // 因为这句memset位置错了,调了一阵子
// 控制只能从i开始
for (int j = 0; j < n; j++)
f[j][1 << j] = j == i ? 1 : 0;
for (int j = 0; j < n; j++) {
if (firstLastOk[i][j] >= thres) {
if (calc(j, (1 << n) - 1)) return true;
}
}
}
return false;
}

int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

// 二分答案
// 这个写法是从题解里抄的(感觉也不是很优雅啊)
// <del>谁叫你也写不出优雅的</del>
int l = 0, r = 1e9;
while (l < r - 1) {
int m = (l + r) >> 1;
if (isOk(m)) l = m;
else r = m;
}
if (isOk(r)) cout << r << endl;
else cout << l << endl;
return 0;
}

  1. Codeforces Round #531 (Div. 3) Editorial

题目来源:https://codeforces.com/contest/1102/problem/E

提交次数:1/1

题意

给定一个长度为n的数组a,要求为a生成一个对应的数组b,满足:

  • b[0] = 0
  • 对于任意0 <= i < j <= n,如果满足a[i] == a[j],必有b[i] == b[j](不过a[i] != a[j]时也可能有b[i] == b[j]
  • 任取0 <= i < n - 1,必有b[i] = b[i+1]b[i] + 1 = b[i+1]

问共有多少种可能的b

分析

显然b[i]是一个递增序列,因此可以自然推出,若a[i] == a[j],则必有b[i] == b[i+1] == ... = b[j],也就是说,对于a中任意位置两个相等的元素,它们在b中对应的是一整段相等的元素。显然这种元素相等是可能会发生重叠的,因此一个自然的想法就是,把重复的元素建模成线段,然后合并发生overlap的线段以得到相等元素的最长长度。

我的做法是,从后向前遍历a,如果发现当前元素和后面的元素重复了,则取index最靠后的元素,组成一条线段,插入到栈中与其他元素合并;否则把它自己的index作为一条线段插入到栈中。最后栈中留下的就是几条互不相交(且并组成了整个区间)的线段。

对于(除了第一条之外)每条线段,我们可以选择让它的值和前一条相等,也可以选择让它的值是前一条+1。每种选择都会导致生成一种新的b。于是结果是2^{线段数-1}

例子:对于a = {1, 2, 1, 2, 3},1对应的线段是[0, 2],2对应的线段是[1, 3],3对应的线段是[4, 4];合并之后得到两条线段,[0, 3][1, 4];只有两种b,分别是{0, 0, 0, 0, 0}{0, 0, 0, 0, 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
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int a[200005];
int n;

typedef long long int LL;
const LL P = 998244353;

LL pow2(LL x) {
LL pow = 2, ans = 1;
while (x > 0) {
if (x & 1)
ans = (ans * pow) % P;
pow = (pow * pow) % P;
x >>= 1;
}
return ans;
}

int main() {
map<int, int> indMap;
vector<pair<int, int>> s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (indMap.find(a[i]) == indMap.end()) {
indMap[a[i]] = i;
}
}
for (int i = n - 1; i >= 0; i--) {
pair<int, int> interval;
if (indMap.find(a[i]) != indMap.end() && indMap[a[i]] < i) {
interval = make_pair(indMap[a[i]], i);
}
else {
interval = make_pair(i, i);
}
if (!s.empty() && s.back().first <= interval.first && s.back().second >= interval.second)
continue;
if (!s.empty() && interval.second >= s.back().first) {
interval.second = s.back().second;
s.pop_back();
s.push_back(interval);
}
if (s.empty() || interval.second < s.back().first)
s.push_back(interval);
}


int cnt = 0;
if (!s.empty() && s.front().second < n - 1) cnt++;
if (!s.empty() && s.back().first > 0) cnt++;
for (int i = 0; i < s.size(); i++) {
cnt++;
// 本条线段和前一条线段之间的间隔
if (i > 0 && s[i - 1].second < s[i].first - 1)
cnt++;
}
cout << pow2(cnt - 1) << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/D

提交次数:1/1

题意

给定一个只包含0、1、2的长度是3的倍数的字符串,要求替换最少数量的字符,使得其中0、1、2的数量相等,且得到的字符串字典序最小。

分析

这道题让我想起之前的某道USACO题(Sorting a Three-Valued Sequence)。好吧,其实没啥太大的关系(除了都是三值序列以外)。

既然要求替换最少数量的字符,那么把什么字符换成什么字符,以及换多少个其实都是确定的。如果这一点听起来不是很直接的话……比如,0的数量和1的数量都比n/3多,那么多出来的0和1都要换成2。如果0的数量和1的数量都比n/3少,那么多出来的2要分别换成0和1。实际上只有这两种情况。

然后就可以开始考虑怎么换了。显然,如果要把小的字符换成大的字符,应该从后向前换,换完为止;如果把大的字符换成小的字符,应该从前往后换,也是换完为止。

光考虑这一点还不够。比如说我们需要把两个0换成1,两个0换成2,那么应该先(从后向前)换2,再(从后向前)换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
51
52
53
54
55
#include <iostream>
using namespace std;
int n;
int a[300000];
int cnt[3];
int main() {
char c;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> c;
a[i] = c - '0';
cnt[a[i]]++;
}
int m = n / 3;
// 从i改成j
int order[3][3] = {
{2, 1, 0},
{0, 1, 2},
{0, 1, 2}
};
for (int i = 0; i < 3; i++) {
for (int j1 = 0; j1 < 3; j1++) {
int j = order[i][j1];
if (i == j) continue;
if (cnt[i] == m || cnt[j] == m) continue;
if (cnt[i] < m || cnt[j] > m) continue;
// 从后向前改
if (i < j) {
for (int k = n - 1; k >= 0; k--) {
if (cnt[i] == m || cnt[j] == m) break;
if (a[k] == i) {
a[k] = j;
cnt[i]--;
cnt[j]++;
}
}
}
// 从前向后改
if (i > j) {
for (int k = 0; k < n; k++) {
if (cnt[i] == m || cnt[j] == m) break;
if (a[k] == i) {
a[k] = j;
cnt[i]--;
cnt[j]++;
}
}
}
}
}
for (int i = 0; i < n; i++)
cout << a[i];
cout << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1102/problem/C

提交次数:1/1

题意

n扇门,每扇门的耐久度是a[i],两个人轮流对这些门做一些操作:

  • 我可以任选一扇门,如果它的耐久度是b[i],则可以将它降低到max(0, b[i]-x)
  • 之后对方可以选择一扇门,如果它的耐久度是b[i]b[i] > 0,则可以将它增加到b[i]+y
  • 两人轮流进行游戏

游戏共有10^100轮。问游戏结束后耐久度变成0的门的数量最多是多少?

分析

这道题说是博弈论,其实没啥博弈的……(或者说没有什么复杂的算法)

如果x > y,那么最后肯定是我方完全胜利(这么多轮,无论对方怎么加耐久,我们都可以和对方对敲,然后把所有门都敲爆……)。

如果x <= y,事情就变得有些复杂了。如果我们任选一扇门来敲(且没有敲到0),那么对方在下一轮就可以把它补好,甚至比之前还牢靠(y > x);所以我们选能敲到0的门才有效果。对方的最佳策略显然就是把那些耐久值<=x的门赶紧补齐,补到一下敲不坏为止。所以我方能最终敲坏的门的数量就是耐久值<=x的门的总数除2(取ceil)(因为是我方先开始游戏,可以多敲坏一扇门)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int a[100];
int main() {
int n, x, y, cnt = 0;
cin >> n >> x >> y;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] <= x) cnt++;
}
if (x > y) cout << n << endl;
else cout << (cnt + 1) / 2 << endl;
return 0;
}