当前位置 博文首页 > 文章内容

    洛谷 U140205 虫群入侵

    作者: 栏目:未分类 时间:2020-11-14 15:00:48

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    洛谷 U140205 虫群入侵

    洛谷传送门

    题目背景

    “圣堂武士们,亮出光刃!”

    题目描述

    虫群入侵了星灵的母星——艾尔

    形势紧迫,大主教需要在最短时间内挑选出一支人数为k的精锐部队来抵抗虫群。

    每一位星灵战士都有一个能力值V,而一直精锐部队的能力值是其所有成员能力值的最大公约数。

    虫群已然降临,生灵涂炭。于是大主教找到了你——JDOI滴神。 他想知道精锐部队的最大能力值是多少。

    输入格式

    第1行,一个整数N。 第2行,N个整数,表示第i个战士的能力值。

    输出格式

    共n行

    第i行表示k=i时,精锐部队的最大能力值


    题解:

    2020.11.14模拟赛T1 100pts场。

    列约数找规律。

    长了个记性:0与任何数的GCD都是它本身。

    代码:

    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int maxn=10010;
    const int maxm=1e6+6;
    int n,maxx,last;
    int a[maxn],cnt[maxm],mp[maxn];
    void fac(int x)
    {
    	for(int i=1;i<=sqrt(x);i++)
    		if(x%i==0)
    		{
    			cnt[i]++,cnt[x/i]++;
    			if(i==x/i)
    				cnt[i]--;
    		}
    }
    int main()
    {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    		fac(a[i]);
    		maxx=max(maxx,a[i]);
    	}
    	for(int i=1;i<=maxx;i++)
    		if(cnt[i])
    			mp[cnt[i]]=max(mp[cnt[i]],i);
    	for(int i=n;i>=1;i--)
    		if(mp[i]<mp[last])
    			mp[i]=mp[last];
    		else
    			last=i;
    	for(int i=1;i<=n;i++)
    		printf("%d\n",mp[i]);
    	return 0;
    }