【赛题整理】[Codeforces Round#502(Combined) A~G] 题解

这一场是 SD 的陈醉前辈和 lxl 一起合办的。感觉质量还是可以的?虽然感觉这场比赛唯一的亮点就在于 G…

A

就知道让中国人出这种A就会出奇怪的模拟题 233

B

需要点思考的题。大概就是考虑只有 $a$ 中形如 $0…1$ 对应 $b$ 中的一个 $0…0$ 或者 $0…1$ 才会产生贡献。然后就扫一下 $a$ 的每一位计个数就好了。

C

感觉这题就是十分的牛。

给定一个数 $n$ 。求构造一个长度为 $n$ 的排列,使之 $\rm LIS+LDS$ 最小。

一开始读题读成了最大值。然后随便画了画发现答案就是 $n+1$ emmm

然后读完了随便写了个奇怪的东西被轻松叉了,之后发现原来是个比较强的题。大概就是考虑 dilworth 定理,最长上升/下降子序列长度等于其反链的最多序列数。那么考虑如果是要算 LIS+LDS 之和的话,对于一个 LIS 的定长 $L$ ,根据 dilworth 定理必然会存在 $L$ 个反链,也就是 $L$ 个 DS 。于是可以知道最后有

即为了使 $L$ 个 DS 的最大长度最小,所以要尽量分的平均一点。那么可以知道这个 $L$ 应该取 $\sqrt n$ 。

那么之后就变成了如何构造一个 LIS 为 $\sqrt n$,LDS 为 $\left\lceil\dfrac{n}{\sqrt n}\right\rceil$ 的串。不难知道可以分段构造。

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
#include <cmath>
#include <cstdio>
#include <algorithm>

const int N = 300010 ;

int n, m ;
int ans[N] ;

int main(){
scanf("%d", &n) ;
m = std :: ceil(std :: sqrt(n)) ;
/*
if (n & 1){
ans[(n >> 1) + 1] = n ;
for (int i = 1 ; i <= n >> 1 ; ++ i) ans[i] = i ;
for (int i = (n >> 1) + 2 ; i <= n ; ++ i) ans[i] = n - i + ((n >> 1) + 1) ;
}
else {
for (int i = 1 ; i <= (n >> 1) ; ++ i) ans[i] = i ;
for (int i = (n >> 1) + 1 ; i <= n ; ++ i) ans[i] = n - i + ((n >> 1) + 1) ;
}
for (int i = 1 ; i <= n >> 1 ; ++ i) res[i] = ans[i + (n >> 1)] ;
for (int i = (n >> 1) + 1 ; i <= n ; ++ i) res[i] = ans[i - (n >> 1)] ;*/
int p = 0, q, k = n ;
for (int i = 1 ; i <= std :: ceil(1.0 * n / m) ; ++ i){
q = p ; for (int j = 1 ; j <= m && p < n ; ++ j) ans[++ p] = k -- ;
std :: reverse(ans + q + 1, ans + p + 1) ; // printf("%d %d %d\n", i, q + 1, p) ;
}
for (int i = 1 ; i <= n ; ++ i)
printf("%d ", ans[i]) ; return 0 ;
}

D

简单题。发现可以 $(2^n)^2$ 预处理之后,询问就可以 $\log $ 了。

E

计算几何题,跳了。

F

定义 $\text{exlog} _ f(p _ 1^{a _ 1}p _ 2^{a _ 2}…p _ k^{a _ 2}) = a _ 1 f(p _ 1) + a _ 2 f(p _ 2) + … + a _ k f(p _ k)$,其中 $f(x)=Ax^3+Bx^2+Cx+D$ ,求 $\sum _ {i=1} ^ n \text{exlog} _ f(i)$

$1 \le n \le 3 \times 10 ^ 8,0 \le A,B,C,D \le 10 ^ 6$ 。

时限 $5s$,空间限制 $16\rm Mib$ 。

首先要有个 Observation,大概就是说可以发现对于每个质数的幂次 $a_i$,作为乘法系数是独立的。所以会有 $\text{exlog}_f(a\cdot b)=\text{exlog}_f(a)+\text{exlog}_f(b)$ 。但是这样直接筛的复杂度并不能过,空间会爆。然后考虑如何优化这一过程。

大概是说可以考虑每个质因数产生的贡献,彼此之间是线性无关的 ,所以可以分别考虑每个质数幂的贡献。具体的,我们只需要求出所有的质数以及质数的幂对答案的贡献就好了,这部分为了卡空间可以用埃氏筛。

但是发现还是过不去。因为埃氏筛的复杂度太高了。不过仔细分析一波,发现慢在诸如 $2,3,5,7$ 这种比较小的质因子 $p$,会进行 $\left\lfloor\dfrac{n}{p}\right\rfloor$ 次筛除操作。于是可以先暴力跑出 $2,3,5,7$ 的贡献,然后算其他的时就可以不考虑这些数了。

但是发现这样空间还是会有点问题。于是可以用 bitset + 合并状态来压缩。合并状态的原理是刨除了所有 $2,3$ 的倍数之后,空间就可以只开 $\dfrac{1}{3}$ 。

个人觉得这题能放到 F,唯一的原因就是因为需要十分优秀的卡常 and 卡空间技术。

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
#include <bitset>

#include <cstdio>

const int N = 100000005 ;

using std :: bitset ;

typedef long long ll ;

typedef unsigned int lint ;

int n ;
bitset <N> vis ;
int A, B, C, D ;

lint ans ;

inline bool chk(int x){
return ((!(x & 1)) || (x % 3 == 0) || (x % 5 == 0)) ;
}
lint calc(int p){
return 1u * A * p * p * p + 1u * B * p * p + 1u * C * p + D ;
}
lint solve(int p){
lint ret = 0, v = calc(p) ;
for (ll x = p ; x <= n ; x *= p)
ret += 1u * (n / x) * v ; return ret ;
}
int main(){
scanf("%d", &n) ; ans = 0 ;
scanf("%d%d%d%d", &A, &B, &C, &D) ;
if (n >= 2) ans += solve(2) ;
if (n >= 3) ans += solve(3) ;
if (n >= 5) ans += solve(5) ;
for (int i = 7 ; i <= n ; ++ i){
if (chk(i)) continue ;
if (vis[i / 3]) continue ; ans += solve(i) ; //printf("%u\n", ans) ;
for (int j = i + i ; j <= n ; j += i)
if (!chk(j)) vis[j / 3] = 1 ;
}
printf("%u\n", ans) ; return 0 ;
}

G

这是真神题。

给定一棵树,维护以下 $3$ 个操作:

(1)1 x 表示如果节点 $x$ 为白色,则将其染黑。否则对这个节点的所有儿子递归进行相同操作。

(2)2 x表示将以节点 $x$ 为 $root$ 的子树染白。

(3)3 x表示查询节点 $x$ 的颜色

$1\leq n\leq 10^5$ 。

首先观察发现,操作的复杂度向修改倾斜,即询问复杂度比较低,可以考虑询问的时候搞点事情。

考虑 $(1)$ 操作的本质。因为要向询问倾斜,所以考虑如果某个点 $z$ 会被 1 x 影响到 ,那么必然有 $x\sim z$ 这条路径上除了 $x$ 之外的所有点都已经被染黑了。

考虑忽略 $(2)$ 操作时,如何通过维护权值实现这个事情。一开始将全部的点权设为 $0$,每次 $(1)$ 操作就是对该点进行单点 $+1$ 。这样询问就可以考虑询问 $root\to x$ 这条路径上,是否存在一个后缀 $(s,x)$ 的权和等于 $(s,x)$ 的长度。这样直接做本质上是一个树链上的线段树二分,但其实可以用一个比较传统的技巧优化这个过程,即差分。考虑把每个点的初始点权设为 $-1$ ,这样就是询问是否存在一个后缀,其和 $\geqslant 0$ 。这个可以通过维护链上的最大后缀和来做,写起来简单一些。

然后考虑加上 $(2)$ 操作后如何快速维护。发现 $(2)$ 操作的本质是让整棵子树的点权均变为 $-1$ 。但这还不够,因为 $(2)$ 本质上是强制让某个点 $x$ 变成白色,而上面那个做法本质上是对修改离线,最后再分别确定每个修改对答案的贡献。不过也有比较简单的解决方式,即让 2 x 中的 $x$ 单点减一个权值 $v$ ,使得 $root\to x$ 上的最大后缀和也为 $-1$ 。不难发现 $v=qry(x)+1$ 。

于是最后就可以用 $n\log ^2n $ 的复杂度解决这个问题了。

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
#include <cstdio>

#include <vector>

#include <cstring>

#define p_b push_back

using std :: max ;
using std :: min ;
using std :: vector ;

const int N = 300010 ;

int ans ;
int cnt ;
int n, q ;
int sz[N] ;
int fa[N] ;
int _id[N] ;
int dfn[N] ;
int son[N] ;
int dep[N] ;
int top[N] ;

vector <int> E[N] ;

void dfs1(int x, int da){
dep[x] = dep[da] + 1 ;
sz[x] = 1, fa[x] = da ;
for (auto y : E[x]){
if (y == da) continue ;
dfs1(y, x) ; sz[x] += sz[y] ;
if (sz[y] > sz[son[x]]) son[x] = y ;
}
}
void dfs2(int x, int tp){
top[x] = tp ; ++ cnt ;
_id[dfn[x] = cnt] = x ;
if (son[x])
dfs2(son[x], tp) ;
for (auto y : E[x])
if (y != fa[x] && y != son[x]) dfs2(y, y) ;
}

int seg[N * 3] ;
int val[N * 3] ;
int tag[N * 3] ;

#define lc (rt << 1)
#define rc (rt << 1 | 1)

void _up(int rt){
seg[rt] = seg[lc] + seg[rc] ;
val[rt] = max(val[rc], val[lc] + seg[rc]) ;
}
void _down(int rt, int l, int r){
if (!tag[rt]) return ;
int mid = (l + r) >> 1 ;
seg[rc] = - (r - mid) ;
seg[lc] = - (mid - l + 1) ;
val[lc] = -1, val[rc] = -1 ;
tag[rc] = tag[lc] = 1, tag[rt] = 0 ;
}
void build(int rt, int l, int r){
if (l == r)
return void(seg[rt] = val[rt] = -1) ;
int mid = (l + r) >> 1 ;
build(rc, mid + 1, r) ;
build(lc, l, mid) ; _up(rt) ;
}
void upd(int rt, int l, int r, int p, int v){
if (l == r){
seg[rt] += v ;
val[rt] += v ;
return void() ;
}
_down(rt, l, r) ;
int mid = (l + r) >> 1 ;
if (p <= mid) upd(lc, l, mid, p, v) ;
else upd(rc, mid + 1, r, p, v) ;
_up(rt) ;
}
void cov(int rt, int l, int r, int cl, int cr){
if (cl <= l && r <= cr){
seg[rt] = - (r - l + 1) ;
val[rt] = -1 ; return void(tag[rt] = 1) ;
}
int mid = (l + r) >> 1 ; _down(rt, l, r) ;
if (cr > mid) cov(rc, mid + 1, r, cl, cr) ;
if (cl <= mid) cov(lc, l, mid, cl, cr) ; _up(rt) ;
}
int sum(int rt, int l, int r, int ql, int qr){
if (ql <= l && r <= qr) return seg[rt] ;
int mid = (l + r) >> 1, ret = 0 ; _down(rt, l, r) ;
if (ql <= mid) ret += sum(lc, l, mid, ql, qr) ;
if (qr > mid) ret += sum(rc, mid + 1, r, ql, qr) ;
return ret ;
}
int qry(int rt, int l, int r, int ql, int qr){
_down(rt, l, r) ;
if (ql <= l && r <= qr) return val[rt] ;
int mid = (l + r) >> 1, ret = - n ; _down(rt, l, r) ;
if (ql <= mid) ret = max(ret, qry(lc, l, mid, ql, qr)) ;
if (qr > mid) ret = max(ret + sum(rc, mid + 1, r, ql, qr), qry(rc, mid + 1, r, ql, qr)) ;
return ret ;
}
int Q(int x){
int ret, v = 0 ;
ret = -(n + 1) ;
while (top[x] > 1){
ret = max(ret, v + qry(1, 1, n, dfn[top[x]], dfn[x])) ;
v += sum(1, 1, n, dfn[top[x]], dfn[x]) ; x = fa[top[x]] ;
}
// printf("%d\n", qry(1, 1, n, dfn[top[x]], dfn[x])) ;
ret = max(ret, v + qry(1, 1, n, 1, dfn[x])) ; return ret ;
}
int main(){
scanf("%d%d", &n, &q) ; int x, z ;
for (int y = 2 ; y <= n ; ++ y)
scanf("%d", &x), E[x].p_b(y), E[y].p_b(x) ;
dfs1(1, 0) ; dfs2(1, 1) ; build(1, 1, n) ;
// for (int i = 1 ; i <= n ; ++ i) printf("%d%c", top[i], " \n"[i == n]) ;
// printf("%d %d\n", i, sz[i]) ;
while (q --){
scanf("%d%d", &z, &x) ;
if (z == 1) upd(1, 1, n, dfn[x], 1) ;
else if (z == 2){
cov(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) ;
upd(1, 1, n, dfn[x], - Q(x) - 1) ;
}
else if (z == 3){
// printf("%d\n", Q(x)) ;
ans = (bool)(Q(x) >= 0) ;
puts(ans ? "black" : "white") ;
}
// for(int p=1;p<=3 * n;++p)printf("%d%c", val[p], " \n"[p == 3 * n]);
}
return 0 ;
}