2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020)

对这场的记忆仅限于我的大分类讨论了。

[A Archeologists]

solution

题面:给出 $n$ 个数 $a_i$,构造 $p_i\geq 0$,使得 $|p_i-p_{i-1}|\leq 1$,且 $\sum p_ia_i$ 最大。

做法:一眼积木游戏。直接差分 $p_i$,转换为 $|p_i|\leq 1,\sum p_i\geq 0$,且 $\sum a_i\sum_{j=1}^i p_j$ 最大。再改写一下,要使 $\sum p_i\sum_{j=i}^n a_j$ 最大。直接拿个堆对这东西贪心就行了,时间复杂度 $O(n\log n)$。

[B Reverse Game]

solution

题面:给一个 $01$ 串,两个人,每次操作都可以翻转字符串中的 $10,110,100,1010$,问谁先不能进行操作就输了。

做法:最终结果一定是左边全 $0$,右边全 $1$。考虑逆序对。发现这四个串对逆序对的改变量只有 $1,2$,是不会改变模 $3$ 的结果的。于是只要开局模 $3$ 为零就先手必输,否则必胜。(因为我存在一种策略使得每次模 $3$ 都为 $0$ )。时间复杂度 $O(n)$。

[C 3-colorings]

solution

题面:

做法:

[D Disk Sort]

solution

题面:$n+1$ 个柱子,前 $n$ 个柱子上都有 $3$ 个盘子,颜色分别为 $1\backsim n$,且每种颜色恰好三个盘子。每个柱子最多只能放三个盘子,每次只能移动最顶上的到另一个顶上,现要将颜色一样的盘子都放在一个柱子上,且保证最后一个柱子为空,求构造方案,移动次数不超过 $6n$。

做法:来了,大讨论题。每次找一个柱子最顶上的盘子,把和它颜色一样都放在一起。经过分类讨论,发现每种情况都最多六步,而摆完 $n-1$ 个就等于摆完 $n$ 个,于是再将第 $n+1$ 个柱子搬空即可。时间复杂度 $O(n^2)$。

