Codeforces Round #712 (Div. 2)
2024-09-08 09:23:39
A. Déjà Vu
题意：就是问能否加上字母a，使得字符串不中心对称
思路：只有一种情况不能加入，就是全部是a，剩下的都可以满足，找a的位置就找哪个字母不是a，然后让它的对称位置是新加的这个a
代码：
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 using namespace std;
7 const int maxx=3e5+10;
8 int main(){
9 int t;
10 scanf("%d",&t);
11 while(t--){
12 char s[maxx];
13 scanf("%s",&s);
14 int n=strlen(s);
15 int a=0;
16 int flag=-1;
17 for(int i=0;i<n;i++){
18 if(s[i]!='a'){
19 flag=n-1-i;
20 }
21 }
22 if(flag==-1){
23 printf("NO\n");
24 }else{
25 printf("YES\n");
26 for(int i=0;i<n;i++){
27 if(i==flag){
28 printf("a");
29 }
30 printf("%c",s[i]);
31 }
32 printf("\n");
33 }
34 }
35 }
B. Flip the Bits
题意：通过前缀翻转，问a能不能变换为b字符串，并且保证前缀反转的字符串0和1的数量相等
思路：就是从后往前看，先用前缀和标记下来，可以反转的位置，然后从后往前看，能够反转的位置是相同还是相反，记录下来，因为再往左的下一次翻转中间的这些需要和开头的性质一样，然后一定注意是这次之前翻转了多少次，不算这次，也就是说这个值和看后面已经经历了多少个0不一样，会差1
代码:
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 using namespace std;
7 const int maxx=3e5+10;
8 int a[maxx]={0},b[maxx]={0},c[maxx]={0},ps[maxx]={0};
9 int main(){
10 int t;
11 scanf("%d",&t);
12 while(t--){
13 int n;
14 scanf("%d",&n);
15 int bb=0;
16 for(int i=0;i<n;i++){
17 scanf("%1d",&a[i]);
18 if(a[i]==0){
19 ps[i]=-1;
20 }else{
21 ps[i]=1;
22 }
23 }
24 for(int i=0;i<n;i++){
25 scanf("%1d",&b[i]);
26 }
27 int flag=0;
28 for(int i=0;i<n;i++){
29 if(i==0){
30 c[i]=ps[0];
31 }else{
32 c[i]=c[i-1]+ps[i];
33 }
34 //printf("i:%d ps:%d c:%d\n",i,ps[i],c[i]);
35 // printf("i:%d c:%d\n",i,c[i]);
36 }
37 int x=0,y=0;
38 /* for(int i=0;i<n;i++){
39 if(a[i]==0){
40 x++;
41 }else{
42 y++;
43 }
44 if(x==y){
45 c[i]=1;
46 }
47 }*/
48 /* for(int i=0;i<n;i++){
49 printf("%d",c[i]);
50 }
51 printf("\n");*/
52 int p=0;
53 flag=0;//1.��� 2.��ת
54 for(int i=n-1;i>=0;i--){//�ؼ��Ǵ���ǰ�ڴ�֮ǰ���й����ٴη�ת�������ǵ������֮ǰ���е���
55 //c�������0
56 if(c[i]==0){
57 bb++;
58 }
59 if(bb==0){
60 if(a[i]!=b[i]){
61 p=-1;
62 break;
63 }else{
64 continue;
65 }
66 }
67
68 if((bb-1)%2==0){
69 if(c[i]==0&&a[i]==b[i]){
70 flag=1;
71
72 }else if(c[i]==0&&a[i]!=b[i]){
73 flag=2;
74
75 }
76 if(c[i]!=0){
77 if(flag==0&&a[i]!=b[i]){
78 //printf("1: i:%d flag:%d bb:%d\n",i,flag,bb);
79 p=-1;
80 break;
81 }else if(flag==1&&a[i]!=b[i]){
82 // printf("2: i:%d flag:%d bb:%d\n",i,flag,bb);
83 p=-1;
84 break;
85 }else if(flag==2&&a[i]==b[i]){
86 // printf("3: i:%d flag:%d bb:%d\n",i,flag,bb);
87 p=-1;
88 break;
89 }
90 }
91 }else{
92 if(c[i]==0&&a[i]!=b[i]){
93 flag=1;
94
95 }else if(c[i]==0&&a[i]==b[i]){
96 flag=2;
97
98 }
99 if(c[i]!=0){
100 if(flag==0&&a[i]==b[i]){
101 //printf("4: i:%d flag:%d bb:%d\n",i,flag,bb);
102 p=-1;
103 break;
104 }else if(flag==1&&a[i]==b[i]){
105 //printf("5: i:%d flag:%d bb:%d\n",i,flag,bb);
106 p=-1;
107 break;
108 }else if(flag==2&&a[i]!=b[i]){
109 // printf("6: i:%d flag:%d bb:%d\n",i,flag,bb);
110 p=-1;
111 break;
112 }
113 }
114 }
115 // printf("i:%d b:%d\n",i,bb);
116 }
117 if(p==-1){
118 printf("NO\n");
119 }else{
120 printf("YES\n");
121 }
122 }
123 }
C. Balance the Bits
见https://www.bilibili.com/read/cv10616355
思考：1）就是大体就是1和0分开考虑，然后集合起来再思考总体需要满足的条件；2）1是相对于1的个数来说的，而0是相对于0的相对位置来说的；3）一定注意return0的位置
代码：
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<cmath>
6 using namespace std;
7 const int maxx=2e5+10;//一个是直接return 0了，一个就是全部是1的也是可以的
8 int main(){
9 int t;
10 scanf("%d",&t);
11 while(t--){
12 int n;
13 int a[maxx]={0};
14 scanf("%d",&n);
15 int sumx=0,sumy=0;
16 for(int i=0;i<n;i++){
17 scanf("%1d",&a[i]);
18 if(a[i]==0){
19 sumx++;
20 }else{
21 sumy++;
22 }
23 }
24 if(sumx%2==1){
25 printf("NO\n");
26 continue;
27 }
28 int x=1,y=0;//x.0的个数 y.1的个数
29 int b[maxx]={0};//0.you 1.z
30 for(int i=0;i<n;i++){
31 // printf("a[%d]:%d x:%d\n",i,a[i],x);
32 if(a[i]==1&&y<sumy/2){
33 b[i]=0;
34 y++;
35 }else if(a[i]==1&&y>=sumy/2){
36 b[i]=1;
37 // y++;
38 }
39 if(a[i]==0&&x%2==1){
40 b[i]=0;
41 x=0;
42 }else if(a[i]==0&&x%2==0){
43 b[i]=1;
44 x=1;
45 }
46 }
47 /* for(int i=0;i<n;i++){
48 printf("%d",b[i]);
49 }
50 printf("\n");*/
51
52 x=0;
53 y=0;
54 int f=0;
55 for(int i=0;i<n;i++){
56 if(b[i]==0){
57 x++;
58 }else{
59 y++;
60 }
61 if(x<y){
62 f=1;
63 }
64 }
65 if(x!=y||f==1){
66 printf("NO\n");
67 continue;
68 }
69 x=0;
70 y=0;
71 f=0;
72 for(int i=0;i<n;i++){
73 if(a[i]==0){
74 if(b[i]==0){
75 y++;
76 }else{
77 x++;
78 }
79 }else{
80 if(b[i]==0){
81 x++;
82 }else{
83 y++;
84 }
85 }
86 if(x<y){
87 f=1;
88 }
89 }
90 if(x!=y||f==1){
91 printf("NO\n");
92 continue;
93 }
94 printf("YES\n");
95 for(int i=0;i<n;i++){
96 if(b[i]==0){
97 printf("(");
98 }else{
99 printf(")");
100 }
101 }
102 printf("\n");
103 for(int i=0;i<n;i++){
104 if(a[i]==0){
105 if(b[i]==0){
106 printf(")");
107 }else{
108 printf("(");
109 }
110 }else{
111 if(b[i]==0){
112 printf("(");
113 }else{
114 printf(")");
115 }
116 }
117 }
118 printf("\n");
119 }
120 }
最新文章
- 《UML大战需求分析》阅读随笔（五）
- Pause/Resume Instance 操作详解 - 每天5分钟玩转 OpenStack（34）
- div水平居中和垂直居中
- TI CC2541增加一个可读写, 又可以Notify的特征字
- 十天学会单片机Day5 IIC总线AT2402芯片(EEPROM)应用
- 如何获得iphone设备的剩余空间
- lua 学习笔记（一）
- jq 图片上传
- [Angular 2] The form export from NgFormControl
- 【iOS】网页中调用JS与JS注入
- Python -- lambda, map, filter
- mysql 命令备份
- docker registry私有仓库部署
- JSP动态产生的代码，点击显示确认操作，根据操作跳转并传值。
- [数据预处理]-中心化 缩放 KNN（一）
- AtCoder SoundHound Inc. Programming Contest 2018 E + Graph (soundhound2018_summer_qual_e)
- boost 正则表达式 regex
- git迁移
- python历史与基本类型
- Node 连接池pool