【链接】

【题意】

给你一个字符串s.
让你在其中的某一些位置进行操作。。
把[1..i]和[i+1..n]翻转。
使得里面01交替出现的那种子串的长度最长。

【题解】

可以用a,b,c,d,e,f,g依次连在一起。然后a和g再连在一起。形成一个环。。
然后你在这个环上模拟这个操作的过程。
就会发现。不管怎么样。
形成的序列都是下列字符串的一个子串(当然有的时候是反过来的。但会发现正反的话,不影响01串的长度。
abcdefgabcdefg
(你会发现在这个环上从a以一定的方向走,总能找到一个按顺序的a,b,c,d,e,f,g.他们的相对位置没有变。
所以在这个扩大了一倍的字符串上做一次01串的查找就好啦

abcdefgabcdefg

【代码】

#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define rson mid+1,r,rt<<1|1
using namespace std; const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0}; const int N =1e5;
bool cmp(int a,int b)
{
return a>b;
} int m,n;
char s[N+10]; int a[N];
int main()
{
int t,f=0;
scanf("%s",s);
int l=strlen(s);
if(l==1){
cout << 1 << endl;
return 0;
}
int ans=1,z=1;
for(int i=1; i<2*l; i++)
{
if(s[i%l]!=s[(i-1)%l]) z++;
else
{
ans=max(z,ans);
z=1;
}
ans=max(z,ans);
} ans=min(ans,l); printf("%d\n",ans);
return 0;
}
05-11 17:02
查看更多