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

zsyq · 2025-10-14 20:10:21 · 题解

题意简述

题目要求构造一个 0 到 n - 1 的排列，使得每个前缀的异或和都大于 0 ，并且要字典序最小。

解题思路

我们可以选择贪心构造字典序最小的序列：

• 我们维护当前异或和 now 与当前可用的最小数字 last。
• 枚举每个位置，对于每个位置，若 now \oplus last 为 0 就一直寻找直到下一个可用的数字或寻找到 n - 1 仍无法满足题意就跳出循环，输出 \texttt{impossible}。

AC代码

#include <bits/stdc++.h>
using namespace std;
inline int rd()
{
    int x=0,f=1;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+(s^48);s=getchar();}
    return x*f;
}
inline void pr(int x)
{
    if(x<0)putchar('-'),x=-x;
    char s[20];int i=0;
    do s[i++]=x%10+'0';while(x/=10);
    while(i--)putchar(s[i]);
}
int T;
int n;
int ans[1000005];
bool f[1000005];//标记是否已经选入 
void solve()
{
    memset(ans,-1,sizeof(ans)); 
    memset(f,0,sizeof(f));//数组要记得清零 
    int now=0;
    int last=0;
    for(int i=1;i<=n;i++)
    {
        if((now^last)!=0)
        {
            ans[i]=last;
            f[last]=1;
            now=now^last;
            while(f[last]==1&&last<n)
            {
                last++;
            }
        }
        else
        {
            int zhi=last;
            while((now^zhi)==0&&zhi<n)//寻找下一个合法的数 
            {
                zhi++;
            }
            if(zhi>=n)break;//若寻找至n仍不合法就跳出循环输出impossible 
            now=now^zhi;
            ans[i]=zhi;
            f[zhi]=1;
        }
    }
    for(int i=1;i<=n;i++)if(ans[i]==-1)
    {
        cout<<"impossible"<<endl;//若没有答案就输出impossible
        return;
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    cout<<endl;
    return;
}
int main()
{
    T=rd();
    while(T--)
    {
        n=rd();
        solve();
    }
    return 0;
}