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

71 阅读 0 评论 47 点赞

我是靠谱客的博主调皮小猫咪，最近开发中收集的这篇文章主要介绍P8773 [蓝桥杯 2022 省 A] 选数异或，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：[蓝桥杯 2022 省 A] 选数异或 - 洛谷

思路：

维护数组f和数组g

f [ i ] : 数字 i 出现的位置（下标）

g[ i ] : 第i个数最近的一个位置，使得在g[i]~i之间，存在一对数异或值为x

解释：

由于a^b=x -> b = a^x;

若b在前面出现过，那么f[b]就为数字b的位置下标，即包含 f[b]~当前位置的区间都是符合条件的区间。若b未出现过，则f[b]为默认值0，即不存在这样数对，使a^b=x。

代码：

#include<iostream>
using namespace std;

const int N = 100005;
const int M = (1 << 20) +10;

int g[N];
int f[M];
int a,b,x;
int n,m,l,r;

int main()
{
    cin>>n>>m>>x;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        g[i]=max(g[i-1],f[a^x]);
        f[a]=i;
    }

    for(int i=1;i<=m;++i)
    {
        cin>>l>>r;
        if(g[r]>=l) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }

    return 0;
}