## 题目大意
有 $n$ 个数字 $a_i$ 和 $q$ 次询问。每次给出一个非负整数 $m$ ,求能够使得
$$\sum_{i=1}^n a_i \oplus k \le m$$
的最大的非负整数 $k$ 。若无解,输出 $-1$ 。
## 题解
观察到,$k$ 二进制下第 $i$ 位对花费的贡献与其他二进制位无关。于是,我们能够预处理出 $k$ 的第 $i$ 位分别是 $0$ 与 $1$ 时会产生的费用 $P_i,Q_i$ 。考虑贪心地决定二进制下第 $i$ 位是多少。
为了达成限制条件,我们优先选择花费更少的那一个。假如 $P_i < Q_i$ ,我们就在第 $i$ 位上选择 $0$ ;否则选择 $1$ 。如果操作后的总花费已经超过了 $m$ ,就说明无解,输出 $-1$ 即可。
若有解,考虑最大化 $k$ 的值。我们从最高位向最低位计算。如果原先选择的是 $0$,且我们能够接受**新增**的花费,就将它改为 $1$ ,并记录花费。
要注意的是,由于答案可能达到 $2^{60}$ 的级别,因此 $Q_i$ 的值域可能很大(达到 $2^{90}$ 左右)。我们可以特判这种情况,将超过 $2^{60}$ 的 $Q_i$ 直接赋值为 $2^{60}$ 。
## 参考代码
```pas
var A:array[1..100000] of longint;
var P:array[0..64] of int64;
var Q:array[0..64] of int64;
var T:array[0..64] of int64;
var n,m:longint; var i,j:longint;
var w,ans:int64;
begin
T[0]:=1;
for i:=1 to 60 do T[i]:=T[i-1]*2;
for i:=0 to 60 do P[i]:=0;
for i:=0 to 60 do Q[i]:=0;
read(n); for i:=1 to n do begin
read(A[i]);
for j:=0 to 60 do begin
P[j]:=P[j]+ (A[i] and T[j]);
Q[j]:=Q[j]+((not A[i]) and T[j]);
if Q[j]>T[60] then Q[j]:=T[60];
end;
end;
read(m);
for i:=1 to m do begin
read(w);ans:=0; for j:=60 downto 0 do begin
if P[j]<Q[j] then w:=w-P[j]
else begin
w:=w-Q[j];
ans:=ans or T[j];
end;
end;
if w<0 then writeln(-1) else begin
for j:=60 downto 0 do begin
if ((P[j]<Q[j]) and (w>=Q[j]-P[j])) then begin
w:=w-Q[j]+P[j];
ans:=ans or T[j];
end;
end;
writeln(ans);
end;
end;
end.
```