[AGC010E] Rearranging 题解

Statement

AT2306 [AGC010E] Rearranging - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

我们考察一下这个交换位置的操作

它的前提是相邻且互质，但这个条件并不是很好处理

我们知道了什么情况下可以交换，考虑什么时候交换不了

如果 \(x,y\) 互质但不相邻，仍然可能通过某种方式交换，可能不行。

如果 \(x,y\) 不互质，那么在先手排序完后，它们的顺序不可能被交换。意思说，如果两个数不互质，先手可以让其中一个数始终在另一个数前面。

先手肯定是想让小的在前面。

我们不妨在不互质的点对之间连边，形成诸多联通块

对于一个联通块内，先手一定可以把块中最小的点排在最前面

下一步排什么呢？能不能贪心地把次小排第二位？

考虑到次小和最小点之间可能没有连边，如果次小在第二位，此时第一第二位相邻且互质，可以交换。

所以，下一步只能取和最小点有连边的最小的一个，递归下去即可

也就说是，联通块内，先手对每一条边定了向，让原图成了一张 DAG

这里定向边 \(i\to j\) 的实际意义是，给 \(a_j\) 一个必须在 \(a_i\) 后面的限制。

现在，我们考虑联通块间怎么办

这个时候，先手是无能为力的，而交给后手发挥

后手可以进行什么操作？

• 可以随意交换联通块的顺序
• 对于一个点，如果它的所有限制（边）都解除了，它可以排在限制后的任意位置

• 思路1：每个联通块内处理完后，形成了一个个序列，后手只需要类似归并排序（归并是稳定排序）地合并就可以了
• 思路2：因为最后是多张 DAG，我们考虑执行拓扑排序，不同的是，我们需要使用大根堆来达到贪心的目的

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3+5;

int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

vector<int>Edge[N];
int a[N],g[N][N],in[N],n;
bool vis[N];

int gcd(int a,int b){return b?gcd(b,a%b):a;}
void dfs(int u){
    vis[u]=1;
    for(int i=1;i<=n;++i)
        if(!vis[i]&&g[u][i])
            Edge[u].push_back(i),++in[i],dfs(i);
}
void toposort(){
    priority_queue<int>q;
    for(int i=1;i<=n;++i)
        if(!in[i])q.push(i);
    while(q.size()){
        int u=q.top();q.pop();
        printf("%lld ",a[u]);
        for(auto v:Edge[u])q.push(v);
    }
}

signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(gcd(a[i],a[j])!=1)
                g[i][j]=g[j][i]=1;
    for(int i=1;i<=n;++i)
        if(!vis[i])dfs(i);
    toposort();
    return 0;
}