题解 P6747 【Teleport】

囧仙

2020-08-08 22:05:50

Solution

## 题目大意 有 $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; } ```