Description
构造一个序列 {a},这个序列的长度是 2m+1,且 0∼2m−1 中的每一个整数都必须出现 2 次。对于任何 ai=aj (i<j),都满足 ai⊕ai+1⊕⋯⊕aj−1⊕aj=k 。 如果不存在这样的序列输出 -1 。(0≤m≤17,0≤k≤109)
Source
Solution
显然当 k>2m−1 时无解,因为 2m−1 的每一个二进制位都是 1,与比它小的数异或后不可能大于 2m−1 。
考虑构造一个合法的序列。
我们在中间放一个数 k,然后在其两边放相同的数,比如:
0,1,2,3,…,2m−1,k,2m−1,…,3,2,1,0这显然是没有问题的,因为对于任意两个相同的数,它们中间两两相同的数能互相抵消为 0,最终的异或和一定是 k 。如果按这种方法构造,可以让除了 k 之外的所有数符合条件,但是还多了一个 k,考虑这个 k 应该放在哪里。
我们可以通过异或运算的性质得到一个结论:
n 为大于 1 的整数时,存在
0⊕1⊕2⊕⋯⊕(2n−1)=0证明:
将它们两两异或得到一个新的序列。
0⊕(2n−1)=2n−11⊕(2n−2)=2n−12⊕(2n−3)=2n−1⋯⋯(2n−1−1)⊕2n−1=2n−1显然异或后只剩下 2n−1 个 2n−1,根据异或运算的性质(偶数个相同数的异或和为 0)得到:当 n>1 时,2n−1 一定为偶数,该式子的值为 0 得证。
因此我们只需要将另一个 k 放在最后即可,这样两个 k 中间的数与其中一个 k 的异或和刚好为 0,0 异或另一个 k 的值为 k 。最后注意 n=1 时结论不成立需要特判。时间复杂度为 O(n) 。
Code
1 |
|
Be the first person to leave a comment!