D.ZookeeperandTheInfiniteZoo（CodeforcesGlobalRound13）题解xiaodangao

题目链接：D. Zookeeper and The Infinite Zoo
思路：
我们在图中展现11011->10110100有边，图中显示的是让11011的第一个1与10110100中第一个1对齐的操作，如此可见，设a到b有边，那么a的二进制表示的第一个1必须小于等于b的二进制表示的第一个1的位置，换句话说，在左边的1能够进行若干次操作移动到右边，并且不影响a在该位之后的位置，所以这个结论再进行总结就是若a到b有边，当且仅当a对于每一位1的前缀和总是大于等于b的；
$Coding:$


#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 10000+10;
int mex[4] = {0,2,3,1};
int n;
int top[110][110];
pair<int,int>idx,idy;
int gos(int a,int b){
    rep(i,1,3){
        if(i!=a&&i!=b)return i;
    }
    return 1;
}
int sum1[44],sum2[44];
bool check(int a,int b){
    memset(sum1,0,sizeof sum1);
    memset(sum2,0,sizeof sum2);
    if(a == b)return true;
    else if(b<a)return false;
    int p = b - a;
    rep(i,0,29){
        if((a>>i)&1)sum1[i]++;
        if((b>>i)&1)sum2[i]++;
        if(i!=0){
            sum1[i]+=sum1[i-1];
            sum2[i]+=sum2[i-1];
        }
        if(sum2[i]>sum1[i])return false;
    }
    return true;
}
void solve(){
    read(n);
    int cnt = 0;
    while(n--){
        cnt++;
        int u,v;
        read(u);read(v);
        if(check(u,v))puts("YEs");
        else
        puts("NO");
        //stk:;
    }
}
signed main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。