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