题解：CF1491D Zookeeper and The Infinite Zoo

AstaVenti_ · 2025-12-04 17:28:35 · 题解

容易发现，如果 u>v 则一定无法到达，而 u=v 则一定可以到达。

以下分析 u<v 的情况。

我们试着手动构造出一些满足 u\&v=v 的 u 和 v：

到这里应该能发现一些规律。因为 u\&v=v，所以 v 中为 1 的位置在 u 中也一定为 1。对于 u+v，与 u 相比，1 只可能减少或向左移动（进位），而不会增加或向右移动。因此对于 u 和 u+v 的每个后缀，后者 1 的数量一定不会多于前者。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,u,v;
void solve(){
    cin>>u>>v;
    if(u>v){
        cout<<"NO\n";
    }else if(u==v){
        cout<<"YES\n";
    }else{
        vector<ll>a,b;
        while(u)a.push_back(u&1),u>>=1;
        while(v)b.push_back(v&1),v>>=1;
        a.resize(b.size());
        ll s=0,t=0; 
        for(ll i=0;i<a.size();i++){
            s+=a[i],t+=b[i];
            if(t>s){
                cout<<"NO\n";
                return;
            }
        }
        cout<<"YES\n";
    }
}
int main(){
    cin>>T;
    while(T--){
        solve();
    }
}