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

约定

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

思路

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

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

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

根据异或的性质，前一个集合中有奇数个该位为

1

，后一个集合中有偶数个该位为

1

，即 全集中有奇数个该位为 $1$ 。

因此，对于每一位，统计该位为

1

的数的个数，只要出现奇数，就有解；若都为偶数，则无解。

空间优化

由于只需要维护奇偶性，可以用 布尔数组 或 bitset 维护。

代码

CPP

#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");
	}
}

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

文章操作

约定

思路

代码

相关推荐

评论

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