• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3274 – Gold Balanced Lineup

    ACM-POJ EXP 188阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意:

    农夫约翰的N(1≤N≤100000)头奶牛有很多相同之处。其实,约翰己经将每头奶牛的不同之处归纳成为K(1≤K≤30)种特性,比如说,1号特性可以代表她身上有斑点,2号特性代表她更喜欢用Pascal而不是C来写程序等等。

    约翰使用“特性标识符”来描述奶牛的各种特性:一个特性标识符就是一个二进制长度 为K的整数,每位比特可以标识一头奶牛的一个特性。比如一头奶牛的特性标识符是13,将13写成二进制:1101, 从右向左看,就表示这头奶牛具冇1、3、4号特性,但没有2号特性。

    约翰把N头奶牛排成了一排,发现在有些连续区间里的奶牛,每种特性出现的次数是一样的,约翰把这样的区间称为“平衡的”。作为一个喜欢研究的人,约翰希望你能帮忙找出平衡区间的最大长度。


    解题思路

    经典题,不转化问题很难做,先根据官方的方法转化问题,

    把“求最远的两行间各个特征出现次数相等”转化为“求最远的相同两行”,再用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.

    The problem is now to do this efficiently. Notice that s[ i ][l]-s[j][l] being
    constant for all is equivalent to s[ i ][l]-s[j][l]=s[ i ][1]-s[j][1] for all, which can be rearranged to become s[ i ][l]-s[ i ][1]=s[j][l]-s[j][1] for all. 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[ ][ ],得到:
      (行数为cow编号,自上而下从1开始;列数为特征编号,自左到右从0开始)
      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

    再求sum数组,逐行累加得,sum数组为
      (数组sum[i][j]表示从第1到第i头cow属性j的出现次数)
      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 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

    官方对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


    转载请注明:EXP 技术分享博客 » POJ3274 – Gold Balanced Lineup

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址