题解 P6747 【『MdOI R3』Teleport】

· · 题解

异或计算方法：两个数二进制下按位比较，相同返回 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";
    }
}