BZOJ 4236 JOIJOI

题目大意

给你一个'J','O','I'组成的字符串，请输出最长连续子串满足'J''O''I'出现的次数相同。

在几个月前的一次比赛里面出现了这道题，然后我A了?今天同学拿来问我，我竟然忘了= =所以说还是要把它写出来嘛QwQ

这是一道奥妙重重的题= =

我们首先发现，这道题是个序列，当然不可能暴力统计出现次数，于是考虑使用前缀和。

将样例画在草纸上，我发现一个性质：如果出现次数一样的话，那么一定有a[i]+x=a[j],b[i]+x=b[j],c[i]+x=c[j] (a,b,c为'J','O','I'出现次数前缀和)

我们将x都减去（也就是说减去a[i],b[i],c[i]中最小的）此时我们就得到了一个类似于特征序列的东西。此时我们仅需要求出特征序列相同的元素间隔最长的就是我们所求的了。

时间复杂度：排序时间复杂度O(nlogn)

#include <cstdio>
#include <algorithm>
using namespace std;
int n,ans,tmp;
char s[200010];
struct counter
{
	int j,o,i,id;
}a[200010];
bool cmp(counter tx,counter ty)
{
	if(tx.j==ty.j&&tx.o==ty.o&&tx.i==ty.i) return tx.id<ty.id;
	if(tx.j==ty.j&&tx.o==ty.o) return tx.i<ty.i;
	if(tx.j==ty.j) return tx.o<ty.o;
	return tx.j<ty.j;
}
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;++i)
	{
		a[i].j=a[i-1].j;
		a[i].o=a[i-1].o;
		a[i].i=a[i-1].i;
		a[i].id=i;
		switch(s[i])
		{
			case 'J':a[i].j++;break;
			case 'O':a[i].o++;break;
			case 'I':a[i].i++;break;
		}
		int minn=min(min(a[i].j,a[i].o),a[i].i);
		a[i].j-=minn;
		a[i].o-=minn;
		a[i].i-=minn;
	}
	sort(a+1,a+n+2,cmp);
	for(int i=1;i<=n+1;++i)
		if(a[i].j!=a[i-1].j||a[i].o!=a[i-1].o||a[i].i!=a[i-1].i) ans=max(ans,a[i-1].id-tmp),tmp=a[i].id;
	printf("%d\n",ans);
	return 0;
}