[bzoj4893]项链分赃

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

有一串长度为n(n<=10^5)的项链，上面有红绿蓝三种颜色的珠子，每种颜色的珠子数目都是偶数，现在要你把它切几刀分成若干段，把其中一些段分给海盗1，剩余的段分给海盗2，要求两个海盗分得的每种颜色的珠子数量都相同，请输出最少需要切多少刀。

感觉是到智商题 想了很久不懂怎么做开始猜结论  

感觉答案不会超过3  就判掉了答案是1和2的情况，然后就过了233 

然后又想了很久 根本不会证明qaq

去出题人博客上看了看证明 真的神 我是服了..  给个链接吧。

#include<cstdio>
#define getchar() (*S++)
#define MN 100000
char B[<<],*S=B;
using namespace std;
inline int read()
{
    int x = ; char ch = getchar();
    while(ch < '' || ch > '') ch = getchar();
    while(ch >= '' && ch <= '')x = x *  + ch - '',ch = getchar();
    return x;
}

int n,N,a[MN+],tot[];

int main()
{
    fread(B,,<<,stdin);
    n=read();N=n>>;
    for(register int i=;i<=n;++i) ++tot[a[i]=read()];
    tot[]>>=;tot[]>>=;tot[]>>=;
    for(register int i=;i<=N;++i) --tot[a[i]];
    if(!tot[]&&!tot[]&&!tot[]) return *puts("");
    for(register int i=,j=N;j<n;++tot[a[i++]],--tot[a[++j]])
        if(!tot[]&&!tot[]&&!tot[]) return *puts("");
    puts("");
    return ;
}