Gold Balanced Lineup

Time Limit: 2000MS	?	Memory Limit: 65536K
Total Submissions: 10360	?	Accepted: 3086

Description

Farmer John's N cows (1 ≤ N ≤ 100,000) share many similarities. In fact, FJ has been able to narrow down the list of features shared by his cows to a list of only K different features (1 ≤ K ≤ 30). For example, cows exhibiting feature #1 might have spots, cows exhibiting feature #2 might prefer C to Pascal, and so on.

FJ has even devised a concise way to describe each cow in terms of its "feature ID", a single K-bit integer whose binary representation tells us the set of features exhibited by the cow. As an example, suppose a cow has feature ID = 13. Since 13 written in binary is 1101, this means our cow exhibits features 1, 3, and 4 (reading right to left), but not feature 2. More generally, we find a 1 in the 2^(i-1) place if a cow exhibits feature i.

Always the sensitive fellow, FJ lined up cows 1..N in a long row and noticed that certain ranges of cows are somewhat "balanced" in terms of the features the exhibit. A contiguous range of cows i..j is balanced if each of the K possible features is exhibited by the same number of cows in the range. FJ is curious as to the size of the largest balanced range of cows. See if you can determine it.

Input

Line 1: Two space-separated integers, N and K.
Lines 2..N+1: Line i+1 contains a single K-bit integer specifying the features present in cow i. The least-significant bit of this integer is 1 if the cow exhibits feature #1, and the most-significant bit is 1 if the cow exhibits feature #K.

Output

Line 1: A single integer giving the size of the largest contiguous balanced group of cows.

Sample Input

7 3 7 6 7 2 1 4 2

Sample Output

4

題目大意就是說(shuō)n個(gè)數(shù)，表示n頭牛所具有的特性，在化為二進(jìn)制之后哪一位是1表示具有哪種特性，問(wèn)最長(zhǎng)連續(xù)有多少個(gè)牛，它們所有每一種特性的和相等，如：
7->1 1 1
6->1 1 0
7->1 1 1
2->0 1 0
1->0 0 1
4->1 0 0
2->0 1 0
這樣的話從第3行到第6行共4行的長(zhǎng)度，它們3種特性的和都為2

大概意思就是：

數(shù)組sum[i][j]表示從第1到第i頭cow屬性j的出現(xiàn)次數(shù)。

所以題目要求等價(jià)為:

求滿足

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][] 即二維數(shù)組C[][]第i行與第j行對(duì)應(yīng)列的值相等，

那么原題就轉(zhuǎn)化為求C數(shù)組中 相等且相隔最遠(yuǎn)的兩行的距離i-j。

?

這樣的話就只需要對(duì)數(shù)組c進(jìn)行哈希，下面是網(wǎng)上借鑒來(lái)的哈希函數(shù)

inline int hashcode(const int *v){int s = 0;for(int i=0; i<k; i++)s=((s<<2)+(v[i]>>4))^(v[i]<<10);s = s % M;s = s < 0 ? s + M : s;return s;}


另外，在尋找最長(zhǎng)滿足條件區(qū)間長(zhǎng)度的時(shí)候，我用了一個(gè)數(shù)組min_index來(lái)存放兩行相同時(shí)上面一行的下標(biāo)。最初min_index[i]=i.之后一旦找到一個(gè)c[j]=c[i],那么min_index[j]=min_index[i].這樣的話最大的i-min_index[i]就是最常去肩長(zhǎng)度。
當(dāng)然，還有更多較好的方法，如用結(jié)構(gòu)體放最長(zhǎng)長(zhǎng)度，一邊插入就可以一邊找到最大長(zhǎng)度。
下面附上代碼： 1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define MAX 100005 6 #define maxn 107777 7 8 int hash[maxn+5],next[MAX],c[MAX][32],min_index[MAX]; 9 int n,k; 10 11 int abss(int a)//坑爹的code block，不能直接調(diào)用abs 12 { 13 return a>=0?a:-a; 14 } 15 16 bool judge(int a,int b)//判斷兩行是否相同 17 { 18 int i; 19 for(i=0;i<k;i++) 20 { 21 if(c[a][i]!=c[b][i])return false; 22 } 23 return true; 24 } 25 26 inline int hashcode(const int *v)//哈希函數(shù) 27 { 28 int s = 0; 29 for(int i=0; i<k; i++) 30 s=((s<<2)+(v[i]>>4))^(v[i]<<10); 31 s = s % maxn; 32 s = s < 0 ? s + maxn : s; 33 return s; 34 } 35 36 bool all_0(int index)//判斷這一行是不是全部為0， 37 //是的話那么它與他之前的所有行組合起來(lái)可以滿足條件 38 { 39 int i; 40 for(i=0;i<k;i++) 41 { 42 if(c[index][i]!=0)return false; 43 } 44 return true; 45 } 46 47 void insert(int index)//插入第index行的c[index] 48 { 49 int h=hashcode(c[index]); 50 if(!h)//這一行里面全是 0 51 { 52 if(all_0(index)){ 53 min_index[index]=0; 54 return ; 55 } 56 } 57 int u=hash[h]; 58 if(!u) 59 { 60 min_index[index]=index; 61 hash[h]=index; 62 return; 63 } 64 while(u) 65 { 66 if(judge(index,u))//如果找到一行與這行相同，就把這條鏈最小下標(biāo)傳過(guò)去 67 { 68 min_index[index]=min_index[u]; 69 return; 70 } 71 u=next[u]; 72 } 73 min_index[index]=index; 74 next[index]=hash[h]; 75 hash[h]=index; 76 } 77 78 int main() 79 { 80 // freopen("in.txt","r",stdin); 81 // freopen("out1.txt","w",stdout); 82 while(~scanf("%d%d",&n,&k)) 83 { 84 mem(hash); 85 mem(next); 86 mem(min_index); 87 mem(c); 88 89 int sum[32]={0},i,j,num; 90 for(i=1;i<=n;i++) 91 { 92 scanf("%d",&num); 93 for(j=0;j<k;j++) 94 { 95 sum[j]+=( ( (1<<j)&(num) )?1:0 ); 96 c[i][j]=sum[j]-sum[0]; 97 } 98 insert(i); 99 } 100 int max=0; 101 for(i=1;i<=n;i++) 102 { 103 max=max>(i-min_index[i])?max:(i-min_index[i]); 104 } 105 printf("%d\n",max); 106 } 107 return 0; 108 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/gj-Acit/archive/2013/05/20/3089047.html

總結(jié)

以上是生活随笔為你收集整理的POJ3274Gold Balanced Lineup(哈希)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。