POJ3274-Gold Balanced Lineup

来源:转载

转载请注明出处:優YoU  http://user.qzone.qq.com/289065406/blog/1309220772

 

大致题意:


解题思路:

经典题,不转化问题很难做,先根据官方的方法转化问题,把“求最远的两行间各个特征出现次数相等”转化为“求最远的相同两行”,再用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查找相同行,找到相同行再比较最大距离。

注意C数组的值可能为负数,因此生成key值时要注意保证key为非负数。

 

Source修正:

USACO 2007 March Gold

http://www.cppblog.com/Felicia/archive/2007/12/29/39923.html

 

 官方对Hint的解释:


INPUT DETAILS:

The line has 7 cows with 3 features; the table below summarizes the
correspondence:
             Feature 3:   1   1   1   0   0   1   0
             Feature 2:   1   1   1   1   0   0   1
             Feature 1:   1   0   1   0   1   0   0
             Key:         7   6   7   2   1   4   2
             Cow #:       1   2   3   4   5   6   7

OUTPUT FORMAT:

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


OUTPUT DETAILS:

In the range from cow #3 to cow #6 (of size 4), each feature appears
in exactly 2 cows in this range:
             Feature 3:     1   0   0   1  -> two total
             Feature 2:     1   1   0   0  -> two total
             Feature 1:     1   0   1   0  -> two total
             Key:           7   2   1   4
             Cow #:         3   4   5   6

*********************************************************************

 1 //Memory Time
2 //44152K 1141MS
3
4 #include<iostream>
5 #include<cmath>
6 using namespace std;
7
8 const int size=100001;
9 const int mod=99991;
10
11 int feature[size][30]; //feature[i][j]标记第i只牛是否有特征j
12 int sum[size][30]; //从第1到第i只牛,特征j总共出现了sum[i][j]次
13 int c[size][30]; //c[i][j]=sum[i][j]-sum[i][0] , 即所有列都减去第一列后,值保存在c[][]
14 int N; //牛数量
15 int K; //特征数
16 int MaxLen; //最大距离
17
18 typedef class HASH
19 {
20 public:
21 int pi; //保存c[i][j]的行地址c[i]的下标i
22 class HASH* next;
23 HASH()
24 {
25 next=0;
26 }
27 }HashTable;
28
29 HashTable* hash[mod];
30
31 /*检查c[ai][]与c[bi][]是否对应列相等*/
32 bool cmp(int ai,int bi)
33 {
34 for(int j=0;j<K;j++)
35 if(c[ai][j]!=c[bi][j])
36 return false;
37 return true;
38 }
39
40 void Hash(int ci)
41 {
42 int key=0; //生成关键字
43 for(int j=1;j<K;j++)
44 key+=c[ci][j]*j;
45 key=abs(key)%mod; //由于c[][]有正有负,因此key值可能为负数
46
47 if(!hash[key]) //新key
48 {
49 HashTable* pn=new HashTable;
50
51 pn->pi=ci;
52 hash[key]=pn;
53 }
54 else //key值冲突
55 {
56 HashTable* pn=hash[key];
57
58 if(cmp(pn->pi,ci))
59 {
60 int dist=ci-(pn->pi);
61 if(MaxLen<dist)
62 MaxLen=dist;
63 return; //由于pi与ci对应列数字相等,且pi地址必定比ci小
64 } //而要求的是最大距离,因此不需要保存ci,判断距离后直接返回
65 else
66 {
67 while(pn->next)
68 {
69 if(cmp(pn->next->pi,ci))
70 {
71 int dist=ci-(pn->next->pi);
72 if(MaxLen<dist)
73 MaxLen=dist;
74 return;
75 }
76 pn=pn->next;
77 }
78
79 //地址冲突但c[][]各列的值不完全相同
80
81 HashTable* temp=new HashTable;
82 temp->pi=ci;
83 pn->next=temp;
84 }
85 }
86 return;
87 }
88
89 int main(void)
90 {
91 freopen("in.txt","r",stdin);
92 while(cin>>N>>K)
93 {
94 /*Initial*/
95
96 for(int p=0;p<K;p++)
97 {
98 c[0][p]=0; //第0只牛的特征默认为全0
99 sum[0][p]=0;
100 }
101
102 memset(hash,0,sizeof(hash));
103 Hash(0); //把第0只牛先放入哈希表
104 MaxLen=0;
105
106 /*Input*/
107
108 for(int i=1;i<=N;i++)
109 {
110 int Dexf; //十进制特征数
111 cin>>Dexf;
112
113 for(int j=0;j<K;j++)
114 {
115 feature[i][j]=Dexf%2; //Dexf转换为逆序二进制
116 Dexf/=2;
117
118 sum[i][j]=sum[i-1][j]+feature[i][j];
119 c[i][j]=sum[i][j]-sum[i][0];
120 }
121
122 Hash(i);
123 }
124
125 /*Output*/
126
127 cout<<MaxLen<<endl;
128 }
129 return 0;
130 }

Sample Input

7 3
7
6
7
2
1
4
2
 
7 3
7 7 7 7 7 7 7
 
4 4
1
2
4
8
 
4 4
8
1
2
4
 
5 4
3
1
2
4
8
 
1 5
3
 
1 2
3
 
1 3
7
 
6 5
16
8
4
2
31
 
 
 
 
 
Sample Output

4
7
4
4
4
0
1
1
2

我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: