====== 2020牛客暑期多校第四场 ======

====== 比赛地址 ======

[[https://ac.nowcoder.com/acm/contest/5669|牛客OJ]]

Pro: 3/4/10

Rank: 117/1172

====== [B] Basic Gcd Problem ======

===== 题意&题解 =====

签到题

====== [F] Finding the Order ======

===== 题意&题解 =====

签到题


====== [G] Harder Gcd Problem ======

===== 题意 =====

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

===== 题解 =====

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

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

====== [I] Investigating Legions ======

===== 题意 =====

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

===== 题解 =====

乱搞.

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


====== 总结 ======

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