专栏文章

题解：P14223 [ICPC 2024 Kunming I] 乐观向上

bbjzjh
P14223题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlgize
此快照首次捕获于
2025/12/02 04:20
3 个月前
此快照最后确认于
2025/12/02 04:20
3 个月前
查看原文

题目大意

构造一个 0∼n−10 \sim n - 1 的排列排列 p0,p1,p2,⋯ ,pn−1p_0, p_1, p_2, \cdots, p_{n-1}，满足每个异或前缀和都不等于 00 的同时字典序最小。
n≤106n \le 10^6。

做法

思考如何构造，想要字典序最小肯定是一个 0∼n−10 \sim n - 1 的最小，但是这样中间会异或起来等于 00。找规律时可以发现每四个数异或起来等于零，考虑在 xor⁡i=1kai=0\operatorname{xor}_{i=1}^{k} a_i= 0 的时候交换 aka_k 和 ak+1a_{k + 1}。想要证明这个方案是最优的，就需要证明不会连续交换，那么就是连续两个异或起来都等于 00，只有在 ak+1=0a_{k+1}=0 的时候才会出现这种情况，很显然，这是不可能的，所以这样的方案是最优的。
无解的情况只可能是所有的数异或起来等于 00，特判即可。
具体见代码。

AC 代码

CPP
#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';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...