牛客OJ

Pro: 3/4/10

Rank: 117/1172

签到题

签到题

给出一个整数$n$,要求从1到$n$中选出一些数构成两个大小相同的集合,且集合的元素可以两两配对,每一对的gcd大于1.求集合最大是多少.

首先,1和大于$\frac{n}{2}$的质数一定不会被放到集合中.剩下的所有数就是答案.

考虑贪心配对,从大到小枚举质数$p$,然后检查该质数中没有匹配的数,让它们两两配对.如果最后会剩下一个,就余下$2p$.

有$n$个人隶属于$m$个组织,现在告诉你这些人两两之间是否属于同一个组织,求每个人属于组织的情况.给出的每一个信息都有$\frac{1}{S}$的概率是错的.

乱搞.

随便找一个连通块出来,然后统计下两两之间的关系.当一个人与超过三分之一的连通块的人数都有关系时,就认为他们是一个组织的.

式子还是推的有点慢,乱搞的姿势水平也有待提高(?).