题目大意
给定两个数
l
,
r
l, r
l,r,将
[
l
,
l
+
1
,
.
.
.
,
r
?
1
,
r
]
[l, l + 1,..., r-1, r]
[l,l+1,...,r?1,r]的一个任意排列，全部异或
x
x
x，得到一个新的数组
a
a
a。
给定
l
,
r
l, r
l,r和
a
a
a数组，求
x
x
x。
其中
0
=
l
≤
r
≤
2
17
0 = l \le r \le 2^{17}
0=l≤r≤217
题目链接
思路
我们按位处理，我们计算异或前的数组每一位
1
1
1的个数，设为
c
n
t
A
cntA
cntA，计算异或后的数组每一位
1
1
1的个数，记为
c
n
t
B
cntB
cntB
-
那么一旦
c
n
t
A
i
!
=
c
n
t
B
i
cntA_i != cntB_i
cntAi?!=cntBi?,那么就说明
x
x
x这一位一定为
1
1
1 -
对于
c
n
t
A
i
=
=
c
n
t
B
i
cntA_i == cntB_i
cntAi?==cntBi?一样的位数，说明这一位可以为
1
1
1,也可以为
0
0
0。
因为
l
=
0
l=0
l=0,所以2.总是成立，因为异或后的数组一定有一个
x
x
x,异或前有个
0
0
0,所以
x
x
x某一位为
1
1
1，那么异或后的数这一位
1
1
1的数量一定会变化。
而一旦
l
=?
0
l \not = 0
l?=0,那么就有可能
1
1
1变为
0
0
0,
0
0
0变为
1
1
1的数量相同，抵消掉了，比如
[
1
,
2
]
⊕
2
=
[
0
,
3
]
[1,2] \oplus 2 = [0,3]
[1,2]⊕2=[0,3],前后每一位
1
1
1的数量都相同。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxN = 1e5 + 7;
int T, l, r, cnt1[53], cnt2[53];
inline void calc(int *cnt, int x)
{
int now = 0;
while(x) {
if(x & 1)
cnt[now]++;
now++; x >>= 1;
}
}
int main()
{
scanf("%d", &T);
while(T--) {
memset(cnt1, 0, sizeof cnt1);
memset(cnt2, 0, sizeof cnt2);
scanf("%d%d", &l, &r);
for(int i = l; i <= r; ++i) {
calc(cnt1, i);
int x; scanf("%d", &x);
calc(cnt2, x);
}
int ans = 0;
for(int i = 0; i < 31; ++i)
if(cnt1[i] != cnt2[i])
ans |= (1 << i);
printf("%d\n", ans);
}
return 0;
}
|