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

有人做了昨晚的 Codeforces div2 吗?

  •  
  •   huglight · 91 天前 · 874 次点击
    这是一个创建于 91 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    2 回复  |  直到 2019-08-20 10:30:06 +08:00
        1
    DaCong   91 天前   ♥ 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 位整数的上界。
        2
    huglight   91 天前
    @DaCong 非常感谢~~还是自己太菜了,不了解组合数学
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4412 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 02:36 · PVG 10:36 · LAX 18:36 · JFK 21:36
    ♥ Do have faith in what you're doing.