Codeforces 1702F. Codeforces Round #805 (Div. 3) F(思维)
原题链接
中等
作者:
小小_88
,
2023-01-26 00:41:30
,
所有人可见
,
阅读 207
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;
}