想问下为什么 D 题只要不为 0 的数大于 128 个，输出的最小环节点数就为 3 呢？
This topic created in 2457 days ago, the information mentioned may be changed or developed.
2 replies • 2019-08-20 10:30:06 +08:00
 |
1
DaCong Aug 20, 2019  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 位整数的上界。 |
Select Language