題目鏈接

很難想。會哈希，但是想不出。需要一個轉化，本來是求某一段上的二進制上每一位的1數目相等，轉化為找兩段相等的，換元可推出公式。最后注意特判。。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 using namespace std; 6 #define MOD 97777 7 struct node 8 { 9 int data; 10 struct node *next; 11 }*head[MOD],hash[60000]; 12 int sum[100001][31]; 13 int c[100001][31]; 14 int n,m; 15 int judge(int x,int y) 16 { 17 int i; 18 for(i = 0; i < m; i ++) 19 { 20 if(c[x][i] != c[y][i]) 21 return 0; 22 } 23 return 1; 24 } 25 int main() 26 { 27 int i,j,a,key,ans = 0,num = 0; 28 node *q,*t; 29 scanf("%d %d",&n,&m); 30 for(i = 1; i <= n; i ++) 31 { 32 scanf("%d",&a); 33 for(j = 0; j < m; j ++) 34 { 35 if(a&(1<<j)) 36 sum[i][j] = sum[i-1][j] + 1; 37 else 38 sum[i][j] = sum[i-1][j]; 39 } 40 } 41 for(i = 1; i <= n; i ++) 42 { 43 key = 0; 44 for(j = 1; j < m; j ++) 45 { 46 c[i][j] = sum[i][j]-sum[i][0]; 47 key += c[i][j]*j; 48 } 49 for(j = 1;j < m;j ++) 50 { 51 if(c[i][j] != 0) 52 break; 53 } 54 if(j == m&&ans < i) ans = i;//特判是否全是0 55 key = key%MOD; 56 if(key < 0) 57 key = key + MOD; 58 for(t = head[key]; t != NULL; t = t->next) 59 { 60 if(ans < (i - t->data)&&judge(i,t->data)) 61 { 62 ans = i - t->data; 63 } 64 } 65 if(t == NULL) 66 { 67 q = &hash[num++]; 68 q -> data = i; 69 q -> next = head[key]; 70 head[key] = q; 71 } 72 } 73 printf("%d\n",ans); 74 return 0; 75 }

?

轉載于:https://www.cnblogs.com/naix-x/archive/2013/01/14/2860223.html

總結

以上是生活随笔為你收集整理的POJ 3274 Gold Balanced Lineup(哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。