首页 > 代码库 > poj 3274 Gold Balanced Lineup, 拉链式hash
poj 3274 Gold Balanced Lineup, 拉链式hash
sum[i][j] 表示从第1到第i头cow属性j的出现次数
所以题目要求等价为:
求满足
sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=.....=sum[i][k-1]-sum[j][k-1] (j<i)
中最大的i-j
将上式变换可得到
sum[i][1]-sum[i][0] = sum[j][1]-sum[j][0]
sum[i][2]-sum[i][0] = sum[j][2]-sum[j][0]
......
sum[i][k-1]-sum[i][0] = sum[j][k-1]-sum[j][0]
令C[i][y]=sum[i][y]-sum[i][0] (0<y<k)
初始条件C[0][0~k-1]=0
所以只需求满足C[i][]==C[j][] 中最大的i-j,其中0<=j<i<=n。
C[i][]==C[j][] 即二维数组C[][]第i行与第j行对应列的值相等,
那么原题就转化为求C数组中 相等且相隔最远的两行的距离i-j。
将C[i]进行hash,
这样就可以高效的找到i前面C[i]=C[j]的所有j了。
采用拉链式hash表能有效的避免冲突
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100000 + 5; const int maxk = 30 + 5; const int mod = 99983; int sum[maxn][maxk], c[maxn][maxk]; int head[maxn], next[maxn], v[maxn], ecnt; int n, k; void addedge(int a, int b) { next[ecnt] = head[a]; head[a] = ecnt; v[ecnt] = b; ecnt++; } // BKDR Hash Function int hash(int *v) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; for(int i=0; i<k; ++i) hash = hash * seed + v[i]; return (hash & 0x7FFFFFFF) % mod; } int main() { memset(sum, 0, sizeof sum ); memset(c, 0, sizeof c ); memset(head, -1, sizeof head ); ecnt = 0; int ans = 0; addedge(hash(c[0]), 0); scanf("%d%d", &n, &k); for(int i=1; i<=n; ++i) { int a; scanf("%d", &a); for(int j=0; j<k; ++j) { sum[i][j] = sum[i-1][j] + (1&a); c[i][j] = sum[i][j] - sum[i][0]; a >>= 1; } int h = hash(c[i]); for(int j=head[h]; j != -1; j=next[j]) { bool flag = true; for(int p=0; p<k; ++p) if(c[v[j]][p] != c[i][p]) { flag = false; break; } if(flag && ans < i-v[j]) ans = i - v[j]; } addedge(h, i); } printf("%d\n", ans); return 0; } /* 7 3 7 6 7 2 1 4 2 ans: 4 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。