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

joshua0729 · 2025-08-10 17:09:23 · 题解

或许更好的阅读体验

题解：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)，主要用于存储数组和线性基。