分享到:文章主题: 求教大牛一个工程实际问题
weiming383楼主
xixi
等级
用户
文章
507
积分
3859
星座
天秤座
发信人: weiming383 (xixi), 信区: ACM_ICPC
标  题: 求教大牛一个工程实际问题
发信站: 北邮人论坛 (Thu Apr 18 00:03:46 2019), 站内

工作遇到一个问题,百思不得其解,还请大牛们点拨。跪谢先!
几个长度一样的比特数组,比如1001,1100,1010。1表示位置占用,0表示没有占用。
问题是比特数组允许循环移位,比如1001移位后和1100一样,可以做到占用位置相同,共计占用两个位置。第三个数组1010无论怎么移位,只有一个位置和前两个数组相同,所以得新增第三个占用位置。因此三个数组得占用三个位置。

如果多个比特数组,如何才能找到最小数目的占用位置,并且找到对应的各个数组的循环移位?
--

※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 221.217.231.*]
    返回顶部
    Wizmann沙发
    Wizmann
    等级
    用户
    文章
    2294
    积分
    16500
    星座
    巨蟹座
    发信人: Wizmann (Wizmann), 信区: ACM_ICPC
    标  题: Re: 求教大牛一个工程实际问题
    发信站: 北邮人论坛 (Thu Apr 18 00:22:18 2019), 站内

    首先,你的比特数组有多长。

    如果短的话,就穷举。对于每一个比特数组,取最小(或最大)的那个。例如[110, 011],我们都可以用011来表示。

    如果长的话,算一个最小表示法,O(n)的。

    这样我们就把去重的问题解决了。
    --

    ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 167.220.232.*]
      返回顶部
      Wizmann板凳
      Wizmann
      等级
      用户
      文章
      2294
      积分
      16500
      星座
      巨蟹座
      发信人: Wizmann (Wizmann), 信区: ACM_ICPC
      标  题: Re: 求教大牛一个工程实际问题
      发信站: 北邮人论坛 (Thu Apr 18 00:28:29 2019), 站内

      找最小数目用DP吧。如果数据大的话复杂度就比较高了。

      暂时没想到啥更好的方法。
      --

      ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 167.220.232.*]
        返回顶部
        weiming383第3楼
        xixi
        等级
        用户
        文章
        507
        积分
        3859
        星座
        天秤座
        发信人: weiming383 (xixi), 信区: ACM_ICPC
        标  题: Re: 求教大牛一个工程实际问题
        发信站: 北邮人论坛 (Thu Apr 18 04:22:04 2019), 站内

        数组比较长
        看了下最小表示法,似乎不行

        比如0001101,0000011,已经是最小表示了,但实际占用数目应该是3

        也许想得不对,求指正
        【 在 Wizmann 的大作中提到: 】
        : 首先,你的比特数组有多长。
        : 如果短的话,就穷举。对于每一个比特数组,取最小(或最大)的那个。例如[110, 011],我们都可以用011来表示。
        : 如果长的话,算一个最小表示法,O(n)的。
        : ...................

        --

        ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 221.217.231.*]
          返回顶部
          Rclover第4楼
          clover
          等级
          用户
          文章
          44
          积分
          1064
          星座
          射手座
          发信人: Rclover (clover), 信区: ACM_ICPC
          标  题: Re: 求教大牛一个工程实际问题
          发信站: 北邮人论坛 (Thu Apr 18 09:55:14 2019), 站内

          没看懂问题描述。。ema1
          --

          ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.108.113.*]
            返回顶部
            weiming383第5楼
            xixi
            等级
            用户
            文章
            507
            积分
            3859
            星座
            天秤座
            发信人: weiming383 (xixi), 信区: ACM_ICPC
            标  题: Re: 求教大牛一个工程实际问题
            发信站: 北邮人论坛 (Thu Apr 18 10:23:47 2019), 站内

            em17,就是01比特数组,允许循环移位,求相同位置是0的最大个数

            000100 和100000经过循环移位后相同位置0的最大个数是5    如果多个数组,如何快速确定相同位置是0的最大个数
            --

            ※ 来源:·北邮人论坛手机版 http://m.byr.cn·[FROM: 111.205.247.*]
              返回顶部
              a940100079第6楼
              一笑一蹙
              等级
              用户
              文章
              1032
              积分
              10937
              星座
              天蝎座
              发信人: a940100079 (一笑一蹙), 信区: ACM_ICPC
              标  题: Re: 求教大牛一个工程实际问题
              发信站: 北邮人论坛 (Thu Apr 18 11:34:10 2019), 站内

              感觉这个问题应该是贪心的解法
              [1001,1100,1010,......]
              原始为0000
              1001进来后,需要修改为1001
              1100进来后,判断和1001最多循环移位,最多重叠为2,即1100可以通过移动产生1001,当前依旧为1001
              1010,发现不论何种方法,都需要增加1位。即修改为1011

              所以问题就是解决2个bit数循环移位最大重叠数,解决两两的问题就可以了
              bit长度如果为64的话
              (任意2个bit数最大重叠数的求解经过64循环移位一定可以求解出最优解)
              那么解决整个问题的时间复杂度为64*n

              --

              ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 167.220.233.*]
                返回顶部
                Wizmann第7楼
                Wizmann
                等级
                用户
                文章
                2294
                积分
                16500
                星座
                巨蟹座
                发信人: Wizmann (Wizmann), 信区: ACM_ICPC
                标  题: Re: 求教大牛一个工程实际问题
                发信站: 北邮人论坛 (Thu Apr 18 11:36:43 2019), 站内

                分两步,第一步是去重,用最小表示法。

                第二步用DP搞。

                话说比较长是多长啊?100?200?

                不要让大家猜嘛。。。


                【 在 weiming383 的大作中提到: 】
                : 数组比较长
                : 看了下最小表示法,似乎不行
                : 比如0001101,0000011,已经是最小表示了,但实际占用数目应该是3
                : ...................

                --

                ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 167.220.232.*]
                  返回顶部
                  weiming383第8楼
                  xixi
                  等级
                  用户
                  文章
                  507
                  积分
                  3859
                  星座
                  天秤座
                  发信人: weiming383 (xixi), 信区: ACM_ICPC
                  标  题: Re: 求教大牛一个工程实际问题
                  发信站: 北邮人论坛 (Thu Apr 18 12:15:08 2019), 站内

                  多谢解答,第三个数进来以后可能变成1011也可以变成1101,你这个例子可能有点特殊,数组长度如果更长的话,新增1的位置好像对后面新的数组有影响
                  --

                  ※ 来源:·北邮人论坛手机版 http://m.byr.cn·[FROM: 223.104.3.*]
                    返回顶部
                    stdiohero第9楼
                    bobobobobo
                    等级
                    用户
                    文章
                    46
                    积分
                    1423
                    星座
                    射手座
                    发信人: stdiohero (bobobobobo), 信区: ACM_ICPC
                    标  题: Re: 求教大牛一个工程实际问题
                    发信站: 北邮人论坛 (Fri Apr 19 00:06:37 2019), 站内

                    bd,学习大佬回答
                    --

                    ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.28.161.*]
                      返回顶部
                      • 文章数:12 分页:
                        1. 1
                        2. 2
                        3. >>