排排站

【题目描述】

N头奶牛有一些共同之处(1 <= N <= 100000)。我们可以将这N头奶牛通过K种特征来归类(1 <= K <= 30)。

我们有一种简明的描述特征的方法——“特征码”，用一个长度为k的二进制串来表示这头牛的特征表现。例如，一头牛的“特征码”为13，转换为二进制就是1101，代表这头牛具有特征1、3、4（从右读到左），但是不表现特征2。总之，如果这头奶牛表现特征i，那么我们在他的“特征码”的二进制的第i位就为1。

现将奶牛排成了一个1~N的队列，他注意到一种确定的排列方法可以使奶牛们的表现更“平衡”。一个连续的[i,j]的范围平衡表示为K种特征都有同样多的奶牛。询问究竟可以排出一个多长的“平衡”队列。

【输入描述】

第一行两个整数n、k；

接下来n行，每行一个整数。

【输出描述】

输出一个整数表示最大的长度。

源代码：

#include<cstdio>
#include<cstring>
#define INF 999997
int n,m,ans,i[100001],S[100001][35],C[100001][35],Has[1000001];
int Get_Hash(int T)
{
    int t(0);
    for (int a=0;a<m;a++)
      t=t%INF+C[T][a]<<2;
    if (t<0)
      t=-t;
    return t%INF;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int a=1;a<=n;a++)
      scanf("%d",&i[a]);
    for (int a=1;a<=n;a++)
      for (int b=0;b<m;b++)
        if ((1<<b)&i[a])
          S[a][b]=S[a-1][b]+1;
        else
          S[a][b]=S[a-1][b];
    for (int a=1;a<=n;a++)
      for (int b=0;b<m;b++)
        C[a][b]=S[a][b]-S[a][0];
    memset(Has,-1,sizeof(Has));
    Has[0]=0;
    for (int a=1;a<=n;a++)
    {
        int t=Get_Hash(a);
        while (Has[t]!=-1)
        {
            bool Flag(0);
            for (int b=0;b<m;b++)
              if (C[Has[t]][b]!=C[a][b])
              {
                Flag=true;
                break;
              }
            if (!Flag&&a-Has[t]>ans)
            {
                ans=a-Has[t];
                break;
            }
            t++;
        }
        if (Has[t]==-1)
          Has[t]=a;
    }
    printf("%d",ans);
    return 0;
}