题解：P14223 [ICPC 2024 Kunming I] 乐观向上
bjzjh
·
·
题解
题目大意
构造一个 0 \sim n - 1 的排列排列 p_0, p_1, p_2, \cdots, p_{n-1}，满足每个异或前缀和都不等于 0 的同时字典序最小。
## 做法
思考如何构造，想要字典序最小肯定是一个 $0 \sim n - 1$ 的最小，但是这样中间会异或起来等于 $0$。找规律时可以发现每四个数异或起来等于零，考虑在 $\operatorname{xor}_{i=1}^{k} a_i= 0$ 的时候交换 $a_k$ 和 $a_{k + 1}$。想要证明这个方案是最优的，就需要证明不会连续交换，那么就是连续两个异或起来都等于 $0$，只有在 $a_{k+1}=0$ 的时候才会出现这种情况，很显然，这是不可能的，所以这样的方案是最优的。
无解的情况只可能是所有的数异或起来等于 $0$，特判即可。
具体见代码。
## AC 代码
```
#include <bits/stdc++.h>
#define For(i, x, y) for(ll i = x; i <= y; ++ i)
typedef long long ll;
ll T, n;
int main(){
std::cin >> T;
while(T --){
std::cin >> n;
ll Xor = 0;
For(i, 0, n - 1){
Xor ^= i;
}
if(Xor == 0){
puts("impossible"); //无解
continue;
}
Xor = 0;
For(i, 0, n - 1){
Xor ^= i;
if(Xor == 0){
std::cout << i + 1 << ' ' << i << ' '; //交换位置
Xor ^= i + 1;
i ++;
}
else{
std::cout << i << ' '; //正常情况
}
}
std::cout << '\n';
}
}
```