Codeforces Round #722 (Div. 2) 总结&题解

rank600+为啥还会掉,之前rank800+不还涨了吗,哭哭。。

关掉同步!!!

long long!!!

好好的A题1min过,结果B就脑瘫了,C证也不会证,结论又不敢猜,先不开long long 再不关同步,连WA两发也是活该。。

image-20210525125814833

A - Eshag Loves Big Arrays

给定序列 $a$,每次可以选择其中几个数,计算出其平均值,并将它们中大于平均值的数删除。求最多能删除几次。

答案就是 $a$ 中不是最小值的数的个数,这个结论很显然。

本来好好的开局,00:01过,当时还rank60+呐。。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-24 22:35:03
* Source: CF 1529 A
* Problem: https://codeforces.com/contest/1529/problem/A
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N;
vector<int> v;

int main() {
cin >> T;
while (T--) {
cin >> N;
v.resize(N);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
int p = N;
for (int i = 1; i < N; ++i) {
if (v[i] != v[i - 1]) {
p = i;
break;
}
}
cout << N - p << endl;
}
return 0;
}

B - Sifid and Strange Subsequences

给定序列 $a$,选出一个子序列 $b$,满足 $|b_i-b_j|\geq MAX(i<j)$,其中 $MAX=\max{b_i}$。求 $b$ 的最大长度。

显然 $b$ 中最多出现一个正数。

先选出所有负数和 $0$,并求出它们差的最小值。

若存在某个正数不大于这个最小值,则还可以选择这个正数。

开始写麻烦了,调了半天,这是后来改的代码。。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-24 22:35:03
* Source: CF 1529 B
* Problem: https://codeforces.com/contest/1529/problem/B
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

int T, N;
vector<int> v;
multiset<int> s;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--) {
cin >> N;
v.resize(N);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
int num = 0, mn = INT_MAX;
for (int i = 0; i < N; ++i) {
if (v[i] > 0) {
if (v[i] <= mn) ++num;
break;
}
++num;
if (i) chkMin(mn, v[i] - v[i - 1]);
}
cout << num << endl;
}
return 0;
}

C - Parsa’s Humongous Tree

给定一棵树,和每个节点的权值区间 $[l_i,r_i]$,即 $a_i\in [l_i,r_i]$,边 $(u,v)$ 的权值定义为 $|a_u-a_v|$。你需要确定每个点的权值,使得边权之和最大。

$n\leq 2\times 10^5$,$1\leq l_i,r_i\leq 10^9$

大胆猜结论,每个点的点权要么为左端点要么为右端点,然后树形DP就完了,记得关同步并开long long

粗糙的证明如下:

考虑调整法,将所有 $a_v$ 放在数轴上,给定 $a_u$ 的区间 $[l_u,r_u]$,要最大化 $\sum{|a_u-a_v|}$。

根据初中数学知识,当 $a_u$ 放在第 $\lfloor\frac{n}{2}\rfloor$ 和 $\lfloor\frac{n}{2}\rfloor+1$ 个点之间时,$\sum{|a_u-a_v|}$ 最小,而往两边移动都会导致距离和增大。

因此最大值要么在左端点要么在右端点。

$f_{u,0/1}$ 表示当点 $a_u$ 的权值为 $l_u/r_u$ 时,以 $u$ 为根的子树的边权之和的最大值。

转移方程:

$f_{u,0}=\sum\limits_{v\in son(u)}{\max(f_{v,0}+|l_u-l_v|,f_{v,1}+|l_u-r_v|)}$

$f_{u,1}=\sum\limits_{v\in son(u)}{\max(f_{v,0}+|r_u-l_v|,f_{v,1}+|r_u-r_v|)}$

复杂度 $O(n)$。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-24 22:35:03
* Source:
* Problem:
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {return y > x ? x = y, 1 : 0;}
template<class T, class G> bool chkMin(T &x, G y) {return y < x ? x = y, 1 : 0;}

int T, N;
vector<pii> p;
vector<vector<int>> E;
vector<ll> Mx, Mn;

