[POI2015]Trzy wieże

题目大意：

给定一个长度为\(n(n\le10^6)\)的仅包含'B'、'C'、'S'三种字符的字符串，请找到最长的一段连续子串，使得在这一段内出现过的所有字符中，字符的出现次数互不相同。

思路：

一个结论是对于子段\([l,r]\)，当\(l\in[1,3]\)或\(r\in[n-2,n]\)时一定有解，而且一定能找到最优解。

证明略。

预处理\(1\sim n\)各数字出现次数前缀和，枚举\(l,r\)即可。

时间复杂度\(\mathcal O(n)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

inline int getval() {

	register char ch;

	while(!isalpha(ch=getchar()));

	if(ch=='B') return 0;

	if(ch=='C') return 1;

	return 2;

}

const int N=1e6+1;

int cnt[N][3];

inline bool check(const int &l,const int &r) {

	int tmp[3];

	for(register int i=0;i<3;i++) {

		tmp[i]=cnt[r][i]-cnt[l-1][i];

	}

	for(register int i=0;i<3;i++) {

		if(tmp[i]==0) continue;

		for(register int j=i+1;j<3;j++) {

			if(tmp[j]==0) continue;

			if(tmp[i]==tmp[j]) return false;

		}

	}

	return true;

}

int main() {

	const int n=getint();

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

		for(register int j=0;j<3;j++) {

			cnt[i][j]+=cnt[i-1][j];

		}

		cnt[i][getval()]++;

	}

	int ans=0;

	for(register int i=1;i<=3;i++) {

		for(register int j=i;j<=n;j++) {

			if(check(i,j)) ans=std::max(ans,j-i+1);

		}

	}

	for(register int j=n-2;j<=n;j++) {

		for(register int i=1;i<=j;i++) {

			if(check(i,j)) ans=std::max(ans,j-i+1);

		}

	}

	printf("%d\n",ans);

	return 0;

}