给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两个数使得他们的异或等于 x x x 。
输入的第一行包含三个整数 n , m , x n, m, x n,m,x 。
第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An。
接下来 m m m 行，每行包含两个整数 l i , r i l_{i}, r_{i} li,ri 表示询问区间 [ l i , r i ] \left[l_{i}, r_{i}\right] [li,ri] 。
对于每个询问, 如果该区间内存在两个数的异或为
x
x
x 则输出 yes, 否则输出 no。
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
yes
no
yes
no
【样例说明】
显然整个数列中只有 2,3 的异或为 1 。
【评测用例规模与约定】
对于 20 % 20 \% 20% 的评测用例, 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100;
对于 40 % 40 \% 40% 的评测用例, 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1≤n,m≤1000;
对于所有评测用例, 1 ≤ n , m ≤ 1 0 5 , 0 ≤ x < 2 20 , 1 ≤ l i ≤ r i ≤ n 1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n 1≤n,m≤105,0≤x<220,1≤li≤ri≤n ， 0 ≤ A i < 2 20 0 \leq A_{i}<2^{20} 0≤Ai<220 。
蓝桥杯 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");
}
}
解法二：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");
}
}
解法三：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");
}
}
是否可以让这段代码更紧凑？我在这里错过了什么吗？ifvaluemax_ratemax_rateelsevalueend 最佳答案 这里有一些完全不同的东西:[min_rate,value,max_rate].sort[1] 关于ruby-如何更优雅地记下这三种情况？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/13309740/
目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言： 在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析 这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01
?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是： 如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。 如果m不为0，则将时读出来，然后将分读出来，如5
什么是最优雅的做法'string'=>['s','st','str','stri','strin','string']我一直在想一个类轮，但我不能完全做到。欢迎任何解决方案，谢谢。 最佳答案 这个怎么样？s='string'res=s.length.times.map{|len|s[0..len]}res#=>["s","st","str","stri","strin","string"] 关于ruby-'string'到['s','st','str','stri','strin','s
我有两个十六进制字符串，我需要对它们进行异或操作。我的六弦琴喜欢，a="1A6F2D31567C80644A5BEF2D50B986B";b="EF737F481FC7CDAE7C8B40837C80644";它们之间如何进行异或运算？你能给出一些指导方针吗？ 最佳答案 这适用于任何基地:>>(a.to_i(16)^b.to_i(16)).to_s(16)=>"f51c527949bb4dca36d0afae2c39e2f"但是你可以使用String#hex用于十六进制字符串。 关于ru
十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)
慢跑者与狗问题描述一个慢跑者在平面上沿椭圆以恒定的速率𝒗=𝟏跑步，设椭圆方程为:𝒙=𝟏𝟎+𝟐𝟎𝒄𝒐𝒔(𝒕),𝒚=𝟐𝟎+𝟓𝒔𝒊𝒏(𝒕)。突然有一只狗攻击他，这只狗从原点出发，以恒定速率𝒘跑向慢跑者，狗的运动方向始终指向慢跑者。分别求出𝒘=𝟐𝟎,𝒘=𝟓时狗的运动轨迹。模型建立设时刻t慢跑者的坐标为(𝑿(𝒕)，𝒀(𝒕))，狗的坐标为(𝒙(𝒕)，𝒚(𝒕))。则𝑿=𝟏𝟎+𝟐𝟎𝒄𝒐𝒔(𝒕),𝒀=𝟐𝟎+𝟏𝟓𝒔𝒊𝒏(𝒕)，狗从(0,0)出发，建立狗的运动轨迹的参数方程:由于狗始终对准人，因而狗的速度方向平行于狗与人位置的差向量：消去𝝀，得由题意𝑿=𝟏𝟎+𝟐𝟎𝒄𝒐𝒔𝒕,𝒀=𝟐𝟎+1𝟓𝒔𝒊𝒏(𝒕)，狗从(0,0)
本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#
目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式 2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器 （3）AUXR：辅助寄存器编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置 3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一