Codeforces Round #712 (Div. 2)
阅读原文时间:2023年07月09日阅读:1

A. Déjà Vu

题意:就是问能否加上字母a,使得字符串不中心对称

思路:只有一种情况不能加入,就是全部是a,剩下的都可以满足,找a的位置就找哪个字母不是a,然后让它的对称位置是新加的这个a

代码:

1 #include
2 #include
3 #include
4 #include
5 #include
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
2 #include
3 #include
4 #include
5 #include
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=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
2 #include
3 #include
4 #include
5 #include
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=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 }