[Codeforces Round #310 (Div. 2)] #ABC题解

没想到时隔两天竟然又打了cf,做了3题就弃疗了。

题目链接:Codeforces Round #310 (Div. 2)
A. Case of Zeros and Ones
[Description]
给定一个01串,相邻的0和1可以消掉,问最终这个串最短可以消到多长。
[Solution]
可以证明,当这个序列0和1都还存在,是可以继续进行消除的,直到某个数字没有。
[Ans] n-2*(min(num0.num1))
[Code]
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

int num[2];

int main(){
    int n; scanf("%d",&n);
    char c=getchar(); while(!isdigit(c)) c=getchar(); num[c-'0']++;
    for(int i=1;i<n;i++)
c=getchar(),num[c-'0']++;
    printf("%d",n-2*min(num[0],num[1]));
    return 0;

}


B. Case of Fake Numbers

[Description]
给定n个有n个(编号1~n)锯齿的齿轮,给出一个初始的序列,代表他们相嵌的锯齿号(0~n-1),现在可以同时旋转他们,使得奇数编号齿轮和偶数编号齿轮相反旋转,即奇数编号齿轮的锯齿号+1,偶数-1,超过n-1则变为0,小于0则变为n-1,要求判断经过若干次操作后能否达到0~n-1的排列。
[Solution]
因为经过n次操作必然又会回到原来的状态,所以只要枚举n次并判断中间是否出现过符合要求的状态就可以了。
[Code]
#include<cstdio>
#include<cstring>

const int maxn=2000;
int n,a[maxn];

bool check(){
for(int i=1;i<=n;i++) if(a[i]!=i-1) return false;
return true;
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j%2){
a[j]++;
if(a[j]>=n)
a[j]=0;
}
else{
a[j]--;
if(a[j]<0)
a[j]=n-1;
}
}
if(check()){ printf("Yes"); return 0; }
}
printf("No");
return 0;

}


C. Case of Matryoshkas

[Description]
有n个俄罗斯套娃(编号1~n,代表它们的大小),初始被套成q个(每个含多个套娃),每秒可以进行一次操作,把一个套娃放进另一个空的套娃,或者把一个套娃从外层且没被套住的套娃里拿出来,问最少几秒可以把套娃重新组装好。
[Solution]
把最小合法的套娃(即不要拆开的最小的几个)看作一个套娃,其余的全部要一个一个拆,一个一个拼。
[Code]
#include<cstdio>

const int maxn=100000+10;
int order[maxn];

int main(){
int ans=0,t=0;
int n,m; scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int k; scanf("%d",&k); ans+=k-1;
for(int j=0;j<k;j++) scanf("%d",&order[j]);
if(order[0]==1){
int o=0;
while(order[o]==order[o+1]-1) o++,t++;
}
}
printf("%d",n-1+ans-2*t);
return 0;

}

此博客中的热门博文

图论专题总结