V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
huglight
V2EX  ›  算法

有人做了昨晚的 Codeforces div2 吗?

  •  
  •   huglight · 2019-08-19 15:38:14 +08:00 · 3123 次点击
    这是一个创建于 1683 天前的主题,其中的信息可能已经有所发展或是发生改变。

    想问下为什么 D 题只要不为 0 的数大于 128 个,输出的最小环节点数就为 3 呢?

    2 条回复    2019-08-20 10:30:06 +08:00
    DaCong
        1
    DaCong  
       2019-08-20 10:16:43 +08:00   ❤️ 1
    其实并不需要大于 128,大于 120 即可。
    首先,认识到一点:如果任何一个 bit 上的 1 多于 3 个,那么答案为 3,因为这已经是最短的环了。
    而题目的数据范围是 10^18,59<log(10^18)<60,因此一个数最多要 60 个 bit 来储存。
    根据抽屉原理,如果非零的不同数字多于 2*60=120 个,则至少有一个 bit 上是有大于等于 3 个的 1。
    至于为什么很多人用了 64*2,是因为他们懒得精确去算 log(10^18),而是用了 64 位整数的上界。
    huglight
        2
    huglight  
    OP
       2019-08-20 10:30:06 +08:00
    @DaCong 非常感谢~~还是自己太菜了,不了解组合数学
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5317 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 09:34 · PVG 17:34 · LAX 02:34 · JFK 05:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.