CF1025C Plasticine zebra【环状字符串/思维】

给你一个长度为 \(\left|s\right|\) 的01串 \(s\) ，每次操作你可以任选一个 \(k\) ，使01串的 \([1,k]\) 和 \((k,\left|s\right|]\) 分别翻转（其中一个区间可以为空），求经过任意次操作后能得到的最长的01交替出现的子串的长度。（实际题目中01用w和b代替）

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define mod 10003

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int INF = 1<<30;

const int maxn = 1000003;

const double eps = 1e-8;

int t,n,m,q;

int sum[maxn];

int p[maxn],l,r,x,y;

char s[maxn];

LL min(LL x,LL y){return x>y?y:x;}

LL max(LL x,LL y){return x>y?x:y;}

int main()

{

    while(~scanf("%s",s+1))

    {

        LL ans=0,cnt=0;

        int n=strlen(s+1);

        for(int i=1;i<=n;i++)

        {

            s[i+n]=s[i];

        }

        for(int i=1;i<=2*n;i++)

        {

            if(s[i]!=s[i-1])

                ans=max(ans,++cnt);

            else cnt=1;

        }

        cout<<min(ans,n)<<endl;

    }

    return 0;

}

/*

设原串为s1,s2,...sn，我们将原串拉长一倍得到：S=s1,..sn...s2n

很显然的一个事实：无论将原串如何合法处理，得到的新串始终是S的一个子串。

所以我们此时只需要从头到尾去扫一遍统计前后相等与不相等的最长长度即可。

*/

巴特西

CF1025C Plasticine zebra【环状字符串/思维】

最新文章

热门文章