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

选数 异或

蓝桥杯每日一题 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) = ma x (f (i - 1), l a s t (a [i] * 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;
}