自动搬运

查看原文

来自洛谷，原作者为

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

搬运于2025-08-24 23:11:46，当前版本为作者最后更新于2025-01-24 17:48:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

出题人题解。

问题可以转换为求比 $x$ 小的在二进制下有 $k$ 位为 $1$ 的最大的 $a$，及比 $x$ 大的在二进制下有 $k$ 位为 $1$ 的最小的 $b$，答案则为 $\min(x-a,b-x)$。

既然有大小关系的比较，那不妨枚举从最高位开始，$a,b$ 分别在哪一位与 $x$ 不同。假设当前考虑到第 $i$ 位（从右往左数），那么对于 $a$ 来说，$x$ 在二进制下，该位必须为 $1$，此时 $a$ 此位便为 $0$，且由于我们应当构造出最大的合法的 $a$，所以 $a$ 从第 $i-1$ 位开始应当是一段连续的 $1$。$b$ 同理，应贪心的将 $1$ 尽量放在靠右的位上。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[65], t;

int sum(int x) {
	int ans = 0;
	while (x) {
		ans += x % 2;
		x /= 2;
	}
	return ans;
}

signed main() {
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		int x = n;
		if (sum(n) == k) {
			cout << 0 << "\n";
			continue;
		}
		t = 0;
		while (x) {
			a[++t] = x % 2;
			x /= 2;
		}
		if (t <= k)
			cout << (1LL << k) - 1 - n << "\n";
		else {
			int now = 0, one = 0, ans = (1LL << t) + (1LL << (k - 1)) - 1 - n;
			for (int i = t; i >= 1; i--) {
				bool e = (n & (1LL << i - 1));
				if (e) {
					int tmp = now * 2;
					if (i - 1 < k - one || one > k)
						continue;
					tmp *= (1LL << i - 1);
					tmp += (1LL << (i - 1)) - 1 - ((1LL << (i - 1 - (k - one))) - 1);
					one++;
					ans = min(ans, n - tmp);
				}
				now = now * 2 + e;
			}
			now = 0, one = 0;
			for (int i = t; i >= 1; i--) {
				bool e = (n & (1LL << i - 1));
				if (e)
					one++;
				else {
					int tmp = now * 2 + 1;
					if (i - 1 < k - one - 1 || one >= k)
						continue;
					tmp *= (1LL << i - 1);
					if (k - one - 1)
						tmp += (1LL << (k - one - 1)) - 1;
					ans = min(ans, tmp - n);
				}
				now = now * 2 + e;
			}
			cout << ans << "\n";
		}
	}
}