這題，看到別人的解題報告做出來的，分析：

大概意思就是：

數組sum[i][j]表示從第1到第i頭cow屬性j的出現次數。

所以題目要求等價為:

求滿足

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][] 即二維數組C[][]第i行與第j行對應列的值相等，

那么原題就轉化為求C數組中 相等且相隔最遠的兩行的距離i-j

大概意思就是：

數組sum[i][j]表示從第1到第i頭cow屬性j的出現次數。

所以題目要求等價為:

求滿足

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][] 即二維數組C[][]第i行與第j行對應列的值相等，

那么原題就轉化為求C數組中 相等且相隔最遠的兩行的距離i-j

以樣例為例

7 3 7 6 7 2 1 4 2 ?

先把7個十進制特征數轉換為二進制，并逆序存放到特征數組feature[ ][ ]，得到：

7 ->1 1 1

6 ->0 1 1

7 ->1 1 1

2 ->0 1 0

1 ->1 0 0

4 ->0 0 1

2 ->0 1 0

（行數為cow編號，自上而下從1開始；列數為特征編號，自左到右從0開始）

?

再求sum數組，逐行累加得，sum數組為

?1 1 1

1 2 2

2 3 3

2 4 3

3 4 3

3 4 4

3 5 4

再利用C[i][y]=sum[i][y]-sum[i][0]求C數組，即所有列都減去第一列

注意C數組有第0行，為全0

?0 0 0 -> 第0行

0 0 0

0 1 1 ?<------

0 1 1

0 2 1

0 1 0

0 1 1 <-------

0 2 1

顯然第2行與第6行相等，均為011，且距離最遠，距離為6-2=4，這就是所求。

#include<stdio.h> #include<stdlib.h> #include<string.h> int num[100002][31]; int N,K; struct hash{int ind;hash* next; }; hash hashtable[100002]; int gethash(int id){num[id][0]=0;for(int i=1;i<K;i++){num[id][0]+=num[id][i]*i;}num[id][0]=(num[id][0]&0x7fffffff)%100002; return num[id][0]; } int isEqual(int id1,int id2){int flag=1;for(int i=1;i<K;i++){if(num[id1][i]!=num[id2][i]){flag=0;}}return flag; } int main(){scanf("%d %d",&N,&K);for(int j=0;j<K;j++){num[0][j]=0;}memset(hashtable,0,sizeof(hash)*100002);for(int i=1;i<=N;i++){int t;scanf("%d",&t);for(int j=0;j<K;j++){num[i][j]=t%2;t=t>>1;num[i][j]+=num[i-1][j];}}int result=0;for(int i=0;i<=N;i++){for(int j=1;j<K;j++){num[i][j]-=num[i][0];}int h=gethash(i);hash *t=(hash*)malloc(sizeof(hash));t->next=hashtable[h].next;t->ind=i;hashtable[h].next=t;while(t!=NULL){if(isEqual(t->ind,i)){int tmp=i-t->ind;result=result>tmp?result:tmp;}t=t->next;}} printf("%d\n",result);return 0; }

?

?

Time Limit:?2000MS	?	Memory Limit:?65536K
Total Submissions:?13200	?	Accepted:?3866

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

Hint

In the range from cow #3 to cow #6 (of size 4), each feature appears in exactly 2 cows in this range

轉載于:https://www.cnblogs.com/sdxk/p/4707660.html

總結

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

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