Warning: session_start(): open(/tmp/sess_2045e188b7b79687ca370c5e55151614, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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}$的概率是错的.
===== 题解 =====
乱搞.
随便找一个连通块出来,然后统计下两两之间的关系.当一个人与超过三分之一的连通块的人数都有关系时,就认为他们是一个组织的.
====== 总结 ======
式子还是推的有点慢,乱搞的姿势水平也有待提高(?).