题目

分析

首先我们知道，原A序列其实表示一个矩阵，而这个矩阵的对角线上的数字就是答案B序列。

接着\(a、b>=gcd(a,b)\)，所以序列A中的最大的数就是ans[1]，第二大的数就是ans[2]。

但是ans[3]并不一定就是序列A中的第三大的数，因为gcd(ans[1],ans[2])有可能是序列A中的第三大的数。

所以但找到了ans[i]，对于每个gcd(ans[i],ans[1~i-1])在序列A中删掉两个（就是删掉2（i-1）个。为什么是两个自己考虑）。时间复杂度\(O(n^2log_2n)\)

至于如何删掉gcd(ans[i],ans[1~i-1])，有两种方法：hash和二分

这里讲二分的方法：

因为已经将序列A从大到小排好了序，接着二分出位置最小的gcd(ans[i],ans[1~i-1])的位置，设位置为pos，接着将bz[pos]、bz[pos+1]赋值为false。

再设next，将next[pos]加二，下次删除就从next[pos]开始。如此类推。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=1005;

using namespace std;

int a[N*N],sum[N*N],n,m,ans[N*N],tot,next[N*N];

bool bz[N*N];

bool cmp(int x,int y)

{

	return x>y;

}

int gcd(int x,int y)

{

	if(y==0) return x;

    if(x<y) return gcd(y,x);

    else return gcd(y, x%y);

}

int rf(int l,int r,int p)

{

	while(l+1<r)

	{

		int mid=(l+r)/2;

		if(a[mid]>p)

			l=mid;

		else

			r=mid;

	}

	if(p==a[l])

		return l;

	else

		return r;

}

int main()

{

	scanf("%d",&n);

	a[0]=maxlongint;

	memset(bz,true,sizeof(bz));

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

	{

		scanf("%d",&a[i]);

		next[i]=i;

	}

	sort(a+1,a+n*n+1,cmp);

	ans[1]=a[1];

	int k=1;

	for(int i=2;i<=n*n && k<n;i++)

	{

		if(bz[i])

		{

			ans[++k]=a[i];

			for(int j=1;j<=k-1;j++)

			{

				int p=gcd(ans[j],ans[k]);

				int pos=rf(i+1,n*n,p);

				bz[next[pos]]=bz[next[pos]+1]=false;

				next[pos]=next[pos]+2;

			}

		}

	}

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

		printf("%d ",ans[i]);

}

巴特西

【NOIP2016提高A组模拟8.15】Password

题目

分析

最新文章

热门文章