Codeforces 1491 D. Zookeeper and The Infinite Zoo （二进制处理）

解题前提

1. 假设 u = 1010，则 v 可能为 1000、0010、1010。即对于 u 的每一位：
   a. u[i]为1，v[i]为1或0。
   b. u[i]为0，v[i]为0。
2. 假设 u = 1010, v = 1010，则 u+v=10100，其中 v 可以看作 1000+0010。
3. 将所有v分解为原子操作：若 u[i]=1，则 u[i] = u[i]+1 或者 u[i] 不变。
4. 所有的原子操作会导致两种情况
   a. 情况1，不连续进位，例如 0110+0100 = 1010。
   b. 情况2，连续进位，例如 0110+0010 = 1000。
5. 情况1将导致 u 中 ‘1‘ 和 v 中一样多，情况2导致 u 中 ‘1‘ 比 v 中多。
6. 可以得知 u 中 ‘1‘ 一定 大于等于 v 中 ‘1‘。

解题思路

1. 若 u > v ，肯定是 no 。因为u的数位不可能右移。
2. 与 1 同理，可知：所有的 v[i] 右边一定存在 u[j] = 1 。因为 u 只能左移不能右移。
3. 用两个栈存 u 和 v 数位 1 的索引位置。
4. 在 u 中 1 的数量比 v 中 1 的数量多的情况下，对 2 进行判定。

判定条件

1. u > v ===> "NO"。
2. u 中 ‘1‘ 比 v 中 ‘1‘ 少 ===> "NO"。
3. v 中对应‘1‘的位置 要保证 u 中有 ‘1‘ 在其对应位置的右边。 如果不能保证 ===> "NO"。
4. 否则 “YES”。

C++ Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int x, y;
    while (n--) {
        // s1,s2分别存x和y中1的位置。 
        stack<int> s1, s2;
        cin >> x >> y;
        if (x > y) {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 0; x != 0; ++i) {
            int t = x % 2;
            if (t == 1) s1.push(i);
            x /= 2;
        }
        for (int i = 0; y != 0; ++i) {
            int t = y % 2;
            if (t == 1) s2.push(i);
            y /= 2;
        }
        // 如果x中1比y中少，"NO"。 
        if (s1.size() < s2.size()) {
            cout << "NO" << endl;
            continue;
        }
        // 标志位，所有"NO"的条件都会导致flag变成false 
        bool flag = true;
    
        while (s1.size() && s2.size()) {
            // 如果 u 中 1 在 v中1左边，"NO"。因为u不能右移操作。 
            if (s1.top() > s2.top()) {
                flag = false;
                break;
            }
            s1.pop();
            s2.pop();
            if(s2.size() == 0) break;
            // 如果u中有多余的1，将其弹出。（多余=可连续进位） 
            while (s1.size() && s1.top() > s2.top()) {
                s1.pop();
            } 
            // 如果x中1比y中少，"NO"。
            if(s1.size() < s2.size()){
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
    return 0;
}

Codeforces 1491 D. Zookeeper and The Infinite Zoo （二进制处理）

原文：https://www.cnblogs.com/zhangjiuding/p/14465293.html