题解：P11968 「ALFR Round 7」T1 二进制与一 II

· · 题解

题意很清楚了不需要大意了。

由于官方题解对于我和我机房的各位伪人来说太过抽象，所以自己写了一篇。

简要思路

显然可以寻找有 k 位为一的最小的大于 x 的和最大的小于 x 的。

我们可以从第 60 位开始枚举，枚举到第 i 位的意思是将所有的一排成一个有 i 位最小的数，打个比方就是 i=7,k=3 排成 1000011，将这个操作叫做 get，最大的数同理，就是 1110000，叫 get1。

这样有什么意义呢，就是可以找到大于 x 的最小的值和小于 x 的最大值，为什么呢？

为 0 时可以 get 来找到找最小的大于 x 的。当我们枚举到 x 二进制位是 1 的情况时，相当于找位数小于 i 最高位为 0 的位置,按 0 的方法处理。

想到这里还要处理比 x 小最大的，这个只需要在 x 二进制位为 0 的位置后一位 get1 就能找到了。

首先比 x 小的最大的可以手玩几组样例证明，比 x 大的呢，由于我们枚举了每一位 x 为 0 的位置，就相当于在枚举所有可能是大于的最小的数，所以是没有问题的。

文字可能过于抽象，详见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=64;
int T,x,k;
int get(int w,int v){
    if(v>w)return 4e18;
    if(v==0||w==0)return 0;
    int res=1ll<<w-1;v--;
    for(int i=1,j=1;i<=v;i++)
        res+=j,j*=2;
    return res;
}//get操作和上面说的一样
int get1(int w,int v){
    if(v>w)return 4e18;
    if(v==0||w==0)return 0;
    int res=0;
    for(int i=1,j=1ll<<w-1;i<=v;i++)
        res+=j,j/=2;
    return res;
}
signed main(){
    cin>>T;
    while(T--){
        cin>>x>>k;
        int now=0,ans=4e18;int k1=k;//now表示当前给高位x补充的大小
        for(int i=60;i>=1;i--){
            if(!k||i<k)break;
            if(((1ll<<i-1)&x)){
                k--,now+=1ll<<i-1;
                int j=i;
                while(((1ll<<j-1)&x)&&j>=k)j--;
                ans=min(ans,abs(x-(now+get(j,k))));
    //将当前位的1加入now，要找到最小的大于x的，相当于找位数小于i最高位为0的位置找
            }
            else ans=min(ans,abs(x-(now+get(i,k))));
        }
        now=0;
        k=k1;
        for(int i=60;i>=1;i--){
            if(!k||i<k)break;
            if(((1ll<<i-1)&x))
                ans=min(ans,abs(x-(now+get1(i-1,k)))),now+=1ll<<i-1,k--;
            //这里找小于x最大值，相当于在x为0的位置的后面尽量多的1在高位
        }
        cout<<ans<<'\n';
    }
    return 0;
}