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

不得不说,这场是真的真的良心!首先知识点覆盖全面,各种题目也都比较富有思维含量,大概是我打过的 Combined 场里面质量最高的一场。

然后就 vp 了一整场,最后的战绩大概还不错?

一共有 $9$ 道题目。

上面那个是托神。最后 rush 了一个 $\rm G1$ ,结果把 $y$ 写成 $x$ 就挂了。结束之后 $3\sim 5\min$ 左右就过掉了吧。

[A] Paint the Numbers

给出一个长度为 $n$ 的序列 $a_1,a_2,a_3,… ,a_n$,要求你使用最少的颜色对每个染色。对于任何颜色,满足:染成该颜色的数都能被染成该颜色的最小数整除。

$1\leq n\leq 100$ 。

不难知道要排个序之后,对每个数扫一下它的倍数打上标记。最后没有被标记的就是最少的色数。

不过想了一下,如果 $a_i$ 在 $10^6\sim 10^7$ 左右,那么是可以 $O(nd(n))$ 做的。

[B] Koala and Lights

有 $n$ 盏灯,给定初始状态 。
第 $i$盏灯 $a_i,a_i+b_i,a_i+2\times b_i,a_i+3\times b_i\cdots$ 时刻被切换状态 。
求 同一时刻亮的灯数 的最大值。
$n\leq 100,a_i,b_i\leq 5$ 。

一开始觉得又是什么奇怪的 exgcd 题。然后发现 $a_i,b_i\leq 5$ 。于是就可以暴力上 $100$ 万天去找最大值。

一开始因为调试,把天数设置为了 $20$ 导致挂了一发= =。

[C] Paint the Digits

给定一个数字字符串 $s$。把它分割为两个子序列(可以不连续)。满足把第二个子序列接在第一个子序列之后形成的数字串不降

$1\leq n\leq 10^6$ .

一开始猜了一个把 LIS 找出来就完了。然后发现假的离谱。然后就考虑观察性质,发现如果存在合法答案,那么对于一个 $i$ 如果位置不变,会有 $1\sim i-1$ 都 $\leqslant i$ 。不难发现这是个十分强的必要条件。于是可以这么把答案取出来,然后去 check 一下充分性就好了。复杂度线性。

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

#include <vector>

#include <cstring>

#include <algorithm>

const int N = 301000 ;

using namespace std ;

int n, T ;
int maxc ;
int maxv ;
int res[N] ;
int ans[N] ;
int base[N] ;
bool vis[N] ;
vector <int> ans1, ans2 ;

int main(){
scanf("%d", &T) ;
while (T --){
scanf("%d", &n) ;
maxv = maxc = 0 ;
ans2.clear() ; ans1.clear() ;
memset(vis, 0, sizeof(vis)) ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%1d", &base[i]) ;
for (int i = 1 ; i <= n ; ++ i)
if (maxv > base[i])
vis[i] = 1, maxc = max(base[i], maxc) ;
else maxv = std :: max(maxv, base[i]) ;
for (int i = 1 ; i <= n ; ++ i){
if (vis[i] || base[i] < maxc)
ans1.push_back(i) ;
else ans2.push_back(i) ;
}
int cnt = 0 ;
for (auto k : ans1) ans[k] = 1, res[++ cnt] = base[k] ;
for (auto k : ans2) ans[k] = 2, res[++ cnt] = base[k] ;
// for (int i = 1 ; i <= n ; ++ i) printf("%d ", res[i]) ; puts("") ;
for (int i = 1 ; i <= n ; ++ i)
if (res[i] < res[i - 1]) goto cc ;
for (int i = 1 ; i <= n ; ++ i)
printf("%d", ans[i]) ; puts("") ; continue ;
cc : puts("-") ;
}
}

[D] Cow and Snacks

$n$ 种花,$k$ 个客人,每个人喜欢两种编号不同的花。但是每种花在花店里只有一束。

客人按顺序进入花店,会买走所有她喜欢且仍在店铺里的花。如果一个客人买不到任何一束花,那么她就会十分沮丧导致变成肥宅。现在你可以自己安排这 $n$ 个人的顺序,使得肥宅的数量最小。

$1\leq n,k\leq 3\times 10^5$ 。

我就是传说中的图论黑洞吗,这题捣鼓了好久好久 = =

