P1203 [USACO1.1] 坏掉的项链 Broken Necklace
想了好一会 想到了循环队列啥的 感觉不怎么合适 在题解区看到的一个方法豁然醒悟233~~~
借鉴一下某大佬的思路方法
#include<bits/stdc++.h>
using namespace std;
string s;
int compare(int x){int num=0;char ch1=s[x];//确定断裂处的第一个珠子（头）char ch2=s[x+1];//断裂处的第一个珠子（尾）for(int i=x;;i--){//尾 往前扫 小于了n前面还有串的（3个串相加的作用）if(s[i]=='w')num++;else if(ch1==s[i])num++;else break;}for(int i=x+1;;i++){//头 往后加 越过了n后面还有串if(s[i]=='w')num++;else if(ch2==s[i])num++;else break;}return num;
}
int main() {int n,cnt=-1;cin>>n;cin>>s;s=s+s+s;//三个s串相加用来充当一个大的循环项链 相当于圈for(int i=n;i<2*n;i++){if(s[i]=='w'){s[i]='b';cnt=max(cnt,compare(i));//w换成b带入计连续算数量s[i]='r';cnt=max(cnt,compare(i));//w换成rs[i]='w';//换回来}elsecnt=max(cnt,compare(i));}cnt=min(cnt,n);//防止cnt大于题目项链长度 因为在上面函数里面由于for循环没有限制 会出现比较相同字符的数量超出了题目给的项链长度 这是它的最大长度必定是项链长度 例如这一组数据
//输入：8 rrwwwwbb 输出：8if(cnt==-1)cnt=n;cout<<cnt;
}记录一下 日后回看