首页 > 代码库 > poj3274（Gold Balanced Lineup）
poj3274（Gold Balanced Lineup）
题目地址：Gold Balanced Lineup
题目大意：
一个农场有N个奶牛，每个奶牛都有不同的特征，聪明的农夫给奶牛 feature ID。代表奶牛所具有的特征。将feature ID 写成为K位的二进制的数，其中有1的位置代表奶牛具有此特征，0代表没有此特征。从i->j 使这个区间的奶牛所有特征的个数是相等的。其中最大的区间差就是题图所求的。
解题思路：
解题思路：
经典题，不转化问题很难做，先根据官方的方法转化问题，把“求最远的两行间各个特征出现次数相等”转化为“求最远的相同两行”，再用Hash查找。
这是官方解题报告——
Consider the partial sum sequence of each of the k features built by taking the
sum of all the values up to position i. The problem is equivalent to:
Given an array s[n][k], find i,j, with the biggest separation for which s[ i ]
[l]-s[j][l] is constant for all l.
The problem is now to do this efficiently. Notice that s[ i ][l]-s[j][l] being
constant for all l is equivalent to s[ i ][l]-s[j][l]=s[ i ][1]-s[j][1] for all
l, which can be rearranged to become s[ i ][l]-s[ i ][1]=s[j][l]-s[j][1] for all
l. Therefore, we can construct another array a[n][k] where a[ i ][j]=s[ i ][j]-
s[ i ][1] and the goal is to find i and j with the biggest separation for which
a[ i ][l]=a[j][l] for all l.
This can be done by sorting all the a[ i ] entries, which takes O(nklogn) time
(although in practice rarely will all k elements be compared). Another
alternative is to go by hashing, giving an O(nk) solution. Both solutions are
fairly straightforward once the final array is constructed.
大概意思就是：
数组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，这就是所求。
需要注意:
但是最大数据有10W个，即10W行，因此不能直接枚举找最大距离，必须用Hash查找相同行，找到相同行再比较最大距离。
我哈希是将K个数求和sum%N，然后放到一个vector里，然后一一比较找出相同序列，哈希的过程中数组可能是负数，所以记得处理负数的可能。
一个疑问： 如果100000个sum%N的数想同，我代码是不是就超时了呢。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 31 /***************************************/ 32 void openfile() 33 { 34 freopen("data.in","rb",stdin); 35 freopen("data.out","wb",stdout); 36 } 37 /**********************华丽丽的分割线,以上为模板部分*****************/ 38 const int N=1999; 39 const int MMM=100001; 40 int n,kk; 41 int mm; 42 int maax; 43 int c[N][35]; 44 typedef struct 45 { 46 int a[35]; 47 int sum; 48 int m; 49 }node; 50 node bit[MMM]; 51 vector <node >vc[N]; 52 int cmp() 53 { 54 int i,j,k,h; 55 mm=0; 56 maax=0; 57 for(i=0;i<N;i++) 58 for(j=0;j<vc[i].size();j++) 59 { 60 node n1=vc[i][j]; 61 for(k=j+1;k<vc[i].size();k++) 62 { 63 node n2=vc[i][k]; 64 if (n1.sum==n2.sum) 65 { 66 for(h=0;h<kk;h++) 67 if(n1.a[h]!=n2.a[h]) 68 break; 69 if (h==kk) 70 { 71 mm=abs(n1.m-n2.m); 72 if (maax<mm) 73 maax=mm; 74 } 75 } 76 } 77 } 78 return 0; 79 } 80 int main() 81 { 82 while(scanf("%d%d",&n,&kk)!=EOF) 83 { 84 int i,j; 85 memset(bit,0,sizeof(bit)); 86 memset(c,0,sizeof(c)); 87 int x,y; 88 for(i=1;i<=n;i++) 89 { 90 scanf("%d",&x); 91 for(j=0;j<kk;j++) 92 { 93 y=x&1; 94 bit[i].a[j]=bit[i-1].a[j]+y; 95 x>>=1; 96 } 97 } 98 // int sum=0; 99 for(i=0;i<=n;i++)100 {101 bit[i].sum=0;102 x=bit[i].a[0];103 for(j=0;j<kk;j++)104 {105 bit[i].a[j]-=x;106 bit[i].sum+=bit[i].a[j];107 }108 bit[i].m=i;109 vc[(bit[i].sum+MMM)%N].push_back(bit[i]);110 }111 cmp();112 printf("%d\n",maax);113 for(i=0;i<N;i++)114 vc[i].clear();115 }116 return 0;117 }118 /*119 SAMPLE binary add sub120 7 3 0 0 0121 7 -> 1 1 1 1 1 1 0 0 0122 6 -> 1 1 0 2 2 1 1 1 0<---123 7 -> 1 1 1 ---> 3 3 2 --> 1 1 0 |124 2 -> 0 1 0 3 4 2 1 2 0 |4125 1 -> 0 0 1 3 4 3 0 1 0 |126 4 -> 1 0 0 4 4 3 1 1 0<---127 2 -> 0 1 0 4 5 3 1 2 0128 7 3129 7130 6131 7132 2133 1134 4135 2136 4137 138 7 3139 7 7 7 7 7 7 7140 7141 142 4 4143 1144 2145 4146 8147 4148 149 4 4150 8151 1152 2153 4154 4155 156 5 4157 3158 1159 2160 4161 8162 4163 164 1 5165 3166 0167 168 1 2169 3170 1171 172 1 3173 7174 1175 */