P13683题解

洛谷同文链接

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

思路

解决这个问题的关键是利用线性基（一种用于处理异或运算的数学工具）和异或的基本性质：

• 异或的基本性质：
  • 若 $A$ 是整个数组的异或和，$B$ 是某个子集的异或和，那么剩余元素的异或和为 $A\oplus B$（因为 $B\oplus(A\oplus B)A$）。
  • 要使子集 $S$ 的异或和等于 $A$，则剩余元素的异或和必为 0（因为 $A\oplus A=0$）。即问题等价于：判断数组是否存在非空真子集，其异或和为 0。
• 线性基的作用：
  • 线性基可以用来表示数组中所有元素的异或组合，基的大小反映了数组中线性无关元素的数量。
  • 若数组的线性基大小小于数组元素个数，则说明存在非空子集的异或和为 0（存在冗余元素）。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(){
	int n;
	cin>>n;
	vector<int> a(n);
	int totxor=0;
	
	for(int i=0;i<n;++i){
		cin>>a[i];
		totxor^=a[i];
	}
	
	if(totxor==0) return false;//如果整个数组的异或和为 0，那么不存在非空真子集的异或和为 0
	
	int k=31-__builtin_clz(totxor);//找到最高位的 1 的位置
	
	vector<int> ans(30,0);
	
	for(auto i:a){//对于每个数，尝试将其插入线性基
		int x=i;
		for(int i=29;i>=0;--i){//从高位到低位
			if((x>>i)&1){
				if(ans[i]==0){//如果当前位为 1，且线性基中没有该位为 1 的数，那么直接插入
					ans[i]=x;
					break;
				}
				else{
					x^=ans[i];
				}
			}
		}
	}
	
	return ans[k]!=0;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cout<<(check()?"Yes":"No")<<endl;
	}
	
	return 0;
}

AC 记录

复杂度分析：

• 时间复杂度：$O(Tn\log n)$，完全可以通过。
• 空间复杂度：$O(n)$，主要用于存储数组和线性基。