Codeforces Round 469 div2 题解(+bonuses!) | Bill Yang's Blog

Codeforces Round 469 div2 题解(+bonuses!)

再次补打。
由于Bonus的解答没有测试方法,因此可能有一定问题。若有发现,欢迎在下方评论区提出。

比赛地址
官方题解

Problem A. Left-handers, Right-handers and Ambidexters

题目大意

    有$l$个左撇子,用$r$个右撇子,有$a$个左右手都能熟练使用的人,将他们分配到一个组,使得能熟练使用左手和熟练使用右手的人数相同,求最大人数。

题目分析

3秒钟水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int l,r,a;
int main() {
l=Get_Int();
r=Get_Int();
a=Get_Int();
int Min=min(l,r),Max=max(l,r);
if(Max-Min>a)printf("%d\n",2*(Min+a));
else printf("%d\n",2*Max+(a-(Max-Min))/2*2);
return 0;
}

Bonus!

BONUS (easy): 在$O(1)$时间内解决该问题

That’s what I’ve actually done.

BONUS (easy): 读不懂

跳掉吧

Problem B. Intercepted Message

题目大意

    给出两个和相同的序列$A,B$,按照序列先后顺序将$A,B$分别分成若干子序列,使得$A,B$的子序列和对应相等,试最大化分出的子序列数量。

题目分析

从左往右双指针扫一遍,遇到相等就剖分。

代码

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
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=100005;
int n,m,a[maxn],b[maxn],ans=0;
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=a[i-1]+Get_Int();
for(int i=1; i<=m; i++)b[i]=b[i-1]+Get_Int();
int i=1,j=1,lasti=0,lastj=0;
while(i<=n&&j<=m) {
if(a[i]-a[lasti]==b[j]-b[lastj]) {
ans++;
lasti=i,lastj=j;
i++,j++;
} else if(a[i]-a[lasti]<b[j]-b[lastj])i++;
else j++;
}
printf("%d\n",ans);
return 0;
}

Bonus!

BONUS (easy): 若第二个序列丢失了一块,你可以在任意位置插入该块,询问不变

维护三个指针,第三个指针指向最靠左的差量大于等于该块和的位置。
若第一、二个指针相等了,将第三个指针移动到第二个指针。
若第一个指针与第三个指针刚好相差该块和了,在此处插入块,移除第三个指针。
由于两个序列加入块后和相等,因此块一定能找到地方插入。

Problem C. Zebras

题目大意

    定义$0,1$交替且开始结束均为$0$的串是斑马串,如$0,010,01010$是斑马串,而$1,0110,0101$均不是。
    将给定的串分为若干个序列(可以不连续),使得每个序列都是一个斑马串。
    若有多解,输出任意一个。若无解,输出$-1$。

题目分析

存储末尾为$0$与末尾为$1$的斑马串。
若当前位置是$0$,在末尾为$1$的斑马串中找一个接上去,或新开一个斑马串。
若当前位置是$1$,此时若没有末尾为$0$的斑马串就无解,否则选出一个末尾为$0$的斑马串接上去。

代码

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
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=200005;
string s;
vector<int> zero,one,L[maxn];
int main() {
ios::sync_with_stdio(false);
cin>>s;
for(int i=0; i<s.length(); i++)
if(s[i]=='0') {
if(one.empty()) {
zero.push_back(i+1);
L[i+1].push_back(i+1);
} else {
int x=one.back();one.pop_back();
L[x].push_back(i+1);
zero.push_back(x);
}
} else {
if(zero.empty()) {puts("-1");return 0;}
int x=zero.back();zero.pop_back();
L[x].push_back(i+1);
one.push_back(x);
}
if(!one.empty()) {puts("-1");return 0;}
printf("%d\n",zero.size());
for(int x:zero) {
printf("%d ",L[x].size());
for(int y:L[x])printf("%d ",y);
putchar('\n');
}
return 0;
}

Bonus!

BONUS (easy): 使输出方案最长的斑马串最短

每次在挑选串的时候选一个最短的斑马串即可,可以用堆什么的维护。

BONUS (hard): 使输出方案斑马串个数最少

