Atcoder Grand Contest 009&010

010E Rearranging

题目描述

点此看题

解法

这种确定顺序的题，常用的方法是思考不变的相对顺序。

本题我们观察到不互质的数一定不会被后手改变相对顺序，并且考虑到相对顺序通常是用图论来表示的，所以我们把不互质的数之间连一条边，这样会得到一个无向图。

因为互质数的相对顺序是可以任意改变的，先手决定的只有互质的数的相对顺序。考虑先手的功能是给无向图定向（若 \(i\rightarrow j\) 则表示 \(p_i，定向完一定是个拓扑图），后手的功能是给这个无向图定下字典序最大的拓扑序。

先手的定向具有固定策略，首先值最小的点一定作为第一个点，然后我们考虑和它相连边的方向都固定了。然后考虑把下一个位置优先给值更小的点 \(x\) ，发现此时我们可以把 \(x\) 当根，这是一个递归的过程：

void dfs(int u)
{
	vis[u]=1;
	for(int v=1;v<=n;v++)
		if(!vis[v] && b[u][v])
			g[u].pb(v),dfs(v);
}

我们只需要保留在 \(\tt dfs\) 树上的边（因为非树边对顺序没有更强的限制），这种方法为什么是正确的呢？我的理解是我们让值小点的位置尽量小，就使他处在偏序关系的上层，但如果子树间无关联那么顺序是任意的。

如果有更加理性的证明请联系我，上面的文字就是我的一些感性理解。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 2005;
#define pb push_back
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[M],b[M][M],vis[M];
priority_queue q;vector g[M],ans;
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
void dfs(int u)
{
	vis[u]=1;
	for(int v=1;v<=n;v++)
		if(!vis[v] && b[u][v])
			g[u].pb(v),dfs(v);
}
void topo()
{
	while(!q.empty())
	{
		int u=q.top();q.pop();ans.pb(u);
		for(int v:g[u]) q.push(v);
	}
}
signed main()
{
	freopen("rearranging.in","r",stdin);
	freopen("rearranging.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			b[i][j]=b[j][i]=(gcd(a[i],a[j])>1);
	for(int i=1;i<=n;i++) if(!vis[i])
		q.push(i),dfs(i);
	topo();
	for(int x:ans) printf("%d ",a[x]);puts("");
}