Warning: session_start(): open(/tmp/sess_d2e904ab3e13df3828f9cfca486c8295, 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/d/de2edb2fcb553ea79b79c722a4e13dbc.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/5674#question|牛客OJ]]
Pro: 5/5/12
Rank: 161/975
====== [A] Groundhog and 2-Power Representation ======
===== 题意&题解 =====
签到题
Python大法好
====== [E] Groundhog Chasing Death ======
===== 题意 =====
求$\Pi_{i=a}^{b}\Pi_{j=c}^{d}Gcd(x^{i},y^{j})$
===== 题解 =====
先分解质因子,然后计算每个质因子的贡献.如果某个质因子是两个数共有的,就计算一下其指数在哪个范围的时候,gcd的结果取第一个数的因子,以及在哪个范围内取第二个数的因子,累计起来即可.需要卡一下常数.
====== [F] Groundhog Looking Dowdy ======
===== 题意 =====
有$n$个集合,每个集合中有一些数.现在要从每个集合中取出一个数,然后再从这些数中取出$m$个,使得这些数的极值差最小.求这个最小值.
===== 题解 =====
二分答案.
把所有数从小到大排序,二分极值差,然后用一个滑动窗口一样的东西遍历排好序的序列,如果在某个时刻窗口中的数来自不同的至少$m$个集合,就认为该答案合法.
====== [I] The Crime-solving Plan of Groundhog ======
===== 题意 =====
给出$n$个数,要求把它们拼成两个数,使得这两个数的积最小.
===== 题解 =====
贪心.第一个数是一个一位数,为给出的数中最小的数.剩下的数按照从小到大的次序排成第二个数.注意不要带前导零.
====== [K] The Flee Plan of Groundhog ======
===== 题意 =====
有两个人在一棵树上玩追逐战,追人的那个速度是2个节点每秒,被追的那个是1个节点每秒.假如两个人都采用最优策略,求被追的人最晚会在什么时候被抓住.
===== 题解 =====
以追人的位置为根建树.显然,被追的人的逃跑路线一定是先从当前位置沿父节点走到某个节点上,然后一直走到该节点最深的儿子的位置.所以预处理下每个节点最深的儿子有多深,然后从被追的人的位置往上枚举即可.
====== 总结 ======
解题的技巧性还是有待提升,比如B题的策略和国王游戏就比较像,J题0转-1想到了,离化成前缀和模型差了一点点.接下来应该多刷点Atcoder?