一篇题解

· · 题解

出题人题解。

分析

我们有一个数 n，如要使 n 在二进制下从右往左数的第 k 位为 1，则需判断这一位是否为 1，如果是，则无需进行任何操作，否则，n 会改变，操作数也会改变。

举个例子：考虑 5 在二进制下的第 2 位是否为 1。5 在二进制下表示为 101，第二位为 0。可以发现，一个数在二进制下的第 k 位是否为 1 与最高位到第 k+1 位无关，所以，我们要取出这个数的第 1 位到第 k 位。

如何取出这个数的第 1 位到第 k 位呢？只需要这个数对 2^{k} 取模即可。因为，这个数在二进制下的第 1 位到第 k 位一定小于 2^{k}，而最高位到第 k+1 位一定是 2^{k} 的倍数。同上面的例子一样，5 对 2^{2} 取模，得到 1，也就是二进制下的 01;

假设令 n 在二进制下的第 k 为 1 需要 n 至少加上 t，那么 t 就是操作数。由于操作数要尽可能小，那么我们需要让 n 在二进制下的第 1 到第 k 为的值为 2^{k-1}。举个例子，若要使一个数在二进制下的第 4 位为 1，只需让这个数在二进制下的第 1 到第 k 位在二进制下表示为 1000。如果表示为 1001 则不是最优操作。所以，在最优情况下，操作数为 2^{k-1} - (n \bmod (2^k))

如果 n 在二进制下的第 k 位本身就是 1，那么取出的第 1 到第 k 位肯定大于或等于 2^{k-1}，所以在计算操作数时将 2^{k-1} - (n \bmod (2^k)) 与 0 取个最大值即可。 局部代码如下：

lg[0] = 1;
for (int i = 1; i <= 32; i++)
        lg[i] = lg[i - 1] * 2;
...
int k;
cin >> k;
if (lg[k - 1] > (n % lg[k])) {
    ans += lg[k - 1] - (n % lg[k]);
    n += lg[k - 1] - (n % lg[k]);
}