【POJ 3274】Gold Balanced Lineup （stl map ）设计hash表，处理碰撞

秒速五厘米 2023-06-01 14:57 22阅读 0赞

### 题目链接 ###

[题目链接 http://poj.org/problem?id=3274][http_poj.org_problem_id_3274]

### 题意 ###

输入每头牛的特征的10进制，若i~j头牛中每个数位的特征相等则满足要求，求所有满足要求的j-i的最大值。

### 解题思路 ###

1.  抽屉原理，用前缀和处理每个数位即可。
2.  直接暴力的话复杂度太大了，所以需要取巧的办法。
3.  直接暴力求解是sum\[i\]\[p\] - sum\[j\]\[p\] == sum\[i\]\[0\] - sum\[j\]\[0\]。其中i表示第i头牛，j表示第j头牛，p表示第p个特征，i > j。
4.  取巧的办法：sum\[i\]\[p\] - sum\[i\]\[0\] = sum\[j\]\[p\] - sum\[j\]\[0\]。
5.  采用取巧的办法之后，每头牛只用和自己的前缀和特征比较，时间复杂度恰好能满足要求。
6.  我们需要对每头牛的前缀和处理，sum\[i\]\[j\] -= sum\[i\]\[0\]，其中j>0，可以看到**0号特征对结果无影响**，我们只需将第1~k号特征，hash处理之后，存入hash表即可。
7.  hash表和碰撞处理自行设计，代码中是我使用的方法。

### 代码如下（G++） ###

#include <iostream> #include <string.h> #include "map" #include "string" using namespace std; typedef long long ll; double eps = 1e-7; //a[i]表示第i头牛 struct node { int s[32]; //分离特征二进制 int val; //特征10进制 } a[100010]; int n, k, ans; int sum[100010][32]; //前缀和 map<int, int> m; //hash表 //检测哈希值x是否存在，如果存在，比较是否满足要求 //l为 1 -1 2 -2 4 -4 ...... x -x 2x -2x ...... int inHash(int x, int con, int l) { if (m.find(x) != m.end()) { int f = 0; for (int i = 1; i < k; ++i) { if (sum[con][i] != sum[m[x]][i]) { f = 1; break; } } if (f) { if (l > 0) l = -1; else l *= (-2); return inHash(x + l, con, l); } else return m[x]; } else { m[x] = con; return -1; } } int main() { ios::sync_with_stdio(false); while (cin >> n >> k) { //初始化 ans = 0; memset(sum, 0, sizeof(sum)); m.clear(); for (int i = 1; i <= n; ++i) { cin >> a[i].val; int t = a[i].val; int j; //将牛的特征分离 for (j = k - 1; t != 0; --j) { a[i].s[j] = t % 2; t /= 2; } //求前缀和 for (j = 0; j < k; ++j) { sum[i][j] = sum[i - 1][j] + a[i].s[j]; } } for (int i = 0; i <= n; ++i) { //num为hash值，需要自行设计 int num = 0; for (int j = 1; j < k; ++j) { sum[i][j] -= sum[i][0]; num = num * k + sum[i][j]; } // 判断num是否在且满足要求，若满足则返会上一头牛的位置，否则返回-1 int p = inHash(num, i, 1); if (p != -1) { ans = max(ans, i - p); } } cout << ans << endl; } return 0; }

转载于:https://www.cnblogs.com/zhangjiuding/p/11480077.html

[http_poj.org_problem_id_3274]: http://poj.org/problem?id=3274