想问下为什么 D 题只要不为 0 的数大于 128 个,输出的最小环节点数就为 3 呢?
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 位整数的上界。 |