void dfs(int u, int fa) {
Mx[u] = Mn[u] = 0;
for (auto v : E[u]) {
if (v == fa) continue;
dfs(v, u);
Mn[u] += max(Mn[v] + abs(p[u].fir - p[v].fir), Mx[v] + abs(p[u].fir - p[v].sec));
Mx[u] += max(Mn[v] + abs(p[u].sec - p[v].fir), Mx[v] + abs(p[u].sec - p[v].sec));
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--) {
cin >> N;
p.resize(N);
for (auto &x : p) cin >> x.fir >> x.sec;
p.insert(p.begin(), {0, 0});
E.resize(N + 1);
Mx.resize(N + 1);
Mn.resize(N + 1);
for (int i = 1; i <= N; ++i) E[i].clear();
for (int i = 1, u, v; i < N; ++i) {
cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1, 0);
cout << max(Mx[1], Mn[1]) << endl;
}
return 0;
}

D - Kavi on Pairing Duty

X轴上有 $2n$ 个点,第 $i$ 个点的坐标为 $i$。

现在要将这 $2n$ 个点两两配对,但对于任意两对点 $(l_i,r_i)$ 和 $(l_j,r_j)$,需要满足以下两个要求之一:

  • $r_i-l_i=r_j-l_j$
  • $l_i<l_j<r_j<r_i$ 或 $l_j<l_i<r_i<r_j$

image-20210525170149858

例如上图中,A和B都是合法的配对方案,而C就不是。因为红和蓝这两对点既不长度相等,又不存在嵌套。

求有多少种不同的配对方案。

$n\leq 10^6$

设 $f_i$ 为 $2i$ 个点的方案数,所求的值就是 $f_n$。

若点对之间不存在嵌套,则每个点对的长度相同,有 $n$ 的因数个数种不同方案,记为 $D(n)$。

若某些点对存在嵌套,则长度较小的那些点对一定组成一个连续区间,位于中间,其他的点对长度相同。

因此 $f_n=D(n)+\sum\limits_{i=1}^{n-1}{f_i}$。

如何计算 $D(n)$?

我之前一直是欧拉筛预处理所有质数后,对于所求质数做质因数分解,但这个方法实际上很慢。

我们可以仿照埃氏筛的方法,枚举因数 $i$,然后将所有 $i$ 的倍数的因数个数+1,这样的预处理复杂度大概是 $O(n\log{n})$ 量级。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-24 22:35:03
* Source: CF 1529 D
* Problem: https://codeforces.com/contest/1529/problem/D
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int MOD = 998244353;

int N;
vector<ll> g;
vector<int> num;

int main() {
cin >> N;
g.resize(N + 1);
num.resize(N + 1);
for (int i = 1; i <= N; ++i) {
for (int j = i; j <= N; j += i) {
++num[j];
}
}
g[1] = 1;
ll sum = 1;
for (int i = 2; i <= N; ++i) {
g[i] = num[i] + sum;
sum = (sum + g[i]) % MOD;
}
cout << g[N] << endl;
return 0;
}

E - Trees of Tranquillity

给定两棵树 $t1$ 和 $t2$。

任意两点 $u,v$ 若满足在 $t1$ 中存在祖先关系,在 $t2$ 中不存在祖先关系,则在新的无向图 $G$ 中增加边 $(u,v)$。

求 $G$ 的最大团的大小。

$n\leq 3\times 10^5$

对于 $G$ 中的任意一个团,其中的所有点必然构成 $t1$ 上一条从根节点到叶子节点的链的子集。

因此基本思路是,在DFS $t1$ 时,求出每条链上满足条件的最大子集大小。

因此需要维护一个集合,要求集合中的点满足在 $t2$ 中不存在祖先关系,并支持以下三种操作:

  • 插入点 $x$
  • 删除点 $x$
  • 查询集合中点的个数

考虑什么样的点可以插入到当前集合中:它不在当前集合中任意一个点的子树中。

考虑用DFS序维护,因为任意子树的DFS序构成一段连续的区间。

我们用线段树维护,插入点 $x$ 时,将它子树对应的区间全部染成颜色 $x$。

那么对于一个新点,查询它是否被染色即可得知它是否在集合中某个点的子树中。

若 $x$ 未被染色,则将 $x$ 的子树染色,集合中的点个数+1。

