题解：CF2223D Zhily and Cycle

DeaphetS · 2026-05-13 09:32:35 · 题解

赛场上感受不到那股劲，人麻了。

首先可以想到要让每个点的出边都不一样，这是哈密顿环的必要条件。

于是可以考虑先搞一个满足条件的排列出来，这个是容易的，贪心即可。

但这时候构造出来的玩意可能是由多个置换环构成的，考虑使用调整法把他们全合并起来。

具体的，先把所有点按 a_i 排序，然后让排序后在位置 x 的点（即 a_i 第 x 小的点）向 x 连边。这样可以构造出一个符合限制的排列，并用并查集先把对应的连通情况求出来。

然后考虑合并，从小到大枚举 i，若 i 和 i-1 不在一个连通块内，则考虑交换他们的前驱，那么只需在数组上交换相邻位置即可，交换是否合法容易判断。

最后判一下合法性就做完了！

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int T,n,fa[N],nxt[N];
struct rua
{
    int l,id;
    void read(int i){scanf("%d",&l);id=i;}
    bool operator <(const rua &t)const{return l<t.l;}
}a[N];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        a[i].read(i);
        fa[i]=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)fa[Find(a[i].id)]=Find(i);
    for(int i=2;i<=n;i++)if(Find(i)!=Find(i-1))
        if(a[i].l<i)swap(a[i],a[i-1]),fa[Find(i-1)]=Find(i);
    for(int i=1;i<=n;i++)if(Find(i)!=Find(1) || a[i].l>i){printf("No\n");return;}
    for(int i=1;i<=n;i++)nxt[a[i].id]=i;
    printf("Yes\n");
    printf("1");
    int x=nxt[1];
    while(x!=1)printf(" %d",x),x=nxt[x];
    printf("\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)init();
}

交上去之后也是喜提最短解啊！