AGC010 E Rearranging题意题解

107 阅读 0 评论 71 点赞

我是靠谱客的博主老迟到唇彩，最近开发中收集的这篇文章主要介绍AGC010 E Rearranging题意题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

黑板上写着?个整数，第?个数字是??。
A和B会按照以下操作把数列?重新排列：
·首先，A会把序列排成任何他想排成的样子。
·然后，B可以交换两个相邻且互质的数，他可以操作任意多次。
我们可以认为A是绝对聪明的，且他的目的是使最终的数列字典序尽量小；同时，我们也可以认为B是绝对聪明的，且他的目的是使最终的数列字典序尽量大。

题解

由于B只能交换互质的数，那么也就是说，所有互质的数在A确定位置后，它们的相对位置不会变了。
我们可以n^2从不互质的小数往大数连
然后我们这样想，由于B要交换，所以除了说保证答案是那个图的拓扑序以外…A并不能做出额外的限制
所以说答案其实就是最大的拓扑序
我们用优先队列拓扑排序即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2000+5;
typedef long long ll;
int n,a[N];
int gcd(int x,int y){
    if(!y)
        return x;
    return gcd(y,x%y);
}
int G[N][N];
struct node{
    int u,v,nxt;
}edge[N*2];
int head[N],mcnt;
void add_edge(int u,int v){
    mcnt++;
    edge[mcnt].u=u;
    edge[mcnt].v=v;
    edge[mcnt].nxt=head[u];
    head[u]=mcnt;
}
bool vis[N];
int rudu[N];
void dfs(int u){
    vis[u]=1;
    for(int v=1;v<=n;v++){
        if(G[u][v]&&!vis[v]){
            add_edge(u,v);
            rudu[v]++;
            dfs(v);
        }
    }
}
int ans[N];
typedef pair<int,int>pi;
priority_queue<pi>q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    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);
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(!rudu[i])
            q.push(pi(a[i],i));
    while(!q.empty()){
        int w=q.top().first,u=q.top().second;
        q.pop();
        ans[++cnt]=w;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v;
            rudu[v]--;
            if(!rudu[v])
                q.push(pi(a[v],v));
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
}