二进制与一 II 题解

szh_AK_all · 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";
        }
    }
}