【蓝桥杯每日一题】选数异或——线段树

选数异或

蓝桥杯每日一题 2024-12-16 选数异或 线段树 DP 思维

题目大意

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

解题思路

本题分三种解题方式：

1、小白暴力解法：直接在[l,r]区间内进行双重循环即可到手40分。

先了解下前提知识：a^b=x <==> a^x=b

2、思维大佬DP法： f(i) 表示 0 ~ i 之间的与 i 相距最近的那个满足 异或x后的值的下标；然后如果 f(i-1)满足条件，那么f(i)一定也满足件，那么状态转移方程就是：$f(i)=max(f(i-1),last(a[i]\ast x))$；最后判断的时候 f® 一定是0~r之前最大的满足条件的下标，那么只需要判断 其值是否大于L 即可。
为什么执着要判断 0~R 之间的，而不是L_{R之间的？因为在L}R之间如果满足条件那么0~R一定会满足条件，那么这时候我们所要维护判断的边界只有左边界。

3、编程大佬线段树法：线段树的方法只是将DP法中的状态转移过程绕了一圈又回过来了。
也是先预处理每个位置的值所对应异或之后值的位置（都是左边的），然后线段树处理的是，每个区间的一个对应的最大值。要知道，这个最大值是一定小于它所在的下标的，所以说只需要处理找出最大值与左边界比较的结果即可。

40分暴力保分

#include <iostream>

using namespace std;
typedef long long ll;
const int N = 100010;
int a[N];
int n,m;
int x;

void sovle() {
    int l,r;
        cin>>l>>r;
        for(int i = l; i <= r;i++) {
            for(int j = i+1 ;j <= r;j++) {
//                cout<<"---> "<<a[i]<<" "<<a[j]<<" = "<<(a[i]^a[j])<<" "<<x<<endl;
                if((a[i]^a[j]) == x) {
                    
                    cout<<"yes"<<endl;
                    return ;
                }
            }
        }
    cout<<"no"<<endl;
}

int main()
{
    cin>>n>>m>>x;
    for(int i = 1;i <= n;i++) {
        cin>>a[i];
    }
    while(m--) {
        sovle();
    }
    return 0;
}

AC DP法

#include <bits/stdc++.h>

using namespace std;

const int N = 100010,M = 1 << 20;
int last[M],a[N];

int main() {
    int n,m,x;
    cin>>n>>m>>x;
    for(int i = 1;i <= n;i++) {
        int t;
        cin>>t;
        // 一直递进更新，而且每次都是取得最大值
        a[i] = max(a[i-1],last[t^x]);
        last[t] = i;
    }
    while(m--) {
        int l,r;
        cin>>l>>r;
        // 这是a[r] 就代表着 r 前面所能够匹配的那些值的最大值
        if(a[r] >= l) puts("yes");
        else puts("no");
    }
    return 0;
}

AC 线段树

#include <iostream>

using namespace std;

const int N = 100010,M = (1 << 20)+10;
int a[N<<2],last[M],Left[N]; // a数组长度一定要扩大四倍
int n,m,x;

void build(int u,int l,int r) {
    // 递归到叶子结点将所处理的位置更新到线段树上
    if(l == r) {
        a[u] = Left[l];
        return ;
    }
    int mid = l + r >> 1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    // 向上更新线段树 pushUp 操作
    a[u] = max(a[u<<1],a[u<<1|1]);
}

int query(int u,int l,int r,int x,int y) {
    // 如果分后的区间被全包含，直接返回即可
    if(l >= x && r <= y) {
        return a[u];
    }
    int mid = l + r >> 1;
    // 第一种情况：找原始区间的左节点
    if(y <= mid) {
        return query(u<<1,l,mid,x,y);
    } else {
        /**
         * 第三种情况：
         *  l[________m_______]r
         *      x[____m_________]y 
         * 这时候要将目标区间也分开来算，然后取他们的最大值即可
        **/
        if(x <= mid) return max(query(u<<1,l,mid,x,mid),query(u<<1|1,mid+1,r,mid+1,y));
        else return query(u<<1|1,mid+1,r,x,y);  // 第二种情况：找原始区间的右节点
    }
}

int main() {
    cin>>n>>m>>x;
    for(int i = 1;i <= n;i++) {
        int t;
        cin>>t;
        // 预处理当前值所对应异或后的值的位置
        Left[i] = last[t ^ x];
        // 存储之前有的值，并存储索引
        last[t] = i;
    }
    // 建线段树
    build(1,1,n);
    while(m--) {
        int l,r;
        cin>>l>>r;
        // 在初始区间[1,n]中查找[l,r]中的所处理到的最大下标
        int k = query(1,1,n,l,r);
        // 判断这个最大下标是否在规定区间中
        if(k >= l) puts("yes");
        else puts("no");
    }
    return 0;
}

思考

这个题是比上一题好写一些的，但是思维难度是一点不减啊！！！

备注

想要一起备赛的同学可以评论区留言！