poj3274Gold Balanced Lineup

http://poj.org/problem?id=3274

网上题解

数组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。

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 #define size 200010
 8 #define MOD 97777
 9 int sum[100010][31],c[100010][31],t,head[size+10],next[size+10],v[size+10];
10 void init()
11 {
12     t = 0;
13     memset(head,-1,sizeof(head));
14 }
15 void add(int a,int b)
16 {
17     next[t] = head[a];
18     head[a] = t;
19     v[t] = b;
20     t++;
21 }
22 int main()
23 {
24     int i,j,k,n,g,x,bi[31];
25     while(cin>>n>>k)
26     {
27         init();
28         memset(sum,0,sizeof(sum));
29         memset(c,0,sizeof(c));
30         for(i = 1; i <= n ; i++)
31         {
32             cin>>x;
33             g = 0;
34             while(x)
35             {
36                 g++;
37                 j = x%2;
38                 sum[i][g]=j;
39                 x = x/2;
40             }
41             for(j = 1 ; j <= k  ; j++)
42             sum[i][j]+=sum[i-1][j];
43         }
44         int mi = 0;
45         for(i = 1; i <= n ; i++)
46         {
47             int s = 0;
48             for(j = 2 ; j <= k ;j++)
49             {
50                 c[i][j] = sum[i][j]-sum[i][1];
51                 s = c[i][j]*j;//哈希
52             }
53             for(j = 2 ; j <= k ;j++)
54                 if(c[i][j]!=0)  break;
55             if(j==k+1&&mi<i) mi = i;
56             s = s%MOD;
57             if(s<0) s+=MOD;
58             int flag = 0,a;
59             for(j = head[s] ; j!=-1 ; j = next[j])//解决冲突
60             {
61                 flag = 1;
62                 for(a = 2 ; a <= k  ; a++)
63                 {
64                     if(c[i][a]!=c[v[j]][a])
65                     {
66                         flag = 0;
67                         break;
68                     }
69                 }
70                 if(flag&&mi<i-v[j])
71                 mi = i-v[j];
72             }
73             add(s,i);
74         }
75         cout<<mi<<endl;
76     }
77     return 0;
78 }