zhangas

Pay more attention

0%

异或运算的性质

按位的数学运算,也叫半加运算(不进位加法运算)
转换为二进制后 对应相同为1 不同为0
①归零律a^a=0
②恒等率a^0=a
③交换律结合律
④自反性a^b^a=b
实现交换两个数a=3 b=4
a=a^b b=a^b a=a^b 之后a=4 b=3

选数异或 蓝桥13届A组D

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x,给定 m 次查询,每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x。

输入格式
输入的第一行包含三个整数 n,m,x。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。
接下来 m 行,每行包含两个整数 [l,r] 表示询问区间 [l,r]。

输出格式
对于每个询问,如果该区间内存在两个数的异或为 x 则输出 yes,否则输出 no。
input:
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

output:
yes
no
yes
no

解题思路

性质 若a^b=x 则a^x=b
预处理出每个序号满足条件的最大左端点
再判断满足条件 [l,r] 中r的最大序数dp[r]是否比l大

样例解释

异或运算
显然维护的dp[3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int,int>mp;//key是Ai value是序号
void solve(){
int l=read(),r=read();
if(dp[r]>=l)puts("yes");
else puts("no");
}
int n=read(),m=read(),x=read();
for(int i=1;i<=n;i++){
int t=read();
dp[i]=max(dp[i-1],mp[t^x]);//t^x反求出 与t满足 ans^t==x的最小ans
mp[t]=i;
}
//预处理 a^b=x a^x=b 处理出dp[r]满足条件的最小左序号

while(m--){
solve();
}