这在搞笑,因为所有方案的斑马串个数均相同,等于$0$的个数$-1$的个数。

Problem D. A Leapfrog in the Array

题目大意

    有$n$个数,每两个数间隔一个放在长度为$2n-1$的格子中。
    每次移动最后一个数到其前面最靠近它的空位,最后铺满前$n$个格子。

    给出$n$,询问$q$次结束序列第$x$位的数。

题目分析

先敲个暴力压压惊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int a[105];
int main() {
int n=Get_Int();
for(int i=1; i<=n; i++)a[2*i-1]=i;
for(int i=2*n-1; i>n; i--)
for(int j=i-1; j>=1; j--)
if(!a[j]) {a[j]=a[i];break;}
for(int i=1; i<=n; i++)cout<<a[i]<<" ";
return 0;
}

然后找找规律。

$n=1$ $\color{red}1$
$n=2$ $\color{red}1$ $2$
$n=3$ $\color{red}1$ $3$ $\color{red}2$
$n=4$ $\color{red}1$ $3$ $\color{red}2$ $4$
$n=5$ $\color{red}1$ $5$ $\color{red}2$ $4$ $\color{red}3$
$n=6$ $\color{red}1$ $4$ $\color{red}2$ $6$ $\color{red}3$ $5$
$n=7$ $\color{red}1$ $6$ $\color{red}2$ $5$ $\color{red}3$ $7$ $4$

注意红色的项,也就是奇数项,始终不变,等于$\frac {x+1}2$。
现在考虑偶数项。

$n=1$ $1$
$n=2$ $\color{red}1$ $\color{red}2$
$n=3$ $\color{yellow}1$ $\color{yellow}3$ $\color{yellow}2$
$n=4$ $1$ $\color{red}3$ $2$ $\color{red}4$
$n=5$ $1$ $5$ $2$ $4$ $3$
$n=6$ $1$ $\color{yellow}4$ $2$ $\color{yellow}6$ $3$ $\color{yellow}5$
$n=7$ $e1$ $6$ $2$ $5$ $3$ $7$ $4$

$n$是偶数时,偶数项具有规律:如图,相同颜色的数对应大小关系相同。
即与$n=\frac n2$的对应项大小关系相同。

现在考虑$n$是奇数的情况:

$n=1$ $1$
$n=2$ $1$ $2$
$n=3$ $1$ $\color{red}3$ $\color{red}2$
$n=4$ $1$ $\color{yellow}3$ $\color{yellow}2$ $\color{yellow}4$
$n=5$ $1$ $\color{red}5$ $2$ $\color{red}4$ $3$
$n=6$ $1$ $4$ $2$ $6$ $3$ $5$
$n=7$ $e1$ $\color{yellow}6$ $2$ $\color{yellow}5$ $3$ $\color{yellow}7$ $4$

$n$是奇数时,偶数项具有规律:如图,相同颜色的数对应大小关系相同。
即与$n=\frac {n+1}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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
LL n,q;
int main() {
n=Get_Int();
q=Get_Int();
while(q--) {
LL x=Get_Int();
if(x&1)printf("%I64d\n",(x+1)>>1);
else {
LL pos=n-x+1,len=n;
while((len-pos+1)%2==0) {
pos=(pos+1)/2;
len=(len+1)/2;
}
pos=len-pos+1;
printf("%I64d\n",((pos+1)>>1)+n-len);
}
}
return 0;
}

Problem E. Data Center Maintenance

题目大意

    有$n$个数据库,有$m$种数据,一天有$h$小时。
    为了方便下载,每种数据$i$被存放在两个数据库($c_{i,1},c_{i,2}$)中。
    每个数据库$i$都有一个维护时间$u_i$,每天维护一小时。
    要求选出一个非空子集,使得这个子集中的数据库维护时间向后推迟一小时($u_i\leftarrow (u_i+1)\bmod h$)。同时需要满足推迟后任意一种数据在任意时刻都可以被下载,你可以认为给出的初始维护时间满足这一性质。
    保证有解。若有多种方案,选择任意一个方案满足这个非空子集的元素数量最少。

题目分析

