乐趣区

AtCoder-Context-ABC-171-E-Red-Scarf

jiezi

本文章为原创文章，未经过允许不得转载
运行要求
运行时间限制: 2sec
内存限制: 1024MB
原题链接

题目
小明有 N 只猫，N 为偶数。给每个猫一个编号从 1 到 N。每个猫给一个标牌，标牌上面写着一个非负整数。小明最近在学习异或运算 xor。
XOR 的定义

对于 N 个非负整数 x1,x2,x3...xN, 这些数的异或 x1 xor x2 xor x3...xor xN 按照下面的方式定义

x1 xor x2 xor x3 ... xor xn, 把他们用 2 进制表示。对应的位数上的 1 的个数为奇数的话，那么该位的结果为 1，对应的位数的 1 的个数为偶数的话，该位的结果为 0

小明在给猫的标牌上写数字的时候，赶快用一下刚刚学到的 xor 异或运算。

现在给 1 到 N 号猫另外一串特殊编号 ai。

这里的 ai 表示，除了 i 号猫以外，其他的猫的标牌号的 xor 运算结果。

我们给定 1 到 N 号猫的特殊编号 a1,a2,a3….aN

请根据 ai 求出，每个小猫的标牌号。

输入前提条件

  • 所有的输入均为整数
  • 2 <= N <= 200000
  • N 为偶数
  • 0 <= ai <= 1000000000
  • 给出的输入都能够找到相应的输出

输入

N
a1 a2 … aN

输出
输出一行，里面包含用空格分开的 N 个标牌号
从左往右第 i 个数字代表第 i 只猫的标牌号
满足条件的结果由多个的话，输出任意的结果

例 1
输入

4
20 11 9 24

输出

26 5 7 22

按照上面输出的标牌号，非自身以外的标牌号的 xor 结果，满足给定条件 ai

  • 5 xor 7 xor 22 = 20
  • 26 xor 7 xor 22 = 11
  • 26 xor 5 xor 22 = 9
  • 26 xor 5 xor 7 = 24

读懂题目
xor 用 ^ 来代替

相当于给定一串数组 a1,a2,a3,a4,a5…..aN
求另外一串数组 b1,b2,b3,b4,b5…..bN
要求满足
a1 = b2 ^ b3 ^ b4 … ^ bN
a2 = b1 ^ b3 ^ b4 … ^ bN
a3 = b1 ^ b2 ^ b4 … ^ bN
a4 = b1 ^ b2 ^ b3 … ^ bN
…
aN = b1 ^ b2 ^ b3 … ^ bN-1

想到于解 xor 的多元一次方程

解题思路

我们来看一下 XOR 运算的规律

如图所示 5 ^ 7 ^ 5 = 7
在等号左边的运算中 5 出现了 2 次，7 出现了 1 次


如图所示
5 ^ 5 = 0
等号左边的 5 出现了 2 次，最后 5 被消掉

5 ^ 5 ^ 5 = 5
等号左边的 5 出现了 3 次，最后 5 被留下

上面两个例子就是，在异或运算中，当某一个元素最后出现的个数是偶数的时候，最后会被消掉，出现的次数是奇数的时候，最后该数字会被留下来
比如下面，最后只有 m 和 t 被留在了等号右边
m ^ m ^ m ^ n ^ n ^ t = m ^ t


如图所示，我们已知 a1,a2,a3,…aN
如果我们把 a1,a2,a3…aN 一起做一个 XOR 运算的话，可以得到
a1 ^ a2 ^ a3 … ^ aN = b1 ^ b2 ^ b3 … ^ bN
因为 N 是偶数，bi 都只出现了 N - 1 次，N- 1 为奇数，所以最后它们 bi 都会被留下来

bi 代表了 i 号猫标牌上的数字
我们这样就知道了所有的 bi 的 xor 结果


对于每个 ai 来说，ai ^ (b1 ^ b2 ^ b3 ^…bN) = bi

我们已知 ai 和(b1 ^ b2 ^ b3 ^…bN), 就能求得 bi

代码

N = 4
ARR = [20, 11, 9, 24]

N = int(input())
ARR = list(map(int, input().split()))


def calculate(n, arr):
    s = arr[0]
    for i in range(1, n):
        s = s ^ arr[i]

    result = []

    for i in range(n):
        result.append(str(arr[i] ^ s))

    print(" ".join(result))


calculate(N, ARR)

总结
这一题考察了对于 XOR 异或运算的理解
同一个数出现的次数为偶数将会被清洗
同一个数出现的次数为偶数将会被留下

※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注

退出移动版