这次比赛做得乱七八糟,事实上一共只做出来两道题,结果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

这篇文章主要参考了Centroid DecompositionAn illustrated introduction to centroid decomposition两篇文章。


问题的描述

首先给出一道例题:Codeforces 342E. Xenia and Tree。这道题的题意是这样的:有一棵结点数量为n的树,结点标号为1到n。起始时,结点1是红色的,其他结点都是蓝色的。编程处理以下两种查询:

  • update(a):将a更新为红色
  • query(a):查询a离最近的红色点的距离

两种颜色的结点

可以立刻想到两种解法:

  1. 查询时做BFS/DFS(O(N)),更新时直接更新(O(1)
  2. 维护每个结点到最近的红色点的距离,查询时直接查询(O(1)),更新时做BFS/DFS(O(N)

显然这两种解法都不够好。重心剖分(Centroid Decomposition,以下简写为CD)则可以在这两种方法之间取得平衡,使得查询和更新的代价都变成O(log(N))

重心的定义

记树的总结点数为n,定义树的重心为,移除后使得留下的所有连通分量(树)的大小均不超过n/2的结点。

一个重心的例子

请注意:重心不是中心。

如何找到树的重心?

下面给出一种计算树的重心的算法。首先任取结点a,以a为树的根结点,计算它的所有子树的大小。如果这些子树的大小均不超过n/2,则a就是重心。否则,必然存在一棵(且只能有一棵——这一点是平凡的)子树,大小超过n/2。记b为该子树的根结点,对b重复上述算法。

上述算法的执行过程

b来说,以a为根的子树的大小必然不超过n/2,因此算法不会重复访问已经访问过的结点,因此算法是正确的,它的复杂度是O(n)

为什么算法是正确的

在具体实现中,以a为根结点,首先用DFS求出每棵子树的大小;然后用DFS寻找重心。因为算法不需要重复访问已经访问过的结点,因此对于每个结点,考虑它的子结点对应的子树大小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int subSize[N];
set<int> tree[N];

// 计算子树大小
int dfs(int u, int p) {
subSize[u] = 1;
for (int v: tree[u])
if (v != p)
subSize[u] += dfs(v, u);
return subSize[u];
}

// 计算重心
int get_centroid(int u, int p, int n) {
for (int v: tree[u])
if (v != p && subSize[v] > n/2)
return get_centroid(v, u, n);
return u;
}

练习

练习1:请证明每棵树最多只有一个重心,或者给出反例。

反例:如下图。

蓝色和红色结点各表示一个重心

练习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
int subSize[N];
set<int> tree[N]; // 为了方便删除……
int cd_father[N];

// 计算子树大小
int dfs(int u, int p) {
subSize[u] = 1;
for (int v: tree[u])
if (v != p)
subSize[u] += dfs(v, u);
return subSize[u];
}

// 计算重心
int get_centroid(int u, int p, int n) {
for (int v: tree[u])
if (v != p && subSize[v] > n/2)
return get_centroid(v, u, n);
return u;
}

// 重心分解
void centroid_decomposition(int u, int p) {
int n = dfs(u, p);
int centroid = get_centroid(u, p, n);
cd_father[centroid] = p;
for (int v: tree[centroid])
if (v != p) {
tree[v].erase(centroid);
centroid_decomposition(v, centroid);
}
tree[centroid].clear();
}

时间复杂度

建树的时间复杂度是多少?首先可以给出一个时间复杂度的上界:因为需要对每个结点都执行一次centroid_decomposition,且dfs的代价最多为O(n),因此时间复杂度最多为O(n^2)

不过事实上并没有那么多。对每个结点执行centroid_decomposition时,对应的连通分量大小已经大大减小了,所以dfs的代价也降低了——这是因为根据重心的性质,每个连通分量的大小最多为n/2。事实上这就类似于归并排序的分析:

每一层的代价之和都是O(n)

因为树的高度是O(log(n)),因此总时间复杂度为O(n*log(n))

而且实现中移除边的过程不会影响总时间复杂度,因为最多有O(n)条边需要移除,而移除每条边的代价最多是O(log(n))。(当然,你也可以不这么实现,省一点常数。)

重心剖分的性质

  1. 在CD树中,结点属于它的所有祖先对应的连通分量。

结点14属于14、15、11和3对应的连通分量

证明:在CD树中,结点ab的子结点,仅当a属于移除b后产生的连通分量。显然这件事的前提是,a属于b对应的连通分量。(这听起来是平凡的。)

  1. 原树中结点a到结点b的最短路可以分解成结点alca(a, b)lca(a, b)b的两条路径,其中lca(a, b)是CD树中ab的LCA。

原树中从9到10的最短路可以分解成从9到3的路径和从3到10的路径。

证明:由性质1,ab都属于lca(a, b)对应的连通分量。假定lca(a, b)并不在从ab的最短路上,则在原树中移除lca(a, b)后,ab仍然在同一个连通分量中,这意味着该连通分量的重心是ab的比lca(a, b)更低的共同祖先,这显然是荒谬的。

  1. 原树中的n^2条路径(此处把退化的路径也算进去了)均可分解成两条路径,这两条路径都属于在CD树中每个结点到它的所有祖先结点的共O(n*log(n))条路径的集合。(听起来真是晦涩……)

这个性质比较难,但非常重要。以下图为例:

结点14属于14、15、11和3对应的连通分量

共有n条从结点14开始的路径。这些路径可以分成以下几类:

  1. a in {14}:从14到14,再从14到a
  2. a in {15}:从14到15,再从15到a
  3. a in {6, 9, 13}:从14到11,再从11到a
  4. a in {1, 2, 4, 5, 7, 8, 10, 12}:从14到3,再从3到a

显然14、15、11和3都是14在CD树中的祖先。这种分类方法的思路是这样的:不是选择路径的两个端点,而是选择两个结点在CD树中的LCA。

证明1:性质2说明,原树中的每条路径都可以分解成两条路径(alca(a, b),以及lca(a, b)b)。下面证明从每个结点到它的CD树中祖先结点的路径总数是O(n*log(n))。显然CD树的高度是O(log(n)),共有n个结点,所以祖先总数是O(n*log(n))

证明2:这次考虑CD树中每个结点的后代数量。显然根结点的后代总数是n-1,而且每一层的结点的后代总数都是O(n),因此总路径数为O(n*log(n))

练习

练习3:给定下图中的CD树,求原树。是否有多个可能的答案?

CD树

这棵树看起来好像很有问题,居然有重复结点,算了不管它了。。。不过显然CD树和原树不是一一对应的,举个最简单的例子,如果连通分量只剩下两个结点,那么这两个结点哪一个做重心都可以。

练习4:证明每棵CD树都是自己的CD树,或者举出反例。

证明:由CD树的构造过程可知,对于CD树的每棵子树,记其大小为n,去掉根结点后剩下的的每棵子树的大小均不超过n/2。这是因为每棵子树都是和一个联通分量对应的。因此,对CD树做重心剖分时,只需取每层的根结点为重心即可。

练习5:考虑以下陈述:“对于任意有根树,从ab的路径都可以分解成从alca(a, b)的路径和从lca(a, b)b的路径,这样我们就可以应用性质3中的方法进行处理。”如果这是真的,我们为什么需要重心剖分?

答:这确实是真的,但对于高度没有限制的树,这么做没有意义。考虑退化成一条链的树,根结点的后代数量是n-1,深度为1的结点的后代数量是n-2,以此类推,得到的分解路径总数是n(n-1)/2,和树中所有路径总数的数量级相同,没法起到简化表示的作用。

例题

Codeforces 342E. Xenia and Tree

题意

分析

这道题就是上面讲解时用到的例题,应该很好理解。将树进行重心剖分之后,每两个结点之间的距离都可以分解成它们在原树中到重心剖分树中的LCA的距离。这句话听起来太绕了,不如说,对于每两个结点,它们在重心剖分树中的LCA必然会出现在它们在原树中的最短路径上。从这就可以直接推导出,原树中的每条路径都能以两个端点在重心剖分树中的LCA为终点分解成两条路径。

所以我们可以考虑用ans来维护重心剖分树中每个结点到它的子树中最近的红色结点的距离。初始时,ans[a] = inf(之后才将第一个结点涂成红色)。

左侧是染色的原树,右侧是重心剖分和连通分量。

对于每个update(a)操作,因为a出现在它的祖先结点对应的分量中,所以只需对它的每个祖先结点b,更新ans[b] = min(ans[b], dist(a, b))。由于树的高度为O(log(n)),计算dist(a, b)的复杂度是O(log(n)),因此更新操作的复杂度是O(log^2(n))

对于每个query(a)操作,只需对它的所有祖先结点b,取dist(a, b) + ans[b]的最小值。如果记ans[b]对应的结点为c,则我们实际上是把从ac的路径分解成了从ab的路径(dist(a, b))和从bc的路径(ans[b])。这意味着dist(a, b) + ans[b]是从ab对应的连通分量中离b最近的红色结点的距离。查询操作的时间复杂度也是O(log^2(n))


我花了特别久的时间debug。模板背错之后出现的那些问题就不说了——一背错就很可能会死循环。首先,照原文中那种删除边的写法是行不通的:

1
2
3
4
5
6
7
8
9
10
11
12
13
void build(int u, int p) {
int n = dfs(u, p); // find the size of each subtree
int centroid = dfs(u, p, n); // find the centroid
if (p == -1) p = centroid; // dad of root is the root itself
dad[centroid] = p;

// for each tree resulting from the removal of the centroid
for (auto v : tree[centroid])
// v被删除后,指针就失效了,肯定会挂
tree[centroid].erase(v), // remove the edge to disconnect
tree[v].erase(centroid), // the component from the tree
build(v, centroid);
}

改成不会产生指针失效的版本也不行,会超时。我目前看到了两种比较好的解决方案:

  • 仍然用set,但是在for循环中不从centroid对应的set删除,在for循环结束后再统一清空
  • 改用vector,单独记录删除标记

然后我想了想,觉得自己的LCA写的恐怕大有问题(因为太久没写了),于是就找了个地方,抄了一下LCA的主要计算过程。这之后我觉得没有什么问题了,但是交上去却持续WA。我感到很困惑,查了又查,却找不到什么错误。最后我找到了一份相当不错的结构和我类似的参考代码,抱着“模块化debug”的心情把我的代码中的LCA整个换成了这份代码里的LCA——

结果竟然就过了!!!

原来我太久没写LCA,把初始化时求2^k级祖先的内外循环给搞反了。推导father[i][j]时可能需要的father[?][j-1]的第一维是不确定的,因此应该把j放在外层循环。

1
2
3
4
5
6
void lca_init() {
for (int j = 1; j < 21; j++) {
for (int i = 1; i <= n; i++)
father[i][j] = father[father[i][j-1]][j-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
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
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int n, m;
typedef long long LL;

vector<int> G[100002];
bool deleted[100002];
int subTreeSize[100002];
int cd_father[100002];
int father[100002][21];
LL dist[100002];
LL ans[100002];

// 计算父结点和结点深度(用于LCA)
void dfs(int cur, int parent, int depth) {
father[cur][0] = parent == -1 ? cur : parent;
dist[cur] = depth;
for (int u: G[cur])
if (u != parent) {
dfs(u, cur, depth + 1);
}
}

// LCA初始化
void lca_init() {
for (int j = 1; j < 21; j++) {
for (int i = 1; i <= n; i++)
father[i][j] = father[father[i][j-1]][j-1];
}
}

// 计算x和y的LCA
int get_lca(int x, int y) {
if (dist[x] < dist[y]) swap(x, y);
int d = dist[x] - dist[y];
for (int i = 20; i >= 0; i--) {
if (d & (1 << i))
x = father[x][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--) {
if (father[x][i] != father[y][i]) {
x = father[x][i];
y = father[y][i];
}
}
return father[x][0];
}

// 根据LCA和深度计算x和y在树中的距离
LL get_dist(int x, int y) {
int fa = get_lca(x, y);
return dist[x] + dist[y] - 2 * dist[fa];
}

// 计算子树大小(每次重心剖分的子树都需要)
void get_size(int cur, int parent) {
subTreeSize[cur] = 1;
for (int u: G[cur]) {
if (!deleted[u] && u != parent) {
get_size(u, cur);
subTreeSize[cur] += subTreeSize[u];
}
}
}

// 计算重心
int get_centroid(int cur, int parent, int n) {
for (int u: G[cur]) {
if (!deleted[u] && u != parent && subTreeSize[u] > n / 2)
return get_centroid(u, cur, n);
}
return cur;
}

// 递归进行重心剖分
void centroid_decomposition(int cur, int parent) {
get_size(cur, parent);
int centroid = get_centroid(cur, parent, subTreeSize[cur]);
cd_father[centroid] = parent;
// 这里采取的则是一种比较愚蠢的策略,单独为结点记录了删除标记……
deleted[centroid] = true;
for (int u: G[centroid])
if (!deleted[u] && u != parent)
centroid_decomposition(u, centroid);
}

// 将a更新为红色结点
void update(int a) {
int b = a;
// 对于a在CD树中的每个祖先(包括a),更新a到它的距离
// 注意不是a在CD树中到它的距离!!!
while (b != -1) {
ans[b] = min(ans[b], get_dist(a, b));
b = cd_father[b];
}
}

// 查询a和最近的红色结点之间的距离
int query(int a) {
int b = a;
LL x = 1e9;
// 对于a在CD树中的每个祖先(包括a),取答案为(a到该祖先的距离+该祖先到最近红色结点距离)的最小值
// 注意距离不是CD树中的距离!!!
while (b != -1) {
x = min(x, ans[b] + get_dist(a, b));
b = cd_father[b];
}
return x;
}

int main() {
scanf("%d %d", &n, &m);
int a, b;
int t, v;
for (int i = 0; i < n - 1; i++) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
// 一些必要的初始化
dfs(1, -1, 0);
lca_init();
centroid_decomposition(1, -1);

for (int i = 1; i <= n; i++)
ans[i] = 1e9;
update(1);
for (int i = 0; i < m; i++) {
scanf("%d %d", &t, &v);
if (t == 1) update(v);
else printf("%d\n", query(v));
}
return 0;
}

Codeforces 321C. Ciel the Commander

题意

给定一棵树,要求把上面的所有结点用AZ标记,使得对于任意两个标记相同的结点,它们之间的最短路上至少有一个标记(字典序)更小的结点。

分析

只要会重心剖分,想到这道题要用到重心剖分并不难(……这好像是句废话,考虑到这道题是作为例题出现的……),所以难点在于如何证明重心剖分得到的是最优解。(对于实现而言,这并不是个难点)

题解里给出了两种证明思路。第一种是自顶向下构造。显然,rank为A的结点只能有一个。选定一个结点为rank A之后,树会被分成几个连通分量,这些连通分量之间不会有非法路径(因为必须要通过这个结点),所以可以单独考虑这些连通分量,于是我们得到了一个递归解法。问题是应该怎么选择A。单从连通分量的大小来考虑,我们希望这些连通分量的大小尽量小,所以不妨取rank A结点为重心。然后判断CD树的高度是否大于26就行。

不过,问题是我觉得不能单从连通分量的大小来考虑。但到底怎么考虑比较好,这个我也不知道……

代码

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
#include <iostream>
#include <set>
using namespace std;
set<int> g[100005];
int cd_father[100005];
int subSize[100005];
int cd_depth[100005];
int n;
int maxDepth;

int get_size(int cur, int p) {
subSize[cur] = 1;
for (int u: g[cur])
if (u != p)
subSize[cur] += get_size(u, cur);
return subSize[cur];
}

int get_centroid(int cur, int p, int n) {
for (int u: g[cur])
if (u != p && subSize[u] > n / 2)
return get_centroid(u, cur, n);
return cur;
}

void centroid_decomposition(int cur, int p, int depth) {
int n = get_size(cur, p);
int centroid = get_centroid(cur, p, n);
cd_father[centroid] = p;
cd_depth[centroid] = depth;
maxDepth = max(depth, maxDepth);
for (int u: g[centroid])
if (u != p) {
g[u].erase(centroid);
centroid_decomposition(u, centroid, depth + 1);
}
g[centroid].clear();
}

int main() {
cin >> n;
int u, v;
for (int i = 1; i < n; i++) {
cin >> u >> v;
g[u].insert(v);
g[v].insert(u);
}
centroid_decomposition(1, -1, 0);
if (maxDepth >= 26) {
cout << "Impossible!" << endl;
return 0;
}
for (int i = 1; i <= n; i++)
cout << (char) (cd_depth[i] + 'A') << ' ';
cout << endl;
return 0;
}

因为写总结和做题实在太艰难了,我决定以后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