大概就是说,考虑每一次客人可能会买走 $1$ 或者 $2$ 种花。考略用图论模型去刻画买花这件事情。考虑可以把花当做点,客人每次就是要删去 $(x_i,y_i)$ 这条边的两个端点,而一条边 $(x,y)$ 可以被删当且仅当存在一个端点没有被删掉。于是可以发现,如果一个连通块大小为 $B$,那么至多只会有 $B-1$ 个客人可以不沮丧。

考虑用并查集实现这个过程。那么并查集中的边数即为 $\sum (B-1)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int cnt ;
int fa[N] ;
int n, k, ans ;

int find(int x){
if (fa[x] == x) return x ;
return fa[x] = find(fa[x]) ;
}
void merge(int x, int y){
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 != f2){
++ cnt ;
fa[f1] = f2 ;
}
}
int main(){
cin >> n >> k ; int x, y ;
for (int i = 1 ; i <= n ; ++ i) fa[i] = i ;
for (int i = 1 ; i <= k ; ++ i)
cin >> x >> y, merge(x, y) ;
printf("%d\n", k - cnt) ; return 0 ;
}

[E1] Rotate Columns (easy version)

给定一个 $n×m$ 的矩阵,你可以对每一列进行若干次循环移位。

求操作完成后每一行的最大值之和最大是多少。

$1\leq n\leq 4,1\leq m\leq 100$ 。

大概是需要先起手找一波性质。

发现「每行取最大值」可以转化成每行取一个数,因为根据 max 的结合律这个最大值的限制属实没用。然后就可以设 $f_{i,s}$ 表示考虑了前 $i$ 列,每一行的取数状态为 $s$ 时答案的 max。转移就可以直接枚举子集转移。需要注意的是列是允许循环移位的,所以在预处理 sum[s] 时要考虑到这一点。

