题解：AT_arc213_b [ARC213B] Hamming Distance is not 1

· · 题解

最近啥题都调不出来了，代码能力低下。

约定 n=r-l+1。

通过手玩或者打表能够发现：

先证明答案下界是 \lceil\frac n2\rceil。按 \operatorname{popcount} 的奇偶性把数分成两组，奇偶性相同的一定没有影响。选大的那组，根据抽屉原理，答案下界是 \lceil\frac n2\rceil。

再证明答案上界是 \lfloor\frac n2\rfloor+1。把数按 \lfloor\frac n2\rfloor 两两配对（可能 l 和 r 无法配对），一对中最多选择一个数。根据抽屉原理，答案上界是 \lfloor\frac n2\rfloor+1。

如果 2\nmid n，直接取 \operatorname{popcount} 奇偶多的那边即可。下面讨论 2\mid n 的情况。

如果 l 是偶数，根据上文，所有数都两两配对，答案是 \frac n2，任取 \operatorname{popcount} 奇偶的一边即可。下面讨论 l 是奇数的情况。

令 2^x 为不超过 n 最大的 2 的次幂。则 l\sim r 所有 2^x 之前的位都一样，如果把它们去掉对答案没有影响。去掉之后有可能出现 l>r 的情况，令 r\gets r+2^{x+1} 即可。

考虑 $r<2^{x+1}$ 的情况。对于 $i<2^x$，选 $i$ 当且仅当 $i$ 的 $\operatorname{popcount}$ 奇偶性与 $l$ 相同；对于 $i\ge2^x$，选 $i$ 当且仅当 $i$ 的 $\operatorname{popcount}$ 奇偶性与 $r$ 相同。 - 如果 $n>2^x$，则 $l+2^x\le r$。答案要是 $\lfloor\frac n2\rfloor+1$ 时，但是 $l+2^x$ 不能选。所以 $l+2^x$ 与 $r$ 的 $\operatorname{popcount}$ 奇偶性不同，所以 $l$ 与 $r$ 的 $\operatorname{popcount}$ 奇偶性相同。 - 如果 $n=2^x$，$l$ 与 $r$ 的 $\operatorname{popcount}$ 奇偶性显然相同。 综上，当 $r<2^{x+1}$ 时，答案等于 $\lfloor\frac n2\rfloor+1$ 当且仅当 $l$ 与 $r$ 的 $\operatorname{popcount}$ 奇偶性相同。 考虑 $r\ge 2^{x+1}$ 的情况，此时 $i<2^{x+1}$ 的（从低到高，下同）第 $x+2$ 位是 $0$，第 $x+1$ 位是 $1$；$i<2^{x+1}$ 的第 $x+2$ 位是 $1$，第 $x+1$ 位是 $0$。这样一来 $\operatorname{popcount}$ 至少相差 $2$，不会有影响。所以这种情况一定有解。 由于这些构造及证明是赛后补的，赛时写的不是这个做法，所以 [代码](https://atcoder.jp/contests/arc213/submissions/72766397) 凑合着看吧。