====== 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?