Codeforces Round #669 (Div. 2) B. Big Vova (枚举)

题意:有一个长度为\(n\)的序列,你需要对其重新排序,构造一个新数组\(c\),\(c_{i}=gcd(a_{1},...,a{i})\)并且使得\(c\)的字典序最小.
题解:直接跑\(n\)次,每次找一个目前最大的\(gcd\)出来,并标记位置模拟一下就好了.

代码:

int t;

int n;

int a[N],b[N];

int st[N];

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	t=read();

	while(t--){

		n=read();

		me(st,0,sizeof(st));

		for(int i=1;i<=n;++i){

			a[i]=read();

		}

		int now=0;

		for(int i=1;i<=n;++i){

			int mx=0;

			int pos=-1;

			for(int j=1;j<=n;++j){

				int tmp=__gcd(a[j],now);

				if(tmp>mx && !st[j]){

					mx=tmp;

					pos=j;

				}

			}

			now=mx;

			st[pos]=true;

			printf("%d ",a[pos]);

		}

		puts("");

	}

    return 0;

}

巴特西

Codeforces Round #669 (Div. 2) B. Big Vova (枚举)

最新文章

热门文章