专栏文章

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

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

文章操作

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

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

P14223 [ICPC 2024 Kunming I] 乐观向上

思路简述

因为对于所有 0≤i<n0 \le i < n，都有 p0⊕p1⊕⋯⊕pi>0p_0 \oplus p_1 \oplus \cdots \oplus p_i > 0。所以当填入 pip_i 时，p0⊕p1⊕p2⋯⊕pi−1≠pip_0 \oplus p_1 \oplus p_2 \cdots \oplus p_{i-1} \neq p_i。
又因为要让 p0,p1,p2⋯ ,pn−1p_0, p_1, p_2 \cdots, p_{n-1} 字典序最小。所以要每次要取能取的最小值。
不难想到，我们可以用一个链表维护当前那个数为最小值。
注意：当前面的异或值为最小值时，应选用次小值。

AC代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n,nx[N],h,ans[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while (t--) {
		cin>>n;
		for (int i=0;i<n;i++) nx[i]=i+1;
		h=0;
		int sum=0,f=1;
		for (int i=1;i<=n;i++) {
			if (h==sum) {
                if (nx[h]==n) f=0; 
                int t=nx[h];
				ans[i]=t;
				sum^=t;
				nx[h]=nx[t];
			}else {
				sum^=h;
				ans[i]=h;
				h=nx[h];
			}
		}
		if (!f) cout<<"impossible";
		else {
			for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
		}
		cout<<"\n";
    }
    return 0;
}

评论

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

正在加载评论...