很呵呵的一道题。
开始的时候想的是2-sat,但是似乎不能最小化答案。
又因为题目有这个坑爹的限制:你可以认为给出的初始维护时间满足这一性质。说实话我读了3遍题都没有看出来这是哪句话说的。

这样我们可以重新建图:
若$(u_{c_{i,1}}+1)\bmod k=u_{c_{i,2}}$,连一条边$c_{i,1}\rightarrow c_{i,2}$。
若$(u_{c_{i,2}}+1)\bmod k=u_{c_{i,1}}$,连一条边$c_{i,1}\rightarrow c_{i,2}$。
边$x\rightarrow y$表示的意义是$x$一结束维护,$y$立刻开始维护。
在这个图中若选择一个点推迟维护,其能够到达的所有点都需要推迟维护。
这样我们对原图进行强连通分量缩点,即可得到一个DAG。
显然,在这个DAG中选择出度为$0$的连通分量是最优的,故在出度为$0$的强连通分量中选择一个最小的即可。
由于题目的坑爹限制,正确性是有保证的。

代码

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
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=200005;
int n,m,k,a[maxn],OutDegree[maxn],Size[maxn],Ans,Min=INT_MAX,step=0,top=0,SCC=0,Dfn[maxn],Lowlink[maxn],Stack[maxn],Belong[maxn];
bool Instack[maxn];
vector<int> edges[maxn],ans;
void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int Next:edges[Now]) {
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
int y;
SCC++;
do {
y=Stack[top--];
Instack[y]=0;
Belong[y]=SCC;
Size[SCC]++;
} while(y!=Now);
}
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
if((a[x]+1)%k==a[y])edges[x].push_back(y);
if(a[x]==(a[y]+1)%k)edges[y].push_back(x);
}
for(int i=1; i<=(n<<1); i++)if(!Dfn[i])Tarjan(i);
for(int Now=1; Now<=n; Now++)
for(int Next:edges[Now])
if(Belong[Now]!=Belong[Next])OutDegree[Belong[Now]]++;
for(int i=1; i<=n; i++)if(!OutDegree[Belong[i]]&&Size[Belong[i]]<Min) {Min=Size[Belong[i]];Ans=Belong[i];}
for(int i=1; i<=n; i++)if(Belong[i]==Ans)ans.push_back(i);
printf("%d\n",ans.size());
for(auto x:ans)printf("%d ",x);
return 0;
}

Bonus!

BONUS (medium): 若原来不满足坑爹的限制,但不要求最小化答案,你能解决吗?

当然,这就是刚刚说的2-sat的方法。
关于2-sat怎么选择非空子集?因为保证有解,因此可以随便选一个点,让其选择不推迟,检查是否有合法方案。
若有合法方案,直接输出,否则让其选择推迟,再寻找合法方案。

BONUS ((NP?)-hard): 若原来不满足坑爹的限制,要求最小化答案,你能解决吗?

好像确实是NP问题。

Problem F. Curfew

题目大意

    学校有个$n$个寝室排列成一条直线,每个寝室住有$b$个学生,查寝前学生在任意寝室玩,若第$i$个寝室有$a_i$个学生,满足$\sum_{i=1}^na_i=nb$。
    现在有$2$个宿管老师来查寝,在检查寝室$i$的时候,若$a_i\neq b$,宿管老师就会记录一个寝室违规,但不会驱逐学生,若$a_i=b$时,老师也不会点名而认为该寝室没有违规。检查完毕后,宿管老师会关灯锁门。另外,学生可以藏在床底下,你可以认为床底下可以藏任意多个学生,而不会被宿管老师发现。
    第一个宿管老师从$1$寝室检查到$\frac {n+1}2$寝室,第二个则从$n$寝室检查到$\frac {n+1}2+1$。
    查寝的流程是这样的:

  • 当宣布查寝时,第$i$个寝室有$a_i$个学生。
  • 学生可以跑到另外一个寝室,但是不能移动超过$d$个寝室。然后学生可以藏在床底下。
  • 宿管老师进入$1$寝室和$n$寝室,清点人数然后关灯锁门(之后没人能够进入或出去)。
  • 在$2\sim n-1$号寝室的学生可以跑到另一个寝室,但是不能移动超过$d$个寝室,也不能进入一个锁着的寝室。然后学生可以藏在床底下。
  • 宿管老师进入$2$寝室和$n-1$寝室,清点人数然后关灯锁门(之后没人能够进入或出去)。
  • 按照以上流程重复进行。

    若第一个宿管老师发现有$x_1$个寝室违规,第二个宿管老师发现有$x_2$个寝室违规时,他们会将$\max(x_1,x_2)$报给校长。故你需要找到一种最优的方案,使得$\max(x_1,x_2)$最小。

