【0】做题心得 - 2025 NOIP #70 - T1 / 题解：P10026 「HCOI-R1」哀之变化【位运算】【构造】

· · 题解

你考虑一个不停 \times 2 的方法，来取得最高位。然后你就发现 \times 2 再 -1 就可以做到不停不变为 1，显然直接发现只要奇偶性相同就可以。然后你考虑如何最小化操作次数。这个的话你发现在前面放可以被后面的 \times 2 多次放大，于是找到需要调整的值类似二进制去做就可以了。还有一个问题就是最小的不一定奇偶性一致，你考虑把一个高次操作拆成两个低次操作，就可以省去一次操作变多 2 次操作，总操作次数 +1。然后就是简单做了，不知道为什么是绿色的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pl __builtin_popcountll
ll n,k;
int main(){
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>k>>n;
        bool fl=0;
        for(int i=60;~i;i--){
            if((1ll<<i)>=n){
                ll op=i+(1ll<<i)-n, pc=pl((1ll<<i)-n);
                if(k>=op&&op%2==k%2) fl=1;
                op=i+pc;
                if((1ll<<i)-n>=2){ if(k>=op+1&&(op+1)%2==k%2) fl=1; }
                if(k>=op&&op%2==k%2) fl=1;
            }
        }
        cout<<(fl?"Yes\n":"No\n");
    }
    return 0;
}