题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

Cherry_Pop · 2025-11-01 23:37:29 · 题解

前言

为什么我找不到贪心的题解。\ 这题显然贪心

思路

• 根据 xor 的性质，不难发现 xor 是可以前缀异或和的。
• 显然当区间 \left[i，j-1\right] 异或和不为 k ，但区间 \left[j，l\right] 异或和为 k ，且 \left[i，j\right] 异或和为 k 时，一定是选择区间 \left[i，j\right] 更优，不然的话会占用更多区间数量，可能对后续区间的选择产生干扰，进而影响整体最优解的实现。\ 其中 1\le i\le j\le l\le n。

  AC记录

  #include<bits/stdc++.h>
  #define int unsigned long long
  using namespace std;
  void read(int &x){
  x=0;bool f=0;char ch=getchar();
  while(ch>'9'||ch<'0'){
      if(ch=='-')f=1;
      ch=getchar();
  }do{x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}while(ch>='0'&&ch<='9');
  x=f?-x:x;
  }
  int n,m,f[500001],x,s;
  map<int,bool>a,b;
  signed main(){
  read(n),read(m);
  for(int i=1;i<=n;i++)read(x),f[i]=f[i-1]^x;a[0]=1;
  for(int i=1;i<=n;i++){
      if(s%2){
          if(b[m^f[i]])s++,b=a,a[f[i]]=1;
          else b[f[i]]=1;
      }
      else{
          if(a[m^f[i]])s++,a=b,b[f[i]]=1;
          else a[f[i]]=1;
      }
  }
  cout<<s;
  return 0;
  }