题解 CF2165C Binary Wine

给定长度为

n

的数组

a

，你可以进行若干次操作，每次花费

1

代价使

a

中的某个元素增加

1

。

q

次询问，每次给定一个

c

，求使得下面条件成立的最小代价：

存在一个长度为 $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

，然后按上面三种情况讨论，其中后两种都每次取堆顶。

文章操作