文档章节

又是毕业季2

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 716
阅读 3
收藏 0

题目背景

“叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水,全凝聚在毕业晚会上,相信,这一定是一生最难忘的时刻!

题目描述

彩排了一次,老师不太满意。当然啦,取每位同学的号数来找最大公约数显然不太合理。于是老师给每位同学评了一个能力值。于是现在问题变为,从n个学生中挑出k个人使得他们的默契程度(即能力值的最大公约数)最大。但因为节目太多了,而且每个节目需要的人数又不知道。老师想要知道所有情况下能达到的最大默契程度是多少。这下子更麻烦了,还是交给你吧~

PS:一个数的最大公约数即本身。

输入输出格式

输入格式:
第一行一个正整数n。

第二行为n个空格隔开的正整数,表示每个学生的能力值。

输出格式:
总共n行,第i行为k=i情况下的最大默契程度。

输入输出样例

输入样例#1:
4
1 2 3 4
输出样例#1:
4
2
1
1
说明

【题目来源】

lzn原创

【数据范围】

记输入数据中能力值的最大值为inf。

对于20%的数据,n<=5,inf<=1000

对于另30%的数据,n<=100,inf<=10

对于100%的数据,n<=10000,inf<=1e6

最容易想出的就是枚举每次拿n个数,然后分别求gcd。但是显然在这里会TLE。那么我们有什么好办法呢?
首先我们对每个数进行质因数分解,并记录因子x出现的次数i。如果因子x出现了n次,显然它就是所有数的公约数。这样我们取最大的次数的数就得到了取n个数的时候的gcd。以此类推,我们取j个数,只需要寻找出现次数为j的因子就可以(平方的情况需要特殊讨论)
贴代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath> 
#include<algorithm>

using namespace std;
int n,a[10005],b[1000005],o[10005];

void before(int x)
{
    int y=sqrt(x);
    for(int i=2;i<=y;i++)
    {
        if(!(x%i))
        {
            if(i!=x/i)
            b[i]++,b[x/i]++;
            else b[i]++;
        }
    }
    b[x]++;
}

int main()
{
    scanf("%d",&n);
    int Max=-1e9;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);    
        before(a[i]);
        if(a[i]>Max)Max=a[i];
    }
    for(int i=1;i<=Max;i++)
    {
        if(!o[b[i]])o[b[i]]=i;
        else o[b[i]]=max(o[b[i]],i);
    }
    for(int i=1;i<=n;i++)
    {
        int mmax=-1;
        for(int j=i;j<=n;j++)
        {
            if(o[j]>mmax)mmax=o[j];
        }
        printf("%d\n",mmax==0?1:mmax);
    }
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52775595

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
又是一年考研季

又到了一年一度的考研选择困难症爆发的季节,不少准大四学生已经为了考研在自习室或者图书馆埋头苦干几个月了,但也有不少同学依然在考研和找工作之间摇摆不定。 “要不要考研?” “要不要考...

ApplySquare
2017/11/24
0
0
从失恋中走出来是什么感觉

图 | 来自网络 -1- 那天,我在桥下,她在桥上。清风吹过,柳枝轻摇,长发飘动,她微笑的看着远处的风景,我也在桥下看“风景”。这一刻,仿佛时光停止,万物皆无,有的只有我和她,我以前从来...

绫晓路
2017/12/25
0
0
为什么找不到工作的是你,技术差的还是你?

1、为什么找不到工作的是你 对于一些恰逢毕业季的学生来说,找工作真的没有那么可怕。那为什么找不到工作的是我呢?是啊,为什么是你呢?别人行,我不行?对,你就是缺乏自信。在「为什么找不...

一只小YU儿
2017/04/18
0
0
为什么现在的大学生都急功近利?

前几天一个同学问我,你的公众号一个月可以挣多少钱啊。我说“很长时间都没有赞赏了,有的话也就一块两块”。他说“好的吧”。 我非常明白他的好的吧是什么意思。如果我说可以挣一些钱,他立...

洪范同学
2017/06/27
0
0
又是一年大学毕业季,有感而发!自己这几年跌跌撞撞的过来了!

昨晚上在爱奇艺上看了几个关于毕业季的视频,突然有感而发,不禁打开OSCHINA写下一篇。 2007年是我的高考年,说实话家里给我的压力很大,目标就是一本最差也要二本。对于报什么学校选什么专业...

蜡笔小新_
2014/06/26
3.1K
51

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
42分钟前
4
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
4
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
13
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
14
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部