题解 P6747 【『MdOI R3』Teleport】

### subtask 1,2 暴力即可。 ### subtask 3 发现 $a_i$ 上限非常大，我们考虑看第 $i$ 位 $(2^i\geq m)$，如果这一位不能把 $1$ 全部消掉就输出 $-1$，否则算答案。 至于剩下的数位，暴力计算。 ### subtask 4 ~~可能是给忘记开 long long 的选手准备的。~~ ### subtask 5（正解） 看到异或，想到拆位。 可以统计出每一位上 $1$ 的个数 $b_i$，计算答案时如果 $k$ 在二进制下的当前位取 $0$，那么当前位对答案的贡献就是 $2^ib_i$；当前位取 $1$，对答案的贡献就是 $2^i(n-b_i)$。 对于每次询问，由于高位填 $1$ 一定比低位填 $1$ 更优，考虑贪心。 但是这样做可能会有问题，我们还需要保证无后效性。 确保无后效性的方法是预处理后先扫一遍数组 $b$，求出一个模板 $k_0$，表示 $k$ 在取 $k_0$ 时答案最小，这样我们每把 $k_0$ 中的一个 $0$ 改成 $1$ 都可以保证答案是最优的。 询问时从高位到低位扫一遍，如果 $k_0$ 的当前位是 $1$，这一位显然不需要调整，如果当前位是 $0$，则判断当前位改为 $1$ 后答案是否超过 $m$，如果不超过则更新 $k$。 时间复杂度 $O(n\log m)$。 ```cpp #include<iostream> #include<cstdio> #include<cmath> using namespace std; #define int unsigned long long int n,a[100001],q,m,ans,sum,res,maxn; int b[55]; inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x; } void print(int x) { if(x>=10) print(x/10); putchar(x%10+'0'); } signed main() { n=read(); for(register int i=1;i<=n;++i) { a[i]=read(); int p=a[i],cnt=0; while(p) { b[++cnt]+=p&1; p>>=1; } } for(register int i=50;i>=1;--i) { if(b[i]>=n-b[i]) res+=1ull<<(i-1); maxn+=min(b[i],n-b[i])*(1ull<<(i-1)); } q=read(); while(q--) { m=read(); ans=res; sum=maxn; if(maxn>m) { puts("-1");//想一想，为什么 continue; } int p=log2(m); for(register int i=p+1;i>=1;--i) { if(ans&(1ull<<(i-1))) continue; if((sum-(min(b[i],n-b[i])*(1ull<<(i-1)))+(max(b[i],n-b[i])*(1ull<<(i-1))))<=m) { sum=sum-(min(b[i],n-b[i])*(1ull<<(i-1)))+(max(b[i],n-b[i])*(1ull<<(i-1))); ans+=1ull<<(i-1); } } print(ans); puts(""); } return 0; } ```