【MX-X16-T1】「DLESS-3」XOR and Greater Sum 题解

· · 题解

约定

本文中所有的「位」指的是 二进制位。

思路

~根据幼儿园数学~，两个数比较大小时，高位大的比高位小的更大。

于是，只要有一个集合异或和的某一位比另一个集合异或和的同一位更大，则前者的异或和更大。

在二进制下，上述情况只有一种可能：前者的该位为 1，后者该位为 0。

根据异或的性质，前一个集合中有奇数个该位为 1，后一个集合中有偶数个该位为 1，即 全集中有奇数个该位为 1。

因此，对于每一位，统计该位为 1 的数的个数，只要出现奇数，就有解；若都为偶数，则无解。

:::success[空间优化] 由于只需要维护奇偶性，可以用 布尔数组 或 bitset 维护。 :::

代码

#include <bits/stdc++.h>
#define UP(i, l, r) for(int i = (l); i <= (r); ++ i)
using namespace std;
int t, n, a;
bool b[30], f;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t --){
        UP(j, 0, 29) b[j] = 0;
        f = 0;
        cin >> n;
        UP(i, 1, n){
            cin >> a;
            UP(j, 0, 29) b[j] ^= a >> j & 1;
        }
        UP(j, 0, 29) if(b[j]){
            f = 1;
            break;
        }
        cout << (f ? "Yes\n" : "No\n");
    }
}