具体讨论就是,比如相同颜色是否在三个不同柱子上,分别在第几层之类的,这可以看我代码了,讲起来太累了。

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
int n;
int a[N][4];
int blank;
vector<Pair> ans;
int main(){
n=read(),blank=n+1;
for(res i=1;i<=3;i++)for(res j=1;j<=n;j++)a[j][i]=read();
for(res T=1;T<=n;T++){
res i;
for(i=1;i<=n+1;i++){
if(i==blank)continue;
if(a[i][1]==a[i][2]&&a[i][2]==a[i][3])continue;
break;
}
if(i==n+2)break;
res v=a[i][1];
Pair p=mp(0,0),q=mp(0,0);
for(res j=i;j<=n+1;j++){
for(res k=1;k<=3;k++){
if(a[j][k]==v){
if(j==i&&k==1)continue;
if(!p.fi)p=mp(j,k);
else q=mp(j,k);
}
}
}
if(i!=p.fi&&p.fi!=q.fi&&i!=q.fi){
if(p.se>q.se)swap(p,q);
if(p.se==1&&q.se==1){
ans.pb(mp(i,blank)),ans.pb(mp(p.fi,blank)),ans.pb(mp(q.fi,blank));
ans.pb(mp(q.fi,i)),ans.pb(mp(q.fi,p.fi));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][1]=a[q.fi][2],a[p.fi][1]=a[q.fi][3];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
else if(p.se==1&&q.se==2){
ans.pb(mp(i,blank)),ans.pb(mp(p.fi,blank));
ans.pb(mp(q.fi,i)),ans.pb(mp(q.fi,blank)),ans.pb(mp(q.fi,p.fi));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][1]=a[q.fi][1],a[p.fi][1]=a[q.fi][3];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
else if(p.se==1&&q.se==3){
ans.pb(mp(i,blank)),ans.pb(mp(p.fi,blank));
ans.pb(mp(q.fi,i)),ans.pb(mp(q.fi,p.fi)),ans.pb(mp(q.fi,blank));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][1]=a[q.fi][1],a[p.fi][1]=a[q.fi][2];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
else if(p.se==2&&q.se==2){
ans.pb(mp(i,blank)),ans.pb(mp(p.fi,i));
ans.pb(mp(p.fi,blank)),ans.pb(mp(q.fi,p.fi));
ans.pb(mp(q.fi,blank)),ans.pb(mp(q.fi,p.fi));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][1]=a[p.fi][1],a[p.fi][2]=a[q.fi][1];
a[p.fi][1]=a[q.fi][3];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
else if(p.se==2&&q.se==3){
ans.pb(mp(i,blank)),ans.pb(mp(p.fi,i));
ans.pb(mp(p.fi,blank)),ans.pb(mp(q.fi,p.fi));
ans.pb(mp(q.fi,p.fi)),ans.pb(mp(q.fi,blank));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][1]=a[p.fi][1],a[p.fi][2]=a[q.fi][1];
a[p.fi][1]=a[q.fi][2];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
else if(p.se==3&&q.se==3){
ans.pb(mp(p.fi,blank)),ans.pb(mp(p.fi,blank));
ans.pb(mp(i,p.fi)),ans.pb(mp(q.fi,blank));
ans.pb(mp(q.fi,i)),ans.pb(mp(q.fi,p.fi));
a[blank][3]=a[p.fi][1],a[blank][2]=a[p.fi][2];
a[blank][1]=a[q.fi][1];
a[i][1]=a[q.fi][2];
a[p.fi][1]=a[p.fi][2]=a[p.fi][3]=v;
blank=q.fi;
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=0;
}
}
else {
if(i==p.fi){
if(p.se==2&&q.se==1){
ans.pb(mp(i,blank)),ans.pb(mp(i,blank)),ans.pb(mp(q.fi,blank));
ans.pb(mp(i,q.fi));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=i,a[q.fi][1]=a[i][3];
a[i][1]=a[i][2]=a[i][3]=0;
}
else if(p.se==2&&q.se==2){
ans.pb(mp(i,blank)),ans.pb(mp(i,blank)),ans.pb(mp(q.fi,i));
ans.pb(mp(q.fi,blank)),ans.pb(mp(q.fi,i));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][2]=a[q.fi][1],a[i][1]=a[q.fi][3];
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==2&&q.se==3){
ans.pb(mp(i,blank)),ans.pb(mp(i,blank)),ans.pb(mp(q.fi,i));
ans.pb(mp(q.fi,i));ans.pb(mp(q.fi,blank));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=q.fi,a[i][2]=a[q.fi][1],a[i][1]=a[q.fi][2];
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==3&&q.se==1){
ans.pb(mp(i,blank)),ans.pb(mp(q.fi,blank)),ans.pb(mp(i,q.fi));
ans.pb(mp(i,blank));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=i,a[q.fi][1]=a[i][2];
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==3&&q.se==2){
ans.pb(mp(q.fi,blank)),ans.pb(mp(i,q.fi)),ans.pb(mp(i,blank));
ans.pb(mp(q.fi,i));ans.pb(mp(q.fi,i)),ans.pb(mp(q.fi,blank));
a[blank][3]=a[q.fi][1],a[blank][2]=a[i][2],a[blank][1]=a[q.fi][3];
a[i][1]=a[i][2]=a[i][3]=v;
blank=q.fi;
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==3&&q.se==3){
ans.pb(mp(q.fi,blank)),ans.pb(mp(q.fi,blank)),ans.pb(mp(i,q.fi));
ans.pb(mp(i,blank));ans.pb(mp(i,q.fi));
a[blank][3]=a[q.fi][1],a[blank][2]=a[q.fi][2],a[blank][1]=a[i][2];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=v;
blank=i;
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
}
else if(p.se==1&&q.se==2){
ans.pb(mp(q.fi,blank)),ans.pb(mp(q.fi,blank)),ans.pb(mp(i,blank));
ans.pb(mp(q.fi,i));
a[blank][1]=a[blank][2]=a[blank][3]=v;
a[i][1]=a[q.fi][3];
blank=q.fi;
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==1&&q.se==3){
res t=i;
i=p.fi,p=q,q=mp(t,1);
ans.pb(mp(i,blank)),ans.pb(mp(q.fi,blank)),ans.pb(mp(i,q.fi));
ans.pb(mp(i,blank));
a[blank][1]=a[blank][2]=a[blank][3]=v;
blank=i,a[q.fi][1]=a[i][2];
a[blank][1]=a[blank][2]=a[blank][3]=0;
}
else if(p.se==2&&q.se==3){
ans.pb(mp(i,blank)),ans.pb(mp(q.fi,i)),ans.pb(mp(blank,q.fi));
a[i][1]=a[q.fi][1];
a[q.fi][1]=a[q.fi][2]=a[q.fi][3]=v;
}
}
}
if(blank!=n+1){
ans.pb(mp(n+1,blank)),ans.pb(mp(n+1,blank)),ans.pb(mp(n+1,blank));
}
printf("%d\n",ans.size());
for(auto x:ans)printf("%d %d\n",x.fi,x.se);
return 0;
}

[E Divisible by 3]

solution