于是最后的复杂度就是 $O(T\cdot m\cdot 3^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
int T, s ;
int n, m ;
int Id[S] ;
int sum[S] ;
int f[N][S] ;
int row[N][M] ;

const int I = 1000000007 ;

void out_p(int x){
while (x){
if (x & 1)
putchar('1') ;
else putchar('0') ;
x >>= 1 ;
}
putchar(' ') ;
}

int main(){
for (int i = 0 ; i <= 12 ; ++ i)
Id[1 << i] = i + 1 ; cin >> T ;
while (T --){
cin >> n >> m ;
s = (1 << n) - 1 ;
memset(f, -63, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
cin >> row[j][i] ; f[0][0] = 0 ;
for (int i = 1 ; i <= m ; ++ i){
for (int p = 1 ; p <= s ; ++ p){
sum[p] = sum[p - (p & -p)] + row[i][Id[(p & -p)]] ;
// printf("%d %d\n", p, sum[p]) ;
}
for (int p = 1 ; p <= s ; ++ p)
for (int o = 0 ; o < n ; ++ o){
int q = ((p >> o) | (p << (n - o))) & s ;
// out_p(p), out_p(q), puts("") ;
sum[p] = max(sum[p], sum[q]) ;
}
f[i][0] = f[i - 1][0] ;
for (int p = 1 ; p <= s ; ++ p){
f[i][p] = f[i - 1][p] ;
for (int q = p ; q ; q = (q - 1) & p)
f[i][p] = max(f[i][p], f[i - 1][p ^ q] + sum[q]) ;
}
// printf("%d %d\n", s, f[i][s]) ;
}
printf("%d\n", f[m][s]) ;
}
return 0 ;
}

[E2] Rotate Columns (hard version)

$n\leq 12,m\leq 2000$ 。

发现上面那个复杂度要通过有点困难,算了一波大概是 $40\times 531441\times 2000>10^{10}$ …

然后考虑需要猜一个结论。就是一定会存在某些列是根本不会对答案有贡献的,且这些列的数量是 $m-n$ 。那么考虑如果存在某一列,该列的最大值 $c$ 在所有列中排名 $>n$ ,那么由于可以循环移位,可以知道答案一定不在这一列。于是就可以排个序,复杂度就变成了 $O(T\times n\times 3^n)$,大概是 $40\times 531441\times 12<2.5e8$ ,可以通过本题。

[F] Koala and Notebook

定义一条路径的权值为路径上所有边的编号直接相连所得到的十进制数字的大小 。

求 $1$ 到每个点的最短路 $\pmod{10^9+7}$ 。

$1\leq n,m\leq 100000$。

这题是真的有趣。虽然场上并没有去写(感觉写了也是不可能过的)。

一开始觉得「难道不是把出边 xjb 排个序就做完了嘛」。然后发现被叉了,心情郁闷(x

考虑如何比较「编号相连得到的十进制数」的大小,那必然是先比较位数,再从头开始比较权值。于是就有个特别强的建图技巧:拆边。考虑把一条编号为 $(\overline{a_1a_2\cdots a_k})_{10}$ 的边拆成两条有向链,链上的边的边权分别为 $a_1,a_2\cdots a_k$。

然后考虑进行类似分层图的 BFS。这个分层图的细节很丰富:

0、分层的目的是,控制遍历顺序,使得 BFS 的最优性也在当前问题中体现。即使得对于每个点,最先被遍历时一定是最短路。

1、首先要先忽略边权进行分层。

2、其次考虑如果存在多条出边,必然是走权最小的那条边。

3、只符合上面两条还是不对的。因为考虑如果某个点 $t$ 有两条入边 $e_1,e_2$ 满足 $val(e_1)<val(e_2)$,他们在 BFS 树上的深度相同,那么如果单纯按点来转移,可能会出现先走 $e_2$ 再走 $e_1$ 的情况,而此时 $t$ 已经被更新完毕就会导致出错。所以还要按照边权从 $0$ 到 $9$ 进行再分层。

可以知道这样做最后复杂度一定不会超过 $O(10\times m)$ 。

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
int ob ;
int cnt ;
int n, m ;
int arr[M] ;
int f[N] ;
int g[N] ;
int T ;

vector <int> q[N] ;
vector <int> E[N][10] ;

int main(){
cin >> n >> m ;
int x, y, z ; cnt = n ;
for (int i = 1 ; i <= m ; ++ i){
x = qr(), y = qr() ; ob = 0 ; z = i ;
while (z) arr[++ ob] = z % 10, z /= 10 ; z = x ;
for (int j = ob ; j > 1 ; -- j)
E[x][arr[j]].push_back(++ cnt), x = cnt ;
E[x][arr[1]].push_back(y) ;
for (int j = ob ; j > 1 ; -- j)
E[y][arr[j]].push_back(++ cnt), y = cnt ;
E[y][arr[1]].push_back(z) ;
}
g[1] = T = 1 ;
q[1].push_back(1) ;
for (int d = 1 ; d <= T ; ++ d){
// if (!q[d].size()) break ;
for (z = 0 ; z < 10 ; ++ z){
auto t = q[d].begin() ;
while (t != q[d].end()){
x = *t ;
for (auto y : E[x][z]){
if (g[y]) continue ;
f[y] = (f[x] * 10ll + z) % P ;
g[y] = 1, q[T + 1].push_back(y) ;
}
++ t ;
}
if (q[T + 1].size()) ++ T ;
}
}
for (int i = 2 ; i <= n ; ++ i)
printf("%d\n", f[i]) ; return 0 ;
}

[G1] Into Blocks (easy version)

感觉这个 G1 还是比较 naive 的?

给你 $n~q$,$n$表示序列长度,$q$表示操作次数,在该题中 $q$ 等于 0 。

我们需要达成这么一个目标状态:

如果存在 $x$ 这个元素,那么必须满足所有 $x$ 元素都必须在序列中连续。

可以进行这么一种操作:

将所有的 $x$ 元素的变为任意你指定的 $y$ 元素,并且花费 $cnt_x$ 的花费,$cnt_x$代表 $x$ 元素的个数。

求最小花费使得序列满足目标状态。

大概做题时有这么几个 Observation,当时拿笔写了下来,感觉应该是比较正常思路:

1、答案上界一定是 $n-\max \{col{\rm num}\}$ .

2、如果一个颜色存在不相邻,那么要么会被全部涂成别的颜色,要么会被保留。

3、根据 $2$ 不难发现,一段交错排布的元素最后必然只会保留一种颜色。

4、根据 $3$ 可以得到一个贪心:将所有颜色按照出现次数从大到小排序。一开始预处理出所有颜色第一次出现的位置 $s_i$ 和最后一次出现的位置 $t_i$,那么不难看出要把 $[s_i,t_i]$ 之间的元素都涂成当前颜色。不难知道这样是最优的。

然后实现上遇上了一点小阻碍。大概就是说随着不停地染色,可能会有一些别的颜色被染成当前颜色,这样就要动态更新当前颜色的 $s_i$ 和 $t_i$ 。然后就因为觉得这个不好维护就摸了一会儿…结果发现其实是很好维护的。具体来说,从大到小做一定可以让每个点至多被染一次色,复杂度可以保证;同时发现 $[s_i,t_i]$ 分别满足单调性,就可以暴力 while 做了。

最后复杂度显然排序外线性。

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
 
int ans ;
int cnt ;
int n, q ;
int buc[N] ;
int fst[N] ;
int lst[N] ;
int vis[N] ;
int base[N] ;
pint ord[N] ;
vint pos[N] ;

#define m_k make_pair

bool comp(pint a, pint b){
return a.fr == b.fr ? a.sc < b.sc : a.fr > b.fr ;
}

int main(){
cin >> n >> q ; int x, y ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), buc[base[i]] ++ ;
for (int i = 1 ; i <= n ; ++ i)
pos[base[i]].push_back(i) ;
for (int i = 1 ; i <= n ; ++ i)
if (!fst[base[i]]) fst[base[i]] = i ;
for (int i = n ; i >= 1 ; -- i)
if (!lst[base[i]]) lst[base[i]] = i ;
for (int i = 1 ; i <= 200000 ; ++ i)
if (buc[i]) ord[++ cnt] = m_k(buc[i], i) ;
sort(ord + 1, ord + cnt + 1, comp) ;
for (int i = 1 ; i <= cnt ; ++ i){
x = ord[i].fr ; y = ord[i].sc ;
if (vis[y]) continue ; vis[y] = 1 ;
if (x == lst[y] - fst[y] + 1) continue ;
int l = fst[y], r = lst[y] ;
for (int p = fst[y] ; p <= lst[y] ; ++ p){
// printf("%d ", p) ;
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
// printf("%d ", base[p]) ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
// puts("") ;
}
// printf("%d %d\n", l, r) ;
while (1){
int tl, tr ;
// printf("%d %d\n", l, r) ;
tl = fst[y], tr = lst[y] ;
if (l == fst[y] && r == lst[y]) break ;
fst[y] = l, lst[y] = r ;
for (int p = tl - 1 ; p >= l ; -- p){
// printf("(%d %d %d)", p, base[p], vis[base[p]]) ;
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
// printf("%d ", base[p]) ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
// puts("") ;
}
for (int p = tr + 1 ; p <= r ; ++ p){
if (base[p] != y && !vis[base[p]]){
vis[base[p]] = 1 ;
for (auto k : pos[base[p]]){
chkmin(l, k) ;
chkmax(r, k) ;
base[k] = y, ++ ans ;
}
}
}
}
// debug(base, 1, n) ;
// printf("%d %d %d %d %d\n", x, y, fst[y], lst[y], ans) ;
}
printf("%d\n", ans) ;
return 0 ;
}

把最后一个 for 里 if 的 y 写成了 x 导致 Wa On 7 呜呜呜。

[G2] Into Blocks (hard version)

$q=3\times 10^5$ 。

这题是真的🐂🍺!是十分有趣、十分强的题目!

但是类似套路并不是没有见过。曾经写过一篇博客总结了一下「兔队线段树」,这题大概是需要用到那里面 T1 的类似 trick。

大概首先是要对上面那个 easy version 的一些结论进行形式化的提炼和总结。考虑答案的本质。考虑把一个颜色 $c$ 的出现区间化成左开右闭的形式 $[s_c,t_c)$,意思是对于区间中的每个 $i$ ,要把 $i,i+1$ 涂成一个颜色。那么可以发现如果对所有 $c$ 的该区间进行区间 $+1$ ,那么最后可以保留的颜色数就是相邻两个 $0$ 之间出现最多的颜色的数量和。正确性显然。…但这个转化确实十分神奇。

考虑用线段树快速维护这个东西。考虑需要维护什么信息:

1、需要维护分界点。即区间中被覆盖次数为 $0$ 的点。

2、需要维护颜色数。即区间中出现次数最多的颜色。

3、但是 $2$ 中有要求,要求必须是连续段中出现次数最多的颜色。而这个连续段的「连续」对应于一段连续的、覆盖次数 $>0$ 的段。

4、注意到要维护区间中出现次数的最大值,还要求连续且只有全局询问的话,有个小技巧。考虑让颜色 $c$ 的出现次数 $e(c)$ 放到 $s_c$ 处维护,记作 $w_{s_c}$,这样就只需要维护一个 $\max \{w_i,w_{i+1}\}$ 状物。

发现难以维护分界点?但是考虑到只有全局询问,于是可以借鉴兔队线段树里那个类似的思想。具体来说,发现对于线段树的根节点,有效信息是区间 $[1,n]$ ,而 $n$ 这个点必然不会被任何一个线段覆盖,也就是说如果统计全局信息,那么必然会存在 $n$ 为 $0$。那么就好办了,考虑用维护「区间最小值」来代替维护「区间分界点」。

具体细节方面,考虑维护区间中每段里颜色出现次数最大值 ${\rm seg}_x$,左/右端点所在连续区间的最大值 $\mathrm{lmax}_x,\mathrm{rmax}_x$ 。转移时考虑两个区间的 $\min v$ 的关系,其中 $v$ 是覆盖次数。

然后考虑修改操作,发现就是一个区间加再加一个单点维护。注意当 $l=r$ 时,有些量不是良定义,当作不知道就好了(赋值为 $0$) 。

注意到颜色的修改可以再单独拿一个 set 来维护。最终复杂度 $O(n\log n)$ 。

然后具体为什么能比 xyx 的做法少掉一个 log,个人认为是充分利用了『只有全局询问』这个性质。

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

#include <cstdio>

const int N = 200005 ;

#define _be begin
#define _en rbegin

#define era erase
#define ins insert

using namespace std ;

set <int> col[N] ;

int seg[N * 3] ;
int mnv[N * 3] ;
int mxt[N * 3] ;
int tag[N * 3] ;
int lcon[N * 3] ;
int rcon[N * 3] ;

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

inline void _down(int rt){
if (tag[rt]){
mnv[lc] += tag[rt] ;
mnv[rc] += tag[rt] ;
tag[lc] += tag[rt] ;
tag[rc] += tag[rt] ;
tag[rt] = 0 ;
}
}
inline void _up(int rt){
int ls = rt << 1 ;
int rs = rt << 1 | 1 ;
mxt[rt] = max(mxt[ls], mxt[rs]) ;
mnv[rt] = min(mnv[ls], mnv[rs]) ;
if (mnv[ls] < mnv[rs]){
seg[rt] = seg[ls] ;
lcon[rt] = lcon[ls] ;
rcon[rt] = max(mxt[rs], rcon[ls]) ;
//此处由于最后要覆盖,所以 max_Time(rc) 本质上就是包含右端点的值。
}
else if (mnv[ls] > mnv[rs]){
seg[rt] = seg[rs] ;
rcon[rt] = rcon[rs] ;
lcon[rt] = max(mxt[ls], lcon[rs]) ;
}
else {
lcon[rt] = lcon[ls] ; rcon[rt] = rcon[rs] ;
seg[rt] = seg[ls] + seg[rs] + max(lcon[rs], rcon[ls]) ;
}
}
void upd(int rt, int l, int r, int ul, int ur, int v){
if (ul > ur) return ;
if (ul <= l && r <= ur)
return mnv[rt] += v, void(tag[rt] += v) ;
int mid = (l + r) >> 1 ; _down(rt) ;
if (ul <= mid) upd(lc, l, mid, ul, ur, v) ;
if (ur > mid) upd(rc, mid + 1, r, ul, ur, v) ;
_up(rt) ;
}
void cov(int rt, int l, int r, int p, int v){
if (l == r)
return void(mxt[rt] = lcon[rt] = v) ;
int mid = (l + r) >> 1 ; _down(rt) ;
if (p <= mid) cov(lc, l, mid, p, v) ;
else cov(rc, mid + 1, r, p, v) ; _up(rt) ;
}
int n, q ;
int base[N] ;
void mdf(int c, int mk){
int w ;
if (!(w = col[c].size())) return ;
// printf("%d %d %d %d %d\n", c, mk, *col[c]._be(), *-- col[c]._en(), (int)col[c].size()) ;
cov(1, 1, n, *col[c]._be(), mk > 0 ? w : 0) ;
upd(1, 1, n, *col[c]._be(), *col[c]._en() - 1, mk) ;
}
int val_it(){ return n - seg[1] - lcon[1] - rcon[1] ; }

int main(){
int x, y, z ;
scanf("%d%d", &n, &q) ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), col[base[i]].ins(i) ;
for (int i = 1 ; i < N ; ++ i)
mdf(i, 1) ; printf("%d\n", val_it()) ;
while (q --){
scanf("%d%d", &x, &y) ; z = base[x] ;
mdf(z, -1) ; col[z].era(x) ; mdf(z, 1) ;
mdf(y, -1) ; col[y].ins(x) ; mdf(y, 1) ;
printf("%d\n", val_it()) ; base[x] = y ;
}
return 0 ;
}