若查询结果为,点 $x$ 被染色,它在点 $y$ ($y$ 即是 $x$ 的颜色)的子树中。贪心地想,用 $x$ 替换掉 $y$ 一定更优,虽然集合中点的数量没变,但是由于选择 $x$ 而不能选的点集合是由于选择 $y$ 而不能选的点的子集(因此为未来的集合提供了这样的可能性,集合中有多个点,它们都在 $y$ 的子树中,但是不互为祖先)。

因此要撤销掉点 $y$ 的染色,并将 $x$ 的子树染色。并记录 $l[x]=y$,表示为了插入 $x$,撤销了 $y$。此时集合中的点个数不变。

与之对称的还有一种情况,即 $x$ 的某个子树被染色,那么翻转刚刚的思路,此时显然不应该插入 $x$。

因此线段树需要维护两个变量,即某个点的颜色以及某个区间是否存在某个点被染色。

DFS回溯到 $x$时,我们要撤销 $x$ 的染色,并将 $l[x]$ (若存在)的子树染色。

复杂度 $O(n\log{n})$。

Code

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
/* Code Information
* Author: little_skqliao
* Time: 2021-05-24 22:35:03
* Source: CF 1529 E
* Problem: https://codeforces.com/contest/1529/problem/E
**/

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fir first
#define sec second
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

int T, N;
vector<vector<int>> E, E2;
vector<int> St, En, Col, Lst, Num;
int cntD, ans, num;

void dfs(int x) {
St[x] = ++cntD;
for (auto v : E2[x]) dfs(v);
En[x] = cntD;
}

void pushUp(int rt) {
Num[rt] = Num[rt << 1] | Num[rt << 1 | 1];
}

void pushDown(int rt) {
if (Col[rt] == -1) return ;
Col[rt << 1] = Col[rt << 1 | 1] = Col[rt];
Col[rt] = -1;
}

int query(int rt, int l, int r, int p) {
if (l == r) return Col[rt];
int m = (l + r) >> 1;
pushDown(rt);
if (p <= m) return query(rt << 1, l, m, p);
else return query(rt << 1 | 1, m + 1, r, p);
pushUp(rt);
}

bool queryNum(int rt, int l, int r, int a, int b) {
if (a <= l && r <= b) return Num[rt];
int m = (l + r) >> 1, ans = 0;
if (a <= m) ans |= queryNum(rt << 1, l, m, a, b);
if (m < b) ans |= queryNum(rt << 1 | 1, m + 1, r, a, b);
return ans;
}

void update(int rt, int l, int r, int a, int b, int x) {
if (a <= l && r <= b) {
Col[rt] = x;
Num[rt] = x > 0;
return ;
}
pushDown(rt);
int m = (l + r) >> 1;
if (a <= m) update(rt << 1, l, m, a, b, x);
if (m < b) update(rt << 1 | 1, m + 1, r, a, b, x);
pushUp(rt);
}

void add(int x) {
int y = query(1, 1, N, St[x]);
if (y > 0) {
--num;
update(1, 1, N, St[y], En[y], 0);
Lst[x] = y;
}
if (!queryNum(1, 1, N, St[x], En[x])) {
update(1, 1, N, St[x], En[x], x);
++num;
}
}

void sub(int x) {
--num;
update(1, 1, N, St[x], En[x], 0);
if (Lst[x]) {
++num;
update(1, 1, N, St[Lst[x]], En[Lst[x]], Lst[x]);
Lst[x] = 0;
}
}

void dfs2(int x) {
add(x);
chkMax(ans, num);
for (auto v : E[x]) dfs2(v);
sub(x);
}

void init() {
E.assign(N + 1, {});
E2.assign(N + 1, {});
St.assign(N + 1, 0);
En.assign(N + 1, 0);
Lst.assign(N + 1, 0);
Col.assign(N << 2, -1);
Num.assign(N << 2, 0);
num = ans = cntD = 0;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--) {
cin >> N;
init();
for (int i = 2, x; i <= N; ++i) {
cin >> x;
E[x].push_back(i);
}
for (int i = 2, x; i <= N; ++i) {
cin >> x;
E2[x].push_back(i);
}
dfs(1);
dfs2(1);
cout << ans << endl;
}
return 0;
}