题面:定义区间 $[l,r]$ 的价值为 $\sum_{l\leq i<j\leq r} a_ia_j$,问序列 $a$ 有多少个子区间的价值是 $3$ 的倍数。

做法:直接 $\mathrm{dp}$,$f_{i,0/1/2,0/1/2}$ 表示结尾是 $i$ 价值是 $0/1/2$ 和是 $0/1/2$ 的区间个数,直接转移即可。时间复杂度 $O(9n)$。

[F Fence Job]

solution

题面:给出序列 $h_i$,保证数互不相同。每次可以选择一个区间 $[l,r]$,让这个区间的所有数都变成这个区间的最小数。问最终有几种区间?

做法:注意到每个数能改变的区间是固定的且互相包含或者不交的,所以考虑 $f_{i,j}$ 表示当前考虑到第 $i$ 个数,管辖到 $j$ 的方案数。转移就是考虑这个点能改变的区间,然后每个位置转移的都是前缀和。于是可以前缀和优化一下,时间复杂度就降到 $O(n^2)$ 了。

[G Simple Hull]

solution

题面:

做法:

[H AND = OR]

solution

题面:一个集合被称为好集合,当且仅当它可以分成两个集合,使得第一个集合的 $\mathrm{And}$ 和等于第二个集合的 $\mathrm{Or}$ 和。现给出一个序列,多次询问区间,问该区间是否是好集合。

做法:注意到一个是做与操作,一个是或操作,这两种操作可以说是两个极端的操作。因为一个全一才有一,一个全零才有零。

这启发我们考虑一个数有几个 $1$,枚举一个分界点 $k$,$1$ 的数量小于 $k$ 的放在或部分,大于的放在与部分。如果不这么放,比如把小于的放在与部分,那么与部分的 $1$ 的数量直接就会小于 $k$,这不是我们想要的。剩下来等于 $k$ 的可以发现要么都是一个数可以两边放,要么只能全部放到一边,这是容易证明的。这个东西直接暴力枚举 $k$,用线段树维护就是个主席树,时空复杂度 $O(n\log n\log A)$。

实际上,离线下来直接分治,考虑所有穿过中点的询问统一计算,暴力按右端点排序,剩下来的只用暴力维护中点起的后缀和,以及暴力枚举 $k$,这样的复杂度是 $O(n\log n+n\log n+n\log A)$。也即 $O(n\log)$,要快不少。

[I Modulo Permutations]

solution

题面:问长度为 $n$ 的满足 $p_i\mod p_{i+1}\leq 2$ 的排列数,其中 $p_{n+1}=p_1$。

做法:我感觉是可以 $O(1)$ 的,不过考场懒得搞了。

注意到 $1,2$ 只能是两个分段点,其余的都是递减,且是最多两步的递减。考虑一个简单的 $\mathrm{dp}$,$f_{i,j}$ 表示放置数字 $i\backsim n$,$1$ 的末尾是 $i$,$2$ 的末尾是 $j$,发现这个东西的转移是个调和级数,所以就是 $O(n\log n)$ 了。

[J One Piece]

solution

题面:

做法:

code
1
2


[K Codenames]

solution

题面:

做法:

[L Neo-Robin Hood]

solution

题面:你是劫富济自己的罗宾汉,有 $n$ 个富人,第 $i$ 个人有 $m_i$ 元财富,收买他需要 $p_i$ 元。对每个人你都可以选择

1.抢他,你获得 $m_i$ 元

2.不对他进行操作

3.花 $p_i$ 元收买他,他为你开脱你的一件抢劫罪行。

你有一个奇怪的目标:抢的人数越多越好,但是你的每一个罪行都必须被开脱。

问最多抢的人数。

做法:可以调整法证明一定在 $m_i+p_i$ 递减的情况中存在一个分界点。然后二分抢了几个人,枚举分界点,剩下来的就是两边的最小/最大 $k$ 个数的和,直接 priority_queue 维护下就好了。时间复杂度 $O(n\log^2 n)$。

[M Mistake]

solution

题面:$k$ 张一样的 $n$ 个点 $m$ 条边的 $\mathrm{DAG}$,给这 $k$ 个图都做一次拓扑排序,把这个 $k\cdot n$ 的数字排在一起,不改变同一个拓扑序里的顺序。现给出这 $k\cdot n$ 个数字,试构造 $k$ 张图的拓扑序,保证有解。

做法:注意到保证有解了,而一张图如果已经比另一张多走了一些点,那么另一张能走的这一张也一定能走。所以只需按当前数字的出现次数 $x$ 走第 $x$ 张图就好了,时间复杂度 $O(k\cdot n)$。