事业单位网站方案,nodejs做网站,网站开发和系统开发的区别,湘潭seo 推广快湘潭磐石网络[蓝桥杯 2022 省 A] 选数异或
题目描述
给定一个长度为 nnn 的数列 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,⋯,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。
输入格式
输入的第一…[蓝桥杯 2022 省 A] 选数异或
题目描述
给定一个长度为 nnn 的数列 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,⋯,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。
输入格式
输入的第一行包含三个整数 n,m,xn, m, xn,m,x 。
第二行包含 nnn 个整数 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,⋯,An。
接下来 mmm 行每行包含两个整数 li,ril_{i}, r_{i}li,ri 表示询问区间 [li,ri]\left[l_{i}, r_{i}\right][li,ri] 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 xxx 则输出 yes, 否则输出 no。
样例 #1
样例输入 #1
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3样例输出 #1
yes
no
yes
no提示
【样例说明】
显然整个数列中只有 2,3 的异或为 1 。
【评测用例规模与约定】
对于 20%20 \%20% 的评测用例, 1≤n,m≤1001 \leq n, m \leq 1001≤n,m≤100;
对于 40%40 \%40% 的评测用例, 1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000;
对于所有评测用例, 1≤n,m≤105,0≤x220,1≤li≤ri≤n1 \leq n, m \leq 10^5,0 \leq x2^{20}, 1 \leq l_{i} \leq r_{i} \leq n1≤n,m≤105,0≤x220,1≤li≤ri≤n 0≤Ai2200 \leq A_{i}2^{20}0≤Ai220 。
蓝桥杯 2022 省赛 A 组 D 题。
分析 A组的题题目有三种解法但是这道题无论啥解法实际上是万变不离其宗的就是他的关键的对于某个点的预处理。想要解这题主要还是要想出这个处理。之所以写不同的这三种解法主要是复习一下模板吧 首先我们容易知道若a^bx那么a^xb对于数组a[i]我们可以通过关系式找到a[i]^x的左边的最靠近下标明显我们需要找到最靠近的下标而当这个下标是大于等于所需要找的区间的左端点即可满足这个区间内可以找到两个数的异或为x。 当对于一个数其左边没有数与其异或等于x时那么就将其置为0而当我们不断输入数字的时候我们需要同时存储这个数的下标方便循环到下一个下标的时候找到这个数字通过a^xb这样的关系具体看代码 解法一线段树
#includebits/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(lr){t[k]Left[r];return;}int mid(lr)1;buildtree(k1,l,mid),buildtree(k1|1,mid1,r);t[k]max(t[k1],t[k1|1]);
}
inline int query(int k,int l,int r,int x,int y){if(lxry)return t[k];int mid(lr)1;if(ymid)return query(k1,l,mid,x,y);elseif(xmid)return query(k1|1,mid1,r,x,y);else return max(query(k1,l,mid,x,mid),query(k1|1,mid1,r,mid1,y));
}
int main(){int n,m,x;cinnmx;for(int i1;in;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 kquery(1,1,n,x,y);if(kx)printf(yes\n);else printf(no\n);}
}解法二DP
#includebits/stdc.h
#define ll long long
using namespace std;
int f[100005],pos[5000005];
int main(){int n,m,x;cinnmx;for(int i1;in;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);}
}解法三ST表
#includebits/stdc.h
#define ll long long
using namespace std;
int st[100005][20],pos[5000005];
int main(){int n,m,x;cinnmx;for(int i1;in;i){int a;scanf(%d,a);st[i][0]pos[a^x];pos[a]i;}int klog2(n);for(int i1;ik;i)for(int j1;j(1i)-1n;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 lenlog2(r-l1);int pmax(st[l][len],st[r-(1len)1][len]);if(pl)printf(yes\n);else printf(no\n);}
}
