没想到时隔两天竟然又打了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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #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
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<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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #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;
}
|
