POJ 3274 Gold Balanced Lineup（哈希）

Posted on | In | 阅读

给定一串K位二进制数字，需要给出最大区间的大小，使得在这个区间内每一位数字的和相等。

设一个数组sum[i][k]用于记录从第一个数字到第i个数字中第k位数字的和，这样就可以简单地计算出任意一个区间内每一位数字的和，也就是要求出sum[j][k] - sum[i][k]对于所有k都相等的区间[i, j]。

但是这样直接搜索的复杂度是O(N2)，所以需要用哈希来简化。

sum[j][0] - sum[i][0] = sum[j][1] - sum[i][1]

有

sum[j][1] - sum[j][0] = sum[i][1] - sum[i][0]

所以只要结点满足第k位数的总数与第0位数的总数差相等就可以。这一步可以使用哈希策略，详见代码。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>

#define N 100010
#define K 32
#define HASH 100000

using namespace std;

struct node{
    int index;
    int num[K];
};

vector<node> table[HASH];
int sum[K];

int main(){
    int n, k, feature, hash, ans;
    node tmp;
    while(~scanf("%d%d", &n, &k)){
        memset(sum, 0, sizeof(sum));
        memset(tmp.num, 0, sizeof(tmp.num));
        ans = 0;
        tmp.index = 0;
        for(int i = 0; i < HASH; i++){
            table[i].clear();
        }
        table[0].push_back(tmp);
        for(int i = 1; i <= n; i++){
            hash = 0;
            scanf("%d", &feature);
            for(int j = 0; j < k; j++){
                if((feature >> j) & 1){
                    sum[j]++;
                }
                if(j > 0){
                    tmp.num[j] = sum[j] - sum[0];
                    hash += tmp.num[j] * j;
                }
            }
            tmp.index = i;
            hash = abs(hash) % HASH;
            for(int j = 0; j < table[hash].size(); j++){
                bool flag = true;
                for(int l = 0; l < k; l++){
                    if(table[hash][j].num[l] != tmp.num[l]){
                        flag = false;
                        break;
                    }
                }
                if(flag == true){
                    ans = max(ans, tmp.index - table[hash][j].index);
                }
            }
            table[hash].push_back(tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}