D. Zookeeper and The Infinite Zoo 题解(思维)

题目连接

题目大意

如果(u&v=v)则代表(u ightarrow (u+v))有一条单向边

有(q(qleq 1e5))次查询

询问(u,v(1leq u,vleq 2^{30}))

u是否能够到底v

题目思路

首先要明白假如u可以直接到v

那么自己可以模拟一下变化

你会发现把u和v变成二进制

u的二进制前缀和必定比v大

因为必定是加法让低位上的 1 变到高位上的 1，并且二进制中 1 的数量只能变少不能变多

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef  long long ll;
const int maxn=5e3+5,mod=1e7;
int main(){
    int _; scanf("%d",&_);
    while(_--){
        int x,y,dif=0,flag=1;
        scanf("%d%d",&x,&y);
        for(int i=0;i<=30;i++){
            if(x&(1<<i)){
                dif+=1;
            }
            if(y&(1<<i)){
                dif-=1;
            }
            if(dif<0){
                flag=0;
                break;
            }
        }
        if(x>y) flag=0;
        printf(flag?"YES
":"NO
");
    }
    return 0;
}