CF1702F 题解

· · 题解

题目链接（CF，洛谷） | 强烈推荐博客中观看。

前言：本题解的解法参考了这个视频。

题意

多重集是一种特殊的集合，其元素可以重复，并且，和集合一样，元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。

如，\{2, 2, 4\} 和 \{2, 4, 2\} 是相同的。而 \{1, 2, 2\} 和 \{1, 1, 2\} 不是相同的。

现在给你两个多重集 a 和 b，每个包含 n (1 \le 2\cdot 10^5) 个整数。

在一次操作中，b 中的一个元素可以被翻倍或是减半（向下取整）。或者说，对于一个 b 中的元素 x，你可以做下面两种操作。

注意你不能对多重集 a 做任何操作。

请问你是否能使多重集 b 在经过任意数量的操作后和 a 相等（也可以是 0 个操作）。

一些性质

这个 \times 2 和 \lfloor \div 2 \rfloor 可以联系到位运算的左移和右移。如 5 的二进制形式为 (101)_2，5\times 2 的二进制形式就为 (1010)_2。可以看到相比 5，10 的二进制形式在最后加了一个 0。而 10 \div 2 就是 5，二进制形式下的 5 在最后一位比 10 少了一个 0。

所以左移和乘二的运算是等价的，右移和向下取整的除二是等价的。

那么我们就可以发现一个性质，也就是集合（实为多重集，这里为了方便称为集合） a 和 b 中元素的后缀 0 是不重要的。

这里我来解释一下什么是后缀 0，以及“不重要”。

现在有一个数，比如 40，其二进制形式为 (101000)_2。可以看到二进制下的 40 在尾部有 3 个 0。那么这三个 0 就是 40 的后缀 0。

而不重要的意思是：

如果我们设 \alpha \in a, \beta \in b。再设 \alpha^\prime 和 \beta^\prime 分别为 \alpha 和 \beta 去掉后缀 0 的后的数字。那么如果我们能通过提供的两个操作，把 \beta 转换成 \alpha 就一定能把 \beta^\prime 转换为 \alpha^\prime。

这是因为可以通过左移和右移操作，在 \beta^\prime 的尾部增加和删去任意数量的 0。

这样就可以让 \beta^\prime 变成 \beta。而对于 \beta， 我们已经知道了可以将其转换成 \alpha 。现在我们再在当前数字上减去一些 0，就可以变成 \alpha^\prime。

所以为了计算的方便，可以直接在输入的时候去掉元素的后缀 0。

接下来，还有一个性质：

当且仅当 \alpha^\prime 在二进制形式下是 \beta^\prime 的前缀，我们可以将 \beta^\prime 转换为 \alpha^\prime。

这里先解释一下，什么是二进制形式下的前缀。有两个数字，9 和 75。其二进制形式分别是 (1001)_2 和 (1001011)。

那么从字符串的角度来看，\texttt{1001} 就是 \texttt{1001011} 的前缀。而能将 \beta^\prime 转换为 \alpha^\prime 是因为右移操作，我们可以把 \beta^\prime 的尾部去掉使其变成自己的任意二进制下的前缀。

并且，显而易见的，如果 \alpha^\prime > \beta^\prime， \alpha^\prime 一定不是 \beta^\prime 二进制形式下的前缀。那就自然不能将 \beta^\prime 转换为 \alpha^\prime。

具体实现

有了这些性质，我们就可以搞出一些奇怪的方法了。

首先我们把集合 a 的元素存到一个数组里，把集合 b 的元素存到一个优先队列里。在存之前，需要先去掉后缀 0。

vector<int> a(n);
priority_queue<int> b;
for (int i = 0; i < n; i++) { 
    cin >> a[i];
    while ((a[i] & 1) == 0) { // 如果最后一位是 0，那就一直右移来消除后缀 0
        a[i] >>= 1;
    }
}
for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;
    while ((temp & 1) == 0) {
        temp >>= 1;
    }
    b.push(temp);
}

然后再对 a 升序排序，之后就可以搞出一些骚操作了：

sort(a.begin(), a.end());
while (b.size()) {
    int lb = b.top();
    b.pop();
    int la = a.back();
    if (la > lb) {
        goto FAIL;
    } else if (la < lb) {
        lb /= 2;
        b.push(lb);
    } else {  // la == lb
        a.pop_back();
    }
}

可以看到，在这个 while 中，我们每次取出的 la 和 lb 都分别是 a 和 b 中最大的元素。

那么有三种情况。

对于第三种情况，如果说直接把 lb 右移了然后放入优先队列中，那是否会造成： lb 本来是可以跟 a 中别的元素匹配，但现在不行了的情况呢？

答案是不会的，因为 a 中最大的元素已经小于 lb 了，那其他元素一定也小于它，所以不会有别的元素等于 lb 了。

完整代码

#include <bits/stdc++.h>
using namespace std;
// author: tzyt
// ref: https://www.youtube.com/watch?v=HIiX3r5n27M
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        priority_queue<int> b;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            while ((a[i] & 1) == 0) { // 如果最后一位是 0，那就一直右移来消除后缀 0
                a[i] >>= 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            while ((temp & 1) == 0) {
                temp >>= 1;
            }
            b.push(temp);
        }
        sort(a.begin(), a.end());
        while (b.size()) {
            int lb = b.top();
            b.pop();
            int la = a.back();
            if (la > lb) {
                goto FAIL;
            } else if (la < lb) {
                lb /= 2;
                b.push(lb);
            } else {  // la == lb
                a.pop_back();
            }
        }
    SUCC:
        cout << "YES\n";
        continue;
    FAIL:
        cout << "NO\n";
    }
}

最后，希望这篇题解对你有帮助，如果有问题可以通过评论区或者私信联系我。