BZOJ4384 [POI2015]Trzy wie?e

标签：智商题

题目

题目传送门

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;
}