自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 21:15:54，当前版本为作者最后更新于2023-12-26 12:53:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解。

分析

我们有一个数 $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]);
}