题目分析

题面超长。
我们先考虑只有一个宿管老师,他从$1$寝室检查到$n$寝室。
有一种贪心的方案:

  • 从左往右考虑每一个房间。
  • 若这个房间有太多学生,将多余的学生移动到后一个房间。
  • 若这个房间的学生不够,但从右边的房间可以移动学生到当前房间($\sum_{j=i}^{\min(n,i+i\times d)}a_j\ge b$),那就这么做。
  • 若这个房间不可能凑够人数,将所有人移动到后一个房间。
  • 如果这是最后一个房间,所有多余的学生藏在床底。

正确性是显然的,可以在$O(n)$的时间内完成。
可以发现一个性质,学生的移动路径一定不会相交。也就是说,若$i$寝室的学生移动到$a$寝室,$j$寝室的学生移动到$b$寝室,若$i\le j$,则$a\le b$,因为若不满足,可以交换两个学生。

现在重新考虑两个宿管老师的情况。
因为满足学生的移动路径一定不会相交,因此一定存在一个边界$x(0\le x\le nb)$,其中$x$个学生去前$\frac {n+1}2$个寝室,其余的去后$\frac n2$个寝室,同时也存在一个边界位置$pos(1\le pos\le n)$,其中$1\sim pos$的学生去前$\frac {n+1}2$个寝室,$pos\sim n$的学生去后$\frac n2$个寝室。
若$m$是边界,令$f(m)$是第一个宿管老师的记录值,$g(m)$是第二个宿管老师的记录值。
当$m$确定时,可以将原问题分割称两个子问题,分别使用只有一个宿管老师时的方法计算,即可求出$f(m)$与$g(m)$。
不难发现,当$f(m)$减少时,$g(m)$增加,而我们要找到$ans(m)=\max(f(m),g(m))$的最小值,令$z(m)=g(m)-f(m)$,$z(m)$不严格单增。
要寻找$z(m)$最接近$0$的位置,可以使用二分,时间复杂度$O(n\log nb)$。

代码

因为有更优的方法(见Bonus 1),故没写。

Bonus!

Bonus (medium): 在$O(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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
LL n;
int d,b,a[100005];
int main() {
n=Get_Int();
d=Get_Int();
b=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
LL sum=0;
int cnt=0,mid=(n+1)>>1;
for(int i=1,j=1; i<=mid; i++) {
for(; j<=min(n,i+1ll*i*d); j++)sum+=a[j];
if(sum>=b)sum-=b;
else cnt++;
}
int ans=cnt;
cnt=sum=0;
for(int i=n,j=n; i>mid; i--) {
for(; j>=max(0ll,i-1ll*(n-i+1)*d); j--)sum+=a[j];
if(sum>=b)sum-=b;
else cnt++;
}
printf("%d\n",max(ans,cnt));
return 0;
}

Bonus (medium): 若学生们都是Achen(很胖)而不能藏在床下,你能解决吗?

这就意味着贪心时不能将所有学生都怼到最后一个房间了。
修改贪心方案:

  • 从左往右考虑每一个房间。
  • 若这个房间有太多学生,将多余的学生移动到后一个房间。
  • 若这个房间的学生不够,但从右边的房间可以移动学生到当前房间($\sum_{j=i}^{\min(n,i+i\times d)}a_j\ge b$),那就这么做。
  • 若这个房间不可能凑够人数,将一定的学生$x=\max(0,(n-i)b-\sum_{j=i+1}^na_j)$移动到后一个房间,其余的藏在床底。
  • 如果这是最后一个房间,所有多余的学生藏在床底。
0%