自动搬运

查看原文

来自洛谷，原作者为

	infinities New Journey

搬运于2025-08-24 22:23:35，当前版本为作者最后更新于2020-08-11 15:07:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

异或计算方法：两个数二进制下按位比较，相同返回 0，不同返回 1。

首先看数据范围，答案和各种输入的变量都不会爆 long long，于是就可以放心做了。

考虑到有位运算和 $q \le 10^5$ 的数据范围，可以想到一定要按二进制下每一位来进行计算。

要使得 $k$ 尽可能大，且 $\sum_{i=1}^na_i\operatorname{xor}k \le m$。

我们可以按位进行贪心，即先统计 $a_i$ 每一位上 0 和 1 的个数，然后设 $a_i$ 中二进制下位数最多的一个的位数为 $maxx$，则我们对于 $k$ 的每一位，若 1 的个数比较多 $k$ 的这一位就是 1，反之亦然。

这样我们就能保证这时候的 $k$ 会使得 $S$ 最小，于是就可以开始贪心了。

接下来解决判断无解。判断无解即看 $S$ 最小时是否还大于 $m$，大于就无解，否则就可以接着做。

贪心的方法是从高到低贪，如果这一位是 0，我们就看能不能把它变成 1，判断的标准是这一位变成 1 之后当前是否还满足 $S \le m$，满足就可以贪，否则不能。

把一位变成 1 的方式可以使用异或，具体方式可以见代码。

最后还有一些代码实现上的小细节，可以看代码和注释。

code:

#include<bits/stdc++.h>
#define int long long
#define rint regester int
const int maxn = 1e6 + 10;
const int INF = 1e9;
using std::ios;
using std::cin;
using std::cout;
using std::max;
using std::min;
using std::sort;
using std::unique;
using std::lower_bound;
using std::swap;
using std::abs;
using std::acos;
using std::queue;
using std::map;
using std::string;
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, q, a[maxn], num01[233][2], maxsize;
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		a[i] = read();
		int aa = a[i];
		if(aa == 0)maxsize = max(maxsize, 1ll);//特判为0的情况，如果只有一个数且为0那就必须得特判
		for(int i = 1; aa; aa = aa >> 1, i++){
			maxsize = max(maxsize, i);//求出最大位数
			++num01[i][aa & 1];//统计每一位的0/1个数
		}
	}
	for(int i = 1; i <= maxsize; i++){
		num01[i][0] = n - num01[i][1];//因为有的数高位全是0，所以要这样计算一下
	}
	q = read();
	for(int i = 1; i <= q; i++){
		int m = read(), kmax, qwq = 0;
		int k = 0, fl = 0;//fl用来判无解
		for(int j = maxsize - 1; j >= 0; j--){
			if(min(num01[j + 1][1], num01[j + 1][0]) * (1ll << j) > m){
			    cout << -1 << "\n";
			    fl = 1;
			    break;
			}
		}//这一段判无解似乎也可以删了，但是我比较懒，所以就留着了
		if(fl == 1)continue;
		for(int j = maxsize; j >= 1; j--){
			if(num01[j][1] > num01[j][0])k = (k ^ (1ll << (j - 1)));//用异或解决把一位变成1
			qwq = qwq + min(num01[j][1], num01[j][0]) * (1ll << (j - 1));//贪心使S最小
		}
		if(qwq > m){
			cout << -1 << "\n";
			fl = 1;
		}
		if(fl == 1)continue;
		kmax = maxsize;
		for(int j = maxsize; ; j++){
			if(qwq + n * (1ll << j) <= m)kmax = j + 1;//先从高位贪心，顺便记录一下k的最高位
			else break;
		}
		if(kmax > maxsize)k = (k ^ (1ll << (kmax - 1))), qwq += n * (1ll << (kmax - 1));
		//这里要特判k的最高位在a_i的最高位之上再把这一位变成1，否则会出错
        for(int j = kmax; j >= 1; j--){//贪心看能不能把0变成1
			if(!(k & (1ll << (j - 1)))){
				if(j > maxsize){
					if(qwq + n * (1ll << (j - 1)) <= m){
						qwq += n * (1ll << (j - 1));
						k = k ^ (1ll << (j - 1));
					}
				}else
				if(j <= maxsize){
					if(qwq + (num01[j][0] - num01[j][1]) * (1ll << (j - 1)) <= m){
						qwq += (num01[j][0] - num01[j][1]) * (1ll << (j - 1));
						k = k ^ (1ll << (j - 1));
					}
				}
			}
		}
		cout << k << "\n";
	}
}