[cf] 805 div3 F. Equate Multisets

前言

t a g : tag : tag: 二进制 思维 贪心 传送门 :

题意 : 给定两个数组 A [ 1.... N ] A[1....N] A[1....N], B [ 1... N ] B[1...N] B[1...N] 询问是否可以通过有限次操作使得 B = A B=A B=A

操作定义如下 : 选中一个 i i i使得

• B [ i ] ∗ 2 B[i]*2 B[i]∗2
• B [ i ] / 2 B[i]/2 B[i]/2下取整

思路 :

看到 / 2 /2 /2这种操作,我们需要联想到二进制

我们发现 B [ i ] ∗ 2 B[i]*2 B[i]∗2相当于在二进制后面加了个0

而对于第二个操作,就是相当于删除了二进制最后一位

而对于 B [ i ] ∗ 2 B[i]*2 B[i]∗2我们可以看成 A [ i ] / 2 A[i]/2 A[i]/2 (这个只能删除 A [ i ] A[i] A[i]最后一位是0的情况)

如果是可以完成的,那么显然,我们将 A , B A,B A,B尽可能的最小化的情况下,是可以完全抵消的

否则就是不行的

因此这个操作可以使用 M a p ∣ ∣ S e t Map||Set Map∣∣Set完成

code :

#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr