AGC010E Rearranging 做题记录

给定一个长 $n$ 的正整数序列 $a_i$，Alice 会把整个序列任意排列，然后 Bob 可以进行任意次操作，每次选择两个相邻的互质的数交换位置。

Alice 希望最终序列的字典序尽量小，而 Bob 希望字典序尽量大。

若 Alice 和 Bob 都足够聪明，求最终序列。

考虑建立一个 $n$ 个点的无向图 $G$， $\forall 1\le i<j\le n,\gcd(a_i,a_j)\not=1$ 都有 $(i,j)\in G$。

考虑 Alice 的操作对 Bob 的影响，设他任意排列后的序列为 $b$。那么 $\forall 1\le i<j\le n,\gcd(b_i,b_j)\not=1$，Bob 都无法把 $b_j$ 移到 $b_i$ 前面。所以 Alice 相当于是给 $G$ 中每条边都定向，使得得到的有向图 $H$ 是个 DAG，Bob 则会找到 $H$ 中字典序最大的拓扑序。

那么问题转化为给 $G$ 中的边定向使得得到的有向图 $H$ 是 DAG 且拓扑序字典序最大值最小。考虑 $H$ 固定时 Bob 如何找到字典序最大的拓扑序，显然只要用大根堆拓扑就行了。也就是说，若当前入度为 $0$ 的点集为 $S$，Bob 会选择 $S$ 中最大的元素进行拓展。

考虑如何定向，显然要让 $S$ 中最小的元素 $x$ 控制（即指向）尽可能多的其它元素，这样这些元素都会被放到 $x$ 的后面。那么按 $a_i$ 从小到大对每一个 $i$ 跑 dfs，dfs $u$ 时对于所有与 $u$ 有连边的点 $v$ 再按照 $a_v$ 从小到大 dfs 即可：

set<int> g[S];

void dfs(int x)
{
	vis[x]=true;
	for(int v:g[x]) if(!vis[v]) g2[x].push_back(v),ind[v]++,dfs(v);
}

这样做的正确性比较显然，考虑 $u$ 在拓扑时删掉后剩下的若干互不连通的子图，子图之间在拓扑序中的顺序显然 Alice 无法控制，而子图内部一定是让目前能拓展的字典序最小的点（$v$）控制尽可能多的其它点。

时间复杂度 $O(n^2\log V)$（$\log V$ 来自于计算 $\gcd$），代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>

using namespace std;

const int S=2005;

int n,a[S];
set<int> g[S];
bool vis[S];
vector<int> g2[S];
int ind[S];
int tt,ans[S];

inline int gcd(int x,int y)
{
	int t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

void dfs(int x)
{
	vis[x]=true;
	for(int v:g[x]) if(!vis[v]) g2[x].push_back(v),ind[v]++,dfs(v);
}

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=1;j<=n;j++)
		{
			if(i==j) continue;
			if(gcd(a[i],a[j])>1) g[i].insert(j);
		}
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
	priority_queue<pair<int,int>> q;
	for(int i=1;i<=n;i++) if(ind[i]==0) q.push(make_pair(a[i],i));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		ans[++tt]=u;
		for(int v:g2[u]) if(--ind[v]==0) q.push(make_pair(a[v],v));
	}
	for(int i=1;i<=n;i++) printf("%d ",a[ans[i]]);
	printf("\n");
	return 0;
}