考察：hash+前缀和
做完这道题感觉终于懂一点hash了,散列表hash是将值存储在映射的键里,会有不同值映射到相同键,因此必须要处理冲突
这道题牛二进制的前缀和会根据ash函数映射到相同键,这些前缀和有些和答案要求根本不符,所以我们必须筛掉那些不符合的键,也就是说这道题我们不能仅仅存储牛的前缀和映射,因为有和答案不符的会映射到相同键,再存储相同键的时候,我们必须再在相同键里看牛的每一位前缀和是否相同,相同的才是答案
借鉴大佬的思路：
luogu题解的分析比一些csdn的题解写详细多了....建议看luogu的题解.总之需要牛的每一位属性值区间内个数相同,我们必须想到前缀和思想,每一位的前缀和之差相同就是个数增长相同.想到这和上面那些基本就可以做出来了
注意返回的键值不能为负
涉及前缀和一定要考虑边界0
这道题直接存储下标,这样就不用结构体记录id
用开放地址法就是相等的时候要判断cnt是否相同
1 #include <iostream>
2 #include <map>
3 #include <vector>
4 using namespace std;
5 const int N = 100007;
6 int ans,n,k;//hash 会WA的原因,不同的值会映射到相同的键,必须减少冲突
7 int cnt[N][32],h[N];
8 vector<int> v[N];
9 int gethash(int i)
10 {
11 int tmp = 0;
12 for(int j=1;j<=k;j++)
13 tmp = tmp*2+cnt[i][j],tmp%=N;
14 return abs(tmp)%N;
15 }
16 bool same(int i,int j)
17 {
18 for(int x=1;x<=k;x++){
19 if(cnt[i][x]!=cnt[j][x]) return false;
20 }
21 return true;
22 }
23 int main()
24 {
25 scanf("%d%d",&n,&k);
26 for(int i=1;i<=n;i++){
27 int x;
28 scanf("%d",&x);
29 for(int j=1;j<=k;j++) cnt[i][j]=((x>>(j-1))&1)+cnt[i-1][j];
30 }
31 for(int i=0;i<=n;i++){
32 for(int j=k;j>=1;j--) cnt[i][j]-=cnt[i][1];
33 int id = gethash(i);//得到第i头牛的属性和对于哈希值
34 // printf("id==%d\n",id);
35 v[id].push_back(i);//得到i头牛对应属性
36 }
37 for(int i=0;i<N;i++){
38 if(v[i].size()<2) continue;
39 for(int j=0;j<v[i].size();j++){
40 for(int p=j+1;p<v[i].size();p++){
41 if(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);
46 return 0;
47 }