第十三届蓝桥杯A组：选数异或——三种解法（线段树、DP、ST表）

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

题目描述

给定一个长度为 $n$ 的数列 $A_1,A_2,\cdots ,A_n$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l,r]$ 中选择两个数使得他们的异或等于 $x$ 。

输入格式

输入的第一行包含三个整数 $n,m,x$ 。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$ 表示询问区间 $\left[l_i,r_i\right]$ 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 $x$ 则输出 yes, 否则输出 no。

样例 #1

样例输入 #1

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
1
2
3
4
5
6

样例输出 #1

yes
no
yes
no
1
2
3
4

提示

【样例说明】

显然整个数列中只有 2,3 的异或为 1 。

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $1\le n,m\le 100$;

对于 $40\%$ 的评测用例, $1\le n,m\le 1000$;

对于所有评测用例, $1\le n,m\le 10^5,0\le x<2^{20},1\le l_i\le r_i\le n$ ， $0\le A_i<2^{20}$ 。

蓝桥杯 2022 省赛 A 组 D 题。

分析

A组的题，题目有三种解法，但是这道题无论啥解法，实际上是万变不离其宗的，就是他的关键的对于某个点的预处理。想要解这题主要还是要想出这个处理。之所以写不同的这三种解法，主要是复习一下模板吧
首先，我们容易知道：若a^b=x，那么a^x=b，对于数组a[i]，我们可以通过关系式，找到a[i]^x的左边的最靠近下标，明显我们需要找到最靠近的下标，而当这个下标是大于等于所需要找的区间的左端点，即可满足这个区间内可以找到两个数的异或为x。
当对于一个数，其左边没有数与其异或等于x时，那么就将其置为0，而当我们不断输入数字的时候，我们需要同时存储这个数的下标，方便循环到下一个下标的时候找到这个数字（通过a^x=b这样的关系），具体看代码

解法一：线段树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[400005],a[100005],Left[100005],pos[2000005];
inline void buildtree(int k,int l,int r){
    if(l==r){t[k]=Left[r];return;}
    int mid=(l+r)>>1;
    buildtree(k<<1,l,mid),buildtree(k<<1|1,mid+1,r);
    t[k]=max(t[k<<1],t[k<<1|1]);
}
inline int query(int k,int l,int r,int x,int y){
    if(l==x&&r==y)return t[k];
    int mid=(l+r)>>1;
    if(y<=mid)return query(k<<1,l,mid,x,y);
    else
        if(x>mid)return query(k<<1|1,mid+1,r,x,y);
        else return max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
int main(){
    int n,m,x;cin>>n>>m>>x;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        Left[i]=pos[a[i]^x];
        pos[a[i]]=i;
    }
    buildtree(1,1,n);
    while(m--){
        int x,y;scanf("%d%d",&x,&y);
        int k=query(1,1,n,x,y);
        if(k>=x)printf("yes\n");
        else printf("no\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解法二：DP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[100005],pos[5000005];
int main(){
    int n,m,x;cin>>n>>m>>x;
    for(int i=1;i<=n;++i){
        int a;scanf("%d",&a);
        f[i]=max(f[i-1],pos[a^x]);
        pos[a]=i;
    }
    while(m--){
        int l,r;scanf("%d%d",&l,&r);
        if(f[r]>=l)printf("yes\n");
        else printf("no\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法三：ST表

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int st[100005][20],pos[5000005];
int main(){
    int n,m,x;cin>>n>>m>>x;
    for(int i=1;i<=n;++i){
        int a;scanf("%d",&a);
        st[i][0]=pos[a^x];
        pos[a]=i;
    }
    int k=log2(n);
    for(int i=1;i<=k;++i)
        for(int j=1;j+(1<<i)-1<=n;++j)
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    while(m--){
        int l,r;scanf("%d%d",&l,&r);
        int len=log2(r-l+1);
        int p=max(st[l][len],st[r-(1<<len)+1][len]);
        if(p>=l)printf("yes\n");
        else printf("no\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23