AGC010E - Rearranging

134 阅读 0 评论 89 点赞

我是靠谱客的博主辛勤白羊，这篇文章主要介绍AGC010E - Rearranging，现在分享给大家，希望可以做个参考。

中文题意：
Hellen首先按照自己的意愿将n个数重新排列(可以是原来的顺序),然后她让Shawn进行如下操作:选择一对相邻且互质的数,交换它们的位置.(这个操作Shawn可以进行无数次.)
Hellen想要这个序列的字典序尽可能小,而Shawn想要这个序列的字典序尽可能大.Hellen想让你告诉她在两人都采取最优策略的情况下,最后形成的序列是什么样子的.
题解：
这个题考试的时候居然没有想出来，其实很简单，我们可以很简单的发现，如果两个数的gcd=不为1，那么这两个数的相对位置是无法改变的，基于这一点，我们可以把相对位置无法改变的数连边，然后跑拓扑序，由于前面的人要使字典序尽可能小，我们可以开始把较小的卡在前面，之后为了尽量不让第2个人把后面更大的抓过来，我们跑dfs把它能影响的数放置在后面。之后跑一遍拓扑就OK了。

复制代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=2005;
int n,a[MAXN];
int rd[MAXN];
int vis[MAXN];
struct edge
{
	int v,nxt;
	edge(){}
	edge(int vv,int nn)
	{
		v=vv,nxt=nn;
	}
}E[MAXN*MAXN];
int w[MAXN],ncnt=0;
struct node
{
	int id,val;
	node(){}
	node(int ii,int vv)
	{
		id=ii,val=vv;
	}
	bool operator < (const node &a)const 
	{
		return a.val>val;
	}
};
priority_queue<node>q;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
void addedge(int u,int v)
{
	ncnt++;
	E[ncnt]=edge(v,w[u]);
	w[u]=ncnt;
}
void dfs(int u)
{
	vis[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]&&gcd(a[u],a[i])!=1)
		{
			dfs(i);
			rd[i]++;
			addedge(u,i);
		}
	}
}
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++)
		if(!vis[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		if(rd[i]==0)
			q.push(node(i,a[i]));
	while(!q.empty())
	{
		node k=q.top();
		q.pop();
		printf("%d ",k.val);
		for(int i=w[k.id];i;i=E[i].nxt)
		{
			int v=E[i].v;
			rd[v]--;
			if(rd[v]==0)
				q.push(node(v,a[v]));
		}
	}
}

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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=2005;
int n,a[MAXN];
int rd[MAXN];
int vis[MAXN];
struct edge
{
	int v,nxt;
	edge(){}
	edge(int vv,int nn)
	{
		v=vv,nxt=nn;
	}
}E[MAXN*MAXN];
int w[MAXN],ncnt=0;
struct node
{
	int id,val;
	node(){}
	node(int ii,int vv)
	{
		id=ii,val=vv;
	}
	bool operator < (const node &a)const 
	{
		return a.val>val;
	}
};
priority_queue<node>q;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
void addedge(int u,int v)
{
	ncnt++;
	E[ncnt]=edge(v,w[u]);
	w[u]=ncnt;
}
void dfs(int u)
{
	vis[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]&&gcd(a[u],a[i])!=1)
		{
			dfs(i);
			rd[i]++;
			addedge(u,i);
		}
	}
}
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++)
		if(!vis[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		if(rd[i]==0)
			q.push(node(i,a[i]));
	while(!q.empty())
	{
		node k=q.top();
		q.pop();
		printf("%d ",k.val);
		for(int i=w[k.id];i;i=E[i].nxt)
		{
			int v=E[i].v;
			rd[v]--;
			if(rd[v]==0)
				q.push(node(v,a[v]));
		}
	}
}