按位的数学运算,也叫半加运算(不进位加法运算)
转换为二进制后 对应相同为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 | map<int,int>mp;//key是Ai value是序号 |