Codeforces Global Round 13 D. Zookeeper and The Infinite Zoo 思维

传送门：https://codeforces.com/contest/1491/problem/D

题意

给u和v，问u能不能到达v。 u能到达u+v的条件是$u\&v=v$。

思路

因为u到u+v的条件是$u\&v=v$。$\& $和二进制有关，所以比较u和v的二进制。

如果u>v，那u绝对到不了v。 如果u==v，emmm，不用动就能到达。

先给结论：计算u和v的二进制中1的个数，做一个前缀和，对于每一位必须a[i]>=b[i]能保证u到v。

$eg：对于3，(3)_2=11，所以1，10，11，3可以到达3+1，3+2,3+3.$ $eg：对于6，(6)_2=110，所以10，100，110，6可以到达6+2，6+4，6+6，而6到达不了111.$ $就是因为6的第一位是0，7的第一位是1，已经不能满足结论了。$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

void solve() {
    int _; cin >> _;
    while(_--) {
        ll u, v; cin >> u >> v;
        vector<int> a(100, 0), b(100, 0);
        for(int i = 0;i <= 30; i++) {
            a[i] = u >> i & 1;
            b[i] = v >> i & 1;
        }
        for(int i = 1;i <= 30; i++) {
            a[i] += a[i - 1];
            b[i] += b[i - 1];
        }
        if(u > v) cout << "NO" << endl;
        else if(u == v) cout << "YES" << endl;
        else {
            bool flag = 1;
            for (int i = 0; i <= 30; i++) {
                if (a[i] < b[i]) {
                    flag = 0;
                    break;
                }
            }
            if (flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/01/codeforces-global-round-13-d/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！