3194. 字符串消除

科技前沿 • 2025-04-09 07:25 • 阅读 41

大家好，我是讯享网，很高兴认识大家。

单点时限: 2.0 sec

内存限制: 256 MB

给定一个由大写字母A、B、C构成的字符串s，按如下进行消除过程：

1、字符串s中连续相同字母组成的子串，如果子串的长度大于1，那么这些子串会被同时消除，余下的字符拼成新的字符串。

例如：ABCCBCCCAA中CC,CCC和AA会被同时消除，余下AB和B拼成新的字符串ABB。

2、反复进行上述消除，直到新的字符串中相邻字符都不相同为止。

例如：ABCCBCCCAA经过一轮消除得到ABB，再经过一轮消除得到A。

假设在对字符串s消除开始前，允许在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符(A,B或者C)，得到字符串t，然后对字符串t经过一系列消除。

讯享网

请问该如何插入字符，使得字符串t中被消除掉的字符总数（包括插入的字符）最多？

第 ~ 行：每个问题占一行，每行输入一个由A、B、C组成的字符串s，长度不超过100。

样例
input
3
ABCBCCCAA
AAA
ABC
output
case #0:
9
case #1:
4
case #2:
2
提示
第一组数据：在ABCBCCCAA的第2个字符后插入C得到ABCCBCCCAA，消除后得到A，总共消除9个字符(包括插入的’C’)。

第二组数据：AAA插入A得到AAAA，消除后得到”“，总共消除4个字符。

第三组数据：无论是插入字符后得到AABC,ABBC还是ABCC都最多消除2个字符。

/* 思路：暴力试探，一位一位插ABC，最终得到消掉的最大数 */ #include<iostream> #include<algorithm> using namespace std; bool text(string s) { 
    int i=0; while(i<s.size()-1) { 
    if(s[i]==s[i+1]) return true; i++; } return false; } string f(string s) { 
    int i=0; string x; while(i<s.size()) { 
    //ABCCBCCAA if(s[i]==s[i+1]&&i+1<s.size()) { 
    int j = i; while(s[j]==s[j+1]&&j<s.size()-1)j++; i=j+1; } else { 
    x+=s[i]; i++; } } if(text(x)&&x!="") return f(x); else return x; } int main() { 
    int t; cin>>t; for(int k=0; k < t; k++) { 
    string s; cin>>s; int sum=0; for(int i = 0; i < s.size(); i++) { 
    string x,y,z; x=y=z=s; x.insert(i,"A"); y.insert(i,"B"); z.insert(i,"C"); int a=f(x).size(); int b=f(y).size(); int c=f(z).size(); int Min=min(min(a,b),c); Min=s.size()+1-Min; sum=max(sum,Min); } printf("case #%d:\n%d\n",k,sum); } return 0; }

讯享网

3194. 字符串消除

相关推荐