标签：智商题
题目
Description
给定一个长度为n的仅包含’B’、’C’、’S’三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。
Input
第一行包含一个正整数\(n(1<=n<=1000000)\)，表示字符串的长度。 第二行一个长度为n的字符串。
Output
包含一行一个正整数，即最长的满足条件的子串的长度。
Sample Input
9
CBBSSBCSC
Sample Output
6
HINT
选择BSSBCS这个子串。
分析
结论题：
- 所求答案的最长子串\([l,r]\)，3种字母个数最多相差1
- 对于子段\([l,r]\)，当\(l\in [1,3]\ ,r\in [n-2,n]\)时，一定能找到最优解
之后就是暴力乱搞了
目前本题终于卡到了bzoj rank1
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6;
int a[maxn],b[maxn],c[maxn],n,ans=0;
char st[maxn<<1];
int main()
{
n=read();scanf("%s",st+1);
rep(i,1,n)a[i]=a[i-1]+(st[i]=='B'),b[i]=b[i-1]+(st[i]=='C'),c[i]=c[i-1]+(st[i]=='S');
rep(i,1,3)
for(int j=n;j-i+1>ans;j--){
int ta=a[j]-a[i-1],tb=b[j]-b[i-1],tc=c[j]-c[i-1];
if((ta!=tb&&ta!=tc&&tc!=tb)||(!ta)+(!tb)+(!tc)==2){ans=j-i+1;break;}
}
rep(j,n-2,n)
for(int i=1;j-i+1>ans;i++){
int ta=a[j]-a[i-1],tb=b[j]-b[i-1],tc=c[j]-c[i-1];
if((ta!=tb&&ta!=tc&&tc!=tb)||(!ta)+(!tb)+(!tc)==2){ans=j-i+1;break;}
}
cout<<ans<<endl;
return 0;
}
