P8773 [蓝桥杯 2022 省 A] 选数异或 题解

· · 题解

首先根据异或性质可得出：

a \oplus b = x \Leftrightarrow a \oplus x = b

也就是说，对于已经给出的 a 数组，可以求出每一个 a_i 对应的异或值。

考虑设 f_i 表示当i为右端点时，[1,i] 中所有的合法异或值对中最大的左端点。当询问区间 [l,r] 时，只需检验 f_r 是否在区间内即可。

使用哈希表，复杂度 O(n+m)。

upd 2023.1.21:

Q1：

把 lst[a[i]]=i 放到 f[i]=max(f[i-1],lst[a[i]^x]); 上面去，否则就有 hack 如下：1 1 0 1 1 1，应输出 yes 实际输出 no，原因是忽略了可以自己跟自己组

A1:

题面中有原文：

选择两个数使得他们的异或等于 x。

这里我默认不能重复取。

upd 2025.7.5:

改正了评论区提到的复杂度错误的问题。

代码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
using namespace std;
const int N =100005;
int n,m,x; 
int a[N],f[N];
unordered_map<int, int> lst;
int main(){
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lst[a[i]]=i;
        f[i]=max(f[i-1],lst[a[i]^x]);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        if(f[r]<l){
            cout<<"no"<<endl;
        }else{
            cout<<"yes"<<endl;
        }
    }
    return 0;
}