【AGC010E】Rearranging（博弈，图论，拓扑排序）

142 阅读 0 评论 94 点赞

我是靠谱客的博主唠叨星星，这篇文章主要介绍【AGC010E】Rearranging（博弈，图论，拓扑排序），现在分享给大家，希望可以做个参考。

考场上想了很久才想到做法，然后考完后又想了很久，加上看了一下一些大佬的博客和 Atcoder 的官方题解，才完整地证明了整个做法的正确性。综合了一下，在这里详细阐述：

首先发现如果两个数不互质而且相邻，那么他们之间的相对位置不会改变。（就是本来在左边的不能跑到右边去）

考虑如果先手给出的排列是 $a_1,a_2,cdots,a_n$ 。

然后对于 $i < j$ ，如果 $gcd(a_i,a_j)neq 1$ ，那么由于刚刚得到的结论，就可以连一条单向边 $(i, j)$ ，表示后手排完的序列中， $a_i$ 必须在 $a_j$ 的左边。显然这是一个 $DAG$ 。

然后我们就可以通过拓扑排序来找到一组合法的后手排完的序列。

那么若后手想要排完的序列字典序最大，肯定是找字典序最大的拓扑序。（实现就是把普通的队列换成优先队列）

此时考虑当后手用最优策略时，先手应该怎么给出排列才会使得后手排完的序列字典序最小。

同样放在图上：对于 $gcd(a_i,a_j)neq 1$ ，我们就连两条单向边 $(i, j)$ 、 $(j, i)$ 。显然，这构成了若干个连通块。

我们现在要做的就是，在这张图的基础上，选出一些边组成一个新的图，且满足这个图是若干个 $DAG$ ，然后要使得这个新图的字典序最大的拓扑序最小。（不妨称某一个 $DAG$ 的字典序最大的拓扑序为 $DAG$ 的最优序列）

先考虑最简单的情况：只有一个连通块。

首先记以下操作为 $d f s (u)$ ：

按照权值从小到大的顺序枚举 $u$ 的儿子 $v$ ，如果 $v$ 未被遍历过，就连单向边 $(u, v)$ ，并进行操作 $d f s (v)$ 。

那么显然最优的方案就是先找到这个连通块内权值最小的点作为唯一入度为 $0$ 的点 $r t$ ，然后进行 $d f s (r t)$ 。

$d f s (u)$ 先遍历权值小的儿子的原因：

如果我先遍历了小的儿子 $v_1$ ，说不定能 $operatorname{dfs}(v_1)$ 的过程中遍历到某一个大的儿子 $v_2$ ，这样子就不用连边 $u,v_2)$ ，此时产生的 $text{DAG}_1$ 的最优序列就会更小。

而从大儿子 $v_2$ 开始遍历的话，肯定会有连边 $u,v_2)$ ，此时从大儿子开始遍历产生的 $text{DAG}_{2}$ 的最优序列就会大于等于从小儿子开始遍历产生的 $text{DAG}_{1}$ 的最优序列。（此处由于这句太长了就断了一下句 ~~主要是作者语文水平不高~~）

所以可以证明当只有一个连通块的情况下，用这种方式建 $DAG$ 肯定是最优解。

那么有多个连通块的情况呢？其实只需要每个连通块取到最优解就好了，因为他们之间是互不影响的。

所以我们只用先建出一开始的无向图，然后再按上述方式建出 $DAG$ ，最后跑一遍字典序最大的拓扑排序，整道题就完成了。

代码如下：

复制代码

#include<bits/stdc++.h>

#define N 2010
#define INF 0x7fffffff

using namespace std;

int n,a[N];
int cnt,du[N],head[N],nxt[N*N*2],to[N*N*2];
bool vis[N];

struct data
{
	int u;
	data(){};
	data(int a){u=a;}
	bool operator < (const data &b) const
	{
		return a[u]<a[b.u];
	}
};

vector<int>e[N];
priority_queue<data>q;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
	du[v]++;
}

void dfs(int u)
{
	vis[u]=1; 
	for(int i=0,size=e[u].size();i<size;i++)
	{
		int v=e[u][i];
		if(vis[v]) continue;
		adde(u,v);
		dfs(v);
	}
}

void Tuopu()
{
	for(int i=1;i<=n;i++)
		if(!du[i])
			q.push(data(i));
	while(!q.empty())
	{
		int u=q.top().u;
		q.pop();
		printf("%d ",a[u]);
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			du[v]--;
			if(!du[v]) q.push(data(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) e[i].push_back(j);
		}
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
	Tuopu();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>

#define N 2010
#define INF 0x7fffffff

using namespace std;

int n,a[N];
int cnt,du[N],head[N],nxt[N*N*2],to[N*N*2];
bool vis[N];

struct data
{
	int u;
	data(){};
	data(int a){u=a;}
	bool operator < (const data &b) const
	{
		return a[u]<a[b.u];
	}
};

vector<int>e[N];
priority_queue<data>q;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
	du[v]++;
}

void dfs(int u)
{
	vis[u]=1; 
	for(int i=0,size=e[u].size();i<size;i++)
	{
		int v=e[u][i];
		if(vis[v]) continue;
		adde(u,v);
		dfs(v);
	}
}

void Tuopu()
{
	for(int i=1;i<=n;i++)
		if(!du[i])
			q.push(data(i));
	while(!q.empty())
	{
		int u=q.top().u;
		q.pop();
		printf("%d ",a[u]);
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			du[v]--;
			if(!du[v]) q.push(data(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) e[i].push_back(j);
		}
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
	Tuopu();
	return 0;
}