转载请注明出处：優YoU 

 

大致题意：

解题思路：

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

 

 官方对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
     
         5 #include
      
          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
       
        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
        
         next)  68             {
     69                 if(cmp(pn->next->pi,ci))  70                 {
     71                     int dist=ci-(pn->next->pi);  72                     if(MaxLen
         
          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
          
           >Dexf; 112 113 for(int j=0;j
          
         
        
       
      
     

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