Equate Multisets

C++ 代码

/*
对于每个 a[i]，我们令它一直除 2 直到无法整除 2 为止。此时不会影响结果，因此 b 如果能
变成原序列 a，则一定能变成新序列 a。

然后由于 a 被我们处理之后，每个数都一定是奇数，因此对于 b 来说 * 2 的操作就不再需要了，
因为任何数 *2 都会变成一个偶数，不可能得到 a 中任何一个数。

接下来只考虑 / 2 操作，我们依次枚举 b 中最大的数，如果它没有出现在 a 中，我们就将它 / 2，
直到它在 a 中出现为止，此时我们将它从 a 和 b 中删去，然后继续考虑下一个数。如果一直将它
除到 1 都不在 a 中出现，说明这个数永远无法和 a 中任何一个数配对，说明无解。如果能全部配对，
则有解。
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

void work()
{
    int n;
    scanf("%d", &n);
    vector<int> b(n);
    map<int, int> cnt;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        while(x % 2 == 0) x /= 2;
        cnt[x]++;
    }

    for(int i = 0; i < n; i++) scanf("%d", &b[i]);

    sort(b.begin(), b.end(), greater<int>());

    for(int i = 0; i < n; i++)
    {
        while(!cnt[b[i]] && b[i] > 1) b[i] /= 2;
        if(!cnt[b[i]])
        {
            puts("NO");
            return;
        }
        cnt[b[i]]--;
    }
    puts("YES");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}