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

135791a · 2025-10-20 16:22:15 · 题解

P14223 [ICPC 2024 Kunming I] 乐观向上

思路简述

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

AC代码

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