[AGC010E]Rearranging

AGC010E

日常找性质。

• 对于两个不互质的数$a,b$，他们的相对顺序不会被改变。

其实这一条也就够了。。

把原序列中所有gcd不为$1$的对都连上边，这样我们就得到了一个简单无向图。
对于每一个联通块，先手要做一些事情。
对于这个联通块建立序列的某个位置，先手必须要保证它最小，而且这个联通块中与他互质并比他大的数不能通过交换达到这个位置。
那也就是说必须通过gcd链到达那个点，那个点才不会“篡位”
先手的最优策略是把每个连通块最小的点作为起点，然后每次找到最小且没走过的点走过去。
这样对于每个联通块直接从最小的点开始从小到大深搜建立拓扑图正好就是想要的东西了。
后手就是每次找入度为0且的点中最大的，然后把这个点删掉。

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
const int N=2002;
int n,hx[N],in[N],fir[N];
bool vis[N];
struct edge{
	int to,nx;
}eg[N*10];
struct node{
	int x,v;
	bool operator < (const node &b) const {
		return v<b.v;
	}
};
std::priority_queue <node> pq;

inline int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}

inline void add(int a,int b){
	static int cnt;
	eg[++cnt]=(edge){b,fir[a]};
	fir[a]=cnt;
	eg[++cnt]=(edge){a,fir[b]};
	fir[b]=cnt;
}

inline char gtc(){
	static char buf[20000],*h,*t;
	if(h==t){
		t=(h=buf)+fread(buf,1,20000,stdin);
	}
	return h==t?EOF:*h++;
}

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10+c-48,(c=getchar())>='0'&&c<='9');
	return x;
}

inline void dfs(int x){
	vis[x]=1;
	for(int i=1;i<=n;++i){
		if(!vis[i]&&gcd(hx[i],hx[x])!=1){
			++in[i];
			add(x,i);
			dfs(i);
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	n=nxi();
	for(int i=1;i<=n;++i) hx[i]=nxi();
	std::sort(hx+1,hx+n+1);
	for(int i=1;i<=n;++i){
		if(!vis[i]) pq.push((node){i,hx[i]}),dfs(i);
	}
	while(!pq.empty()){
		node x=pq.top();
		pq.pop();
		printf("%d ",x.v);
		for(int i=fir[x.x];i;i=eg[i].nx){
			int y=eg[i].to;
			if(--in[y]==0) pq.push((node){y,hx[y]});
		}
	}
	puts("");
	return 0;
}