POJ-3274 Gold Balanced Lineup---hash经典题！-白红宇

POJ-3274 Gold Balanced Lineup---hash经典题！

阅读量：6981 次

发布时间：2019-06-27

本文共 2478 字，大约阅读时间需要 8 分钟。

题目链接：

题目大意：

给定多头牛的属性，每头牛的属性由一个非负数表示，该数的二进制表示不会超过K位，它的二进制表示的每一位若为1则表示该牛有对应的第i种属性，若为0则表示没有该属性。

对于给定的牛的顺序，要求输出某一段子序列的长度，这个子序列中的牛的K个属性对应相加以后全部相等。

假设n=3, k = 3

输入的3个数变成的二进制分别为(a1, a2, a3), (b1, b2, b3), (c1, c2, c3)

设sum(i)为从第1个数到第i个数的属性和的序列

若从第2个数到第3个数的序列满足条件，则说明b1+c1 = b2+c2 = b3+c3，即sum(3)-sum(2)的序列每一位都相等

推广一下，若sum(i) = (a, b, c)，sum(j) = (d, e, f)，且i到j这个子序列满足条件，则说明(d, e, f) - (a, b, c) = (x, x, x)，即(d, e, f) = (a + x, b + x, c + x)。每个序列中的数都减去序列中的最后一个数，得到(d - f, e - f, 0) = (a - c, b - c, 0)。因此只要判断两个完全转换过后的序列是否相同，就可以知道它们之间的原序列是否满足条件了。

所以解题的第一步是把原来的数转换为二进制序列，第二步是把二进制序列转换成sum序列，即逐步叠加，第三步是把每个sum序列都减去该序列的最后一个数，最后一步是把这些序列进行哈希，计算它们的最大差距。

有一点要注意，如果从第1个数到第i个数这段序列满足条件，即sum(i) - sum(0) = (x, x, x)，则说明sum(i)的各个位都是相同的，因此需要在第三步之前先做这个判断，把符合条件的序列找出来，更新一下答案。所以在hash的时候先存入hash(0)

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
          6 #include
          
            7 #include
           
             8 using namespace std; 9 const int maxn = 100000 + 10;10 const int mod = 99991;11 int num[maxn][32];12 int n, k;13 int maxlen;14 struct hashtable15 {16 int x;17 hashtable * next;18 hashtable(){next = 0;}19 };20 hashtable * Hash[mod];21 22 bool Equal(int i, int j)23 {24 for(int c = 1; c < k; c++)25 if(num[i][c] != num[j][c])return false;26 return true;27 }28 void Hash_Insert(int i)29 //根据关键字key找hash位置, 找到位置后存i表示第i行30 {31 int key = 0;32 for(int j = 1; j < k; j++)33 key += j * num[i][j];34 key = abs(key) % mod;35 if(!Hash[key])//链表的第一个key36 {37 hashtable* p = new hashtable;38 p -> x = i;39 Hash[key] = p;40 }41 else//产生冲突42 {43 hashtable * p = Hash[key];44 if(Equal(p->x, i))//如果和第i行相等45 {46 int dist = i - (p -> x);47 maxlen = max(maxlen, dist);48 }49 else50 {51 while(p->next)//判断p->next是否存在，之后直接判断p->next存的行数和当前行数比较52 {53 if(Equal(p->next->x, i))54 {55 int dist = i - (p -> next -> x);56 maxlen = max(maxlen, dist);57 return;//不用存储i，直接返回，因为已经有和i一样的58 }59 p = p->next;60 }61 //地址冲突但是和每个冲突的都不相同62 hashtable* temp = new hashtable;63 temp->x = i;64 p->next = temp;65 }66 }67 return;68 }69 int main()70 {71 scanf("%d%d", &n, &k);72 int x;73 for(int i = 1; i <= n; i++)74 {75 scanf("%d", &x);76 for(int j = 0; j < k; j++)77 if(x & (1 << j))num[i][j] = 1;78 for(int j = 0; j < k; j++)79 num[i][j] += num[i - 1][j];80 }81 for(int i = 1; i <= n; i++)82 {83 for(int j = 1; j < k; j++)84 num[i][j] -= num[i][0];85 }86 for(int i = 0; i <= n; i++)Hash_Insert(i);//从第0行开始87 cout<
            
             <

转载于:https://www.cnblogs.com/fzl194/p/8946729.html

你可能感兴趣的文章