GoldBalancedLineuphash函数，第一次接触，借鉴了大神的博客思想，看了很久才看懂，弱菜啦

  1 /*
  2 数组sum[i][j]表示从第1到第i头cow属性j的出现次数。
  3 
  4 所以题目要求等价为:
  5 
  6 求满足
  7 
  8 sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=.....=sum[i][k-1]-sum[j][k-1] (j  9 
 10 中最大的i-j
 11 
 12  
 13 
 14 将上式变换可得到
 15 
 16 sum[i][1]-sum[i][0] = sum[j][1]-sum[j][0]
 17 
 18 sum[i][2]-sum[i][0] = sum[j][2]-sum[j][0]
 19 
 20 ......
 21 
 22 sum[i][k-1]-sum[i][0] = sum[j][k-1]-sum[j][0]
 23 
 24  
 25 
 26 令C[i][y]=sum[i][y]-sum[i][0] (0 27 
 28 初始条件C[0][0~k-1]=0
 29 
 30  
 31 
 32 所以只需求满足C[i][]==C[j][] 中最大的i-j，其中0<=j 33 
 34 C[i][]==C[j][] 即二维数组C[][]第i行与第j行对应列的值相等，
 35 
 36 那么原题就转化为求C数组中 相等且相隔最远的两行的距离i-j。
 37 */
 38 #include
 39 #include<string>
 40 #include
 41 #include
 42 #include
 43 using namespace std;
 44 const int maxn=107777;
 45 int hash[maxn],c[maxn][50],sum[maxn];
 46 int i,j,k,n,m;
 47 //min_index[]数组代表相等的上一行的下标
 48 int min_index[maxn],next[maxn];
 49 bool  judge(int a,int b)//判断a行和b行是否相等
 50 {
 51     for(int it=0;it)
 52     {
 53         if(c[a][it]!=c[b][it])
 54           return false;
 55     }
 56     return true;
 57 }
 58 int hashcode(int *v)//hash函数
 59 {
 60    int s=0;
 61    for(int it=0;it)
 62    {
 63        s=((s<<2)+(v[it]>>4))^(v[it]<<10);
 64    }
 65    s=s%maxn;
 66    if(s<0)
 67     s=s+maxn;
 68    return s;
 69 }
 70 int all_0(int index)//判断一行是否为0
 71 {
 72    for(int it=0;it)
 73    {
 74        if(c[index][i]!=0)
 75          return false;
 76    }
 77    return true;
 78 }
 79 void insert(int index)
 80 {
 81     int h=hashcode(c[index]);
 82     if(!h)
 83     {
 84         if(all_0(index))
 85         {
 86             min_index[index]=0;
 87             return;
 88         }
 89     }
 90     int u=hash[h];
 91     if(!u)//如果hash数组为0，则赋值
 92     {
 93         min_index[index]=index;
 94         hash[h]=index;
 95         return;
 96     }
 97     while(u)
 98     {
 99         if(judge(index,u))//找到相等的，则返回
100         {
101             min_index[index]=min_index[u];
102             return;
103         }
104         u=next[u];
105     }
106     min_index[index]=index;
107     next[index]=hash[h];
108     hash[h]=index;
109 
110 }
111 int main()
112 {
113     while(~scanf("%d%d",&n,&k))
114     {
115         memset(c,0,sizeof(c));
116         memset(min_index,0,sizeof(min_index));
117         memset(next,0,sizeof(next));
118         memset(hash,0,sizeof(hash));
119         int sum[39]={0},num,max1=0;
120         for(i=1;i<=n;i++)
121         {
122             scanf("%d",&num);
123             for(j=0;j)
124             {
125                 sum[j]+=((1<1:0;
126                 c[i][j]=sum[j]-sum[0];
127             }
128             insert(i);
129         }
130         for(i=1;i<=n;i++)//求最大值
131         {
132             if(max1min_index[i])
133              max1=i-min_index[i];
134         }
135         printf("%d\n",max1);
136     }
137     return 0;
138 }