A. Love "A"
题意:
如果长度为 len 的串 s 中, 'a' 的个数严格大于 2/len,那么,就成此串为 "good string";
给出你一个串 s,你可以删去任意字符(当然也可以不删)使得 s 变为 "good string",求 "good string" 的最大长度;
思路:
假设 s 中有 sum 个'a',那么,答案就是 min{ sum*2-1,len };
AC代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100; 4 5 char s[maxn]; 6 7 int main() 8 { 9 while(~scanf("%s",s)) 10 { 11 int sum=0; 12 int len=strlen(s); 13 for(int i=0;i < len;++i) 14 if(s[i] == 'a') 15 sum++; 16 printf("%d\n",min(len,sum*2-1)); 17 } 18 }
B. Hate "A"
题意:
新定义:将串 s 中的所有字符 'a' 去掉构成串 s',s+s' = t;
给出你串 t,判断是否有相应的串 s,使得 s+s' = t,如果有,输出串 s,反之,输出":(";
思路:
将给出的串 t 中的所有 'a' 去掉,形成新的串 ans;
1.如果串 ans 的长度为0,输出串 t;
2.如果串 ans 的长度为奇数,输出 ":(";
3.如果串 ans 的长度为偶数,那么便可将串 ans 分成左右两部分 串ansL,串ansR,比对 ansL 是否等于 ansR;
3.1 'a'最后出现的位置在ansR中,输出 ":(";
3.2 如果相等,并且'a'最后出现的位置不在ansR中,输出 t 串中包含 ansL 的部分;
3.3如果不相等,输出":(";
例如:
1. t="aaaa",输出 "aaaa";
2. t="ab",输出 ":(";
3.1 t="ababa",输出 ":(";
3.2 t="abab",输出 "aba";
3.3 t="abac",输出 ":(";
AC代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+50; 4 5 char t[maxn]; 6 char s[maxn]; 7 8 char *Solve() 9 { 10 int sum=0; 11 int sumA=0; 12 int len=strlen(t); 13 for(int i=0;i < len;++i) 14 if(t[i] == 'a') 15 sumA++; 16 else 17 sum++; 18 if(sum == 0)//情况1 19 return t; 20 21 int sumR=0; 22 for(int i=len-1;i >= 0 && t[i] != 'a';i--,sumR++); 23 if(sum%2 != 0 || sumR < sum/2)//情况2,3.1 24 return ":("; 25 26 int sumL=0; 27 int index=0; 28 for(int i=0;sumL < sum/2;++i) 29 { 30 s[index++]=t[i]; 31 if(t[i] == 'a') 32 continue; 33 34 if(t[i] != t[sumA+sumL+sum/2])//情况3.3 35 return ":("; 36 sumL++; 37 38 if(sumL == sum/2)//情况3.2 39 { 40 while(t[i+1] == 'a') 41 s[index++]=t[++i]; 42 } 43 } 44 s[index]='\0'; 45 return s; 46 } 47 int main() 48 { 49 scanf("%s",t); 50 printf("%s\n",Solve()); 51 52 return 0; 53 }
简洁版代码(参考自大神代码,Orz)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 string s; 5 string t; 6 7 string Solve() 8 { 9 for(int i=0;i < s.size();++i) 10 if(s[i] != 'a') 11 t += s[i]; 12 if(t.size()%2 != 0) 13 return ":("; 14 15 int half=t.size()/2; 16 17 string t1=t.substr(0,half);//前半段 18 string t2=t.substr(half,half);//后半段 19 if(t1 == t2 && t1 == s.substr(s.size()-half,half)) 20 return s.substr(0,s.size()-half); 21 return ":("; 22 } 23 int main() 24 { 25 ios::sync_with_stdio(false); 26 cin.tie(false); 27 cout.tie(false); 28 29 cin>>s; 30 cout<<Solve()<<endl; 31 32 return 0; 33 }
用到了string中的一些函数,这些函数我没怎么接触过,之前一直不怎么用string,总感觉char[]比string块,QWQ;