题解 CF2165C Binary Wine
JuRuoOIer
·
·
题解
题解 CF2165C Binary Wine
其他题
题意
给定长度为 n 的数组 a，你可以进行若干次操作，每次花费 1 代价使 a 中的某个元素增加 1。
- 存在一个长度为 $n$ 的数组 $b$ 使得 $\forall 1\le i\le n,0\le b_i\le a_i$，且 $b_1\oplus b_2\oplus\dots\oplus b_n=c$。
数据范围：多测，$\sum n\le 5\times 10^5$，$\sum q\le 5\times 10^4$，值域 $[0,2^{30})$。
### 做法
按位考虑。首先一位上出现多个 $1$ 显然是不优的。
考虑从高往低枚举每一位。设 $a$ 的各项的这一位求和为 $A$，$b$ 的这一位为 $B$，则分三种情况：
- $A>B$ 时，必然能拿出一个 $a_i$ 给 $b$ 的该位，同时还可以拿出另一个 $a_i$ 则可以覆盖 $b$ 的所有更低位，直接停止枚举输出答案；
- $A=B$ 时，必然能拿出一个 $a_i$ 给 $b$ 的该位，把该 $a_i$ 的该位减掉放回，然后接着枚举后面的位；
- $A<B$ 时，拿不出一个 $a_i$ 了，这时就需要加。而加是要代价的所以我们直接取出 $a$ 里面最大的拿来加。加完了之后该 $a_i$ 就进入第二种情况，即留下一个 $0$。
综上，算法思路就是用一个大根堆维护前 $\log V$ 大的 $a_i$，然后按上面三种情况讨论，其中后两种都每次取堆顶。