Gold Balanced Lineup POJ - 3274

             1 #include <iostream>
 2 #include <map>
 3 #include <vector>
 4usingnamespace std;
 5constint N = 100007;
 6int ans,n,k;//hash 会WA的原因,不同的值会映射到相同的键,必须减少冲突  7int cnt[N][32],h[N];
 8 vector<int> v[N];
 9int gethash(int i)
10{
11int tmp = 0;
12for(int j=1;j<=k;j++)
13         tmp = tmp*2+cnt[i][j],tmp%=N;
14return abs(tmp)%N;
15}
16bool same(int i,int j)
17{
18for(int x=1;x<=k;x++){
19if(cnt[i][x]!=cnt[j][x]) returnfalse;
20    }
21returntrue;
22}
23int main()
24{
25     scanf("%d%d",&n,&k);
26for(int i=1;i<=n;i++){
27int x;
28         scanf("%d",&x);
29for(int j=1;j<=k;j++) cnt[i][j]=((x>>(j-1))&1)+cnt[i-1][j];    
30    }
31for(int i=0;i<=n;i++){
32for(int j=k;j>=1;j--) cnt[i][j]-=cnt[i][1];
33int id = gethash(i);//得到第i头牛的属性和对于哈希值 
34//    printf("id==%d\n",id);35         v[id].push_back(i);//得到i头牛对应属性 36    }
37for(int i=0;i<N;i++){
38if(v[i].size()<2) continue;
39for(int j=0;j<v[i].size();j++){
40for(int p=j+1;p<v[i].size();p++){
41if(same(v[i][j],v[i][p])) ans = max(ans,abs(v[i][j]-v[i][p]));
42            }
43        }
44    }
45     printf("%d\n",ans);
46return0;
47 }