POJ 3274 Gold Balanced Lineup

Gold Balanced Lineup
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 5164
 
Accepted: 1631
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 theK 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
Source
USACO 2007 March Gold
 
 
이 문제는 확실히 잘 나왔다
우선 문제의 전환, 어떻게 가장 큰 거리를 찾는가
그럼 예를 한번 볼게요.

7 3
7
6
7
2
1
4
2

2진법으로 전환
111
110
111
010
001
백
010
하나하나
111
221
332
342
343
443
453
각각 맨 오른쪽의 수를 빼다
000
110《----
110
120
010110《----
120
2와 6이 가장 먼 숫자라는 것을 알 수 있다. 그러면 6-2=4만으로 답을 계산할 수 있다
 
그럼 도대체 왜 이러는 게 맞지?
왜 두 수가 똑같아서 정답을 얻었을까?
이렇게 이해할 수 있다. 두 수가 동시에 나타나면 이 두 수 사이에 나타난 수가 각 특징에 나타난 수가 같다는 것을 설명한다. 그렇지 않으면 두 수가 같지 않을 것이다.맨 오른쪽의 그 수가 왼쪽의 모든 수가 증가한 숫자와 같아야만 그들은 맨 오른쪽의 수를 빼고 똑같은 수가 나타날 수 있기 때문이다
 
이어서 HASH를 사용할 수도 있고 MAP를 사용할 수도 있습니다. 저는 MULTIMAP를 사용할 필요가 없다고 생각합니다. 왜냐하면 모든 숫자 형식이 나타나는 가장 빠른 시기만 기록하면 되기 때문입니다.
HASH 함수에 00000000000을 추가하는 것을 주의하십시오.
 
 
#include#includeconst int N=100100;const int prime=100003;int sum[N][32],c[N][32];int hash[N];int hashcode(int* v,int k){    int p;    for(int i=1;i<=k;i++)  p=((p<<2)+(v[i]>>4))^(v[i]<<10);    p=p%prime;    if(p<0)  p=p+prime;    return p;}int main(){   //freopen("lineup.10.in","r",stdin);   //freopen("out.txt","w",stdout);    int n,k;    int ans=0;    while(scanf("%d%d",&n,&k)!=EOF)    {        memset(sum,0,sizeof(sum));        memset(hash,-1,sizeof(hash));        memset(c,0,sizeof(c));        hash[hashcode(c[0],k)]=0;        ans=0;        for(int i=1;i<=n;i++)        {            int x;            scanf("%d",&x);            for(int j=1;j<=k;j++)            {                sum[i][j]=sum[i-1][j]+x%2;                c[i][j]=sum[i][j]-sum[i][1];                x=x>>1;            }           int p=hashcode(c[i],k);           while(hash[p]!=-1)            {                int j;                for(j=1;j<=k;j++)                    if(c[i][j]!=c[hash[p]][j])  break;                if(j==k+1)                {                    if(i-hash[p]>ans)  ans=i-hash[p];                    break;                }                p++;            }            if(hash[p]==-1)  hash[p]=i;        }        printf("%d/n",ans);    }    return 0;}