题解 P6747 【Teleport】
囧仙
2020-08-08 22:05:50
## 题目大意
有 $n$ 个数字 $a_i$ 和 $q$ 次询问。每次给出一个非负整数 $m$ ,求能够使得
$$\sum_{i=1}^n a_i \oplus k \le m$$
的最大的非负整数 $k$ ,其中 $\oplus$ 是异或操作。若无解,输出 $-1$ 。
## 题解
题目中提到了位运算,而位运算一般与二进制紧密地结合在一起。考虑从该方面入手。
首先考虑 $k$ 的每一位对总花费的贡献。显然, $k$ 的每一位互相独立,因此我们可以预处理出每一位的贡献。具体而言,我们统计有多少个 $a_i$ ,它的二进制下第 $i$ 位为 $1$ ,记为 $P_i$ 。为什么要统计**多少个**而并非它的直接贡献呢?因为如果统计**贡献和**,那么 $\text{long long}$ 会溢出。
接着,我们能够贪心地选出一个 $k_0$ ,使得它的总花费最小。具体而言,对于 $k$ 的二进制下的第 $i$ 位,判断 $P_i$ 与 $n-P_i$ 的关系,选择更小的那一个。同时,我们统计出最小花费 $x_0$ 。
考察每一次询问。显然,如果 $m<t_0$ ,直接输出 $-1$ 即可。考虑从 $k_0$ 开始,尽可能地获得一个最大的 $k$ 。根据贪心的思想,我们从最高位开始逐步向最低位开始枚举,并更新答案。具体而言,如果 $k_0$ 第 $i$ 位是 $0$ ,就尝试将它改为 $1$ ,此时会产生新的费用 $(n-2\times P_i)\times 2^i$ 。但是要注意的是,如果直接比较新的费用与 $m$ 的值,就会**溢出**。如何解决呢?
观察到,
$$\begin{aligned}&&m'&\ge m+(n-2\times P_i)\times 2^i\cr
&\iff& m' \div 2^i & \ge m \div 2^i+(n-2\times P_i)\end{aligned}$$
于是,我们能够使用位移操作避免溢出的风险。
当然,你也可以使用 $\text{\_\_int128}$ 规避这些溢出,尽管这种方法可能不能在正规比赛中使用。
## 参考代码
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define up(l,r,i) for(LL i=l;i<=r;i++)
#define dn(l,r,i) for(LL i=l;i>=r;i--)
using namespace std;
typedef long long LL;
LL qread(){
LL w=1,c,ret;
while((c=getchar())> '9'||c< '0'); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
return ret;
}
const int MAXN =1e5+3,MAXM=60+3;
LL w,ans,o,t; int n,q,P[MAXM],Q[MAXM],s;
void write(LL x){
if(x>9) write(x/10); putchar(x%10+'0');
}
int main(){
n=qread(); up(1,n,i){
w=qread(); dn(30,0,j) if(w&(1<<j)) ++P[j];
}
up(0,60,i) Q[i]=n-P[i];
up(0,60,i){
if(P[i]<Q[i]) t+=(LL)P[i]<<i; else t+=(LL)Q[i]<<i,o|=1ll<<i;
}
q=qread(); up(1,q,i){
w=qread(),ans=o,s=64-__builtin_clzll(w);
if(w<t) puts("-1"); else {
w-=t;
dn(s,0,j){
if(P[j]<Q[j]&&(w>>j)>=Q[j]-P[j])
w=w-((LL)(Q[j]-P[j])<<j),ans|=(1ll<<j);
}
write(ans),putchar('\n');
}
}
return 0;
}
```