=====比赛信息===== * **日期：2020.8.8** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5674?&headNav=www#rank|传送门]] * **做题情况：lxh(K)，tyx(AE)，gyp(FIJ)** =====题解===== ====A - Groundhog and 2-Power Representation==== ===solved by tyx=== ===题意=== 给出一个正整数的二进制表示，其中只含有加号，括号和1，2，例如$137=2(2(2)+2+2(0))+2(2+2(0))+2(0)$，问这个数是多少 ===数据范围=== 答案在$[10,10^{180}]$范围内 ===题解=== 直接模拟即可，每次经过括号就换一个层数，除了最外层每层记录当前的值，最外层套一个高精度，或者直接用python ====B - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====C - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====D - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====E - Groundhog Chasing Death==== ===solved by tyx=== ===题意=== 给出$a,b,c,d,x,y$，求$\prod_{i=a}^b \prod_{j=c}^d \gcd(x^i,y^j) \mod 998244353$ ===数据范围=== $0 \le a \le b \le 3 \times 10^6$，$0 \le c \le d \le 3 \times 10^6$，$0 < x,y \le 10^9$ ===题解=== 先把$x,y$质因数分解，这里只需要分解小于等于$\sqrt{x}$和$\sqrt{y}$的，如果最后还剩下那个质因数一样再单独讨论，然后每个质因数的幂次可以预处理出来，我们对于确定的$i(a \le i \le b)$，可以知道某一个质因数的幂次，然后根据等差数列求和公式可以直接算出所有的$j \in [c,d]$时最大公约数的这个质因子需要算多少幂次，注意算出总幂次后再快速幂，否则复杂度会多一个log ====F - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====G - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====H - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====I - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====J - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====K - The Flee Plan of Groundhog==== ===solved by lxh=== ===题意=== 在一棵树上，一个每秒走一条边的人，从 $1$ 点开始往 $n$ 点先走 $t$ 秒，之后第二个人开始从 $n$ 点以两条边每秒的速度开始追它，问最晚几秒被追到。 ===数据范围=== $ 1 \le n \le 1e5 $ ps:每秒钟开始可以认为是第一个人先走。 ===题解=== 首先，我们不难通过朴素爬树处理出第一个人的初始位置。 之后，我们不难发现，第一个人不想被追到，只需要到某点的时间小于第二个人，于是我们做两遍最短路统计答案即可。 =====Replay===== 第一小时：三个人发现A题是签到题，tyx开始写A，gyp开始写I，lxh开始想K，gyp通过I后开始想F，tyx通过A 第二小时：lxh通过K，tyx开始想E，lxh开始想J，tyx的E超时，gyp通过F 第三小时：gyp帮tyx发现了E的问题，优化后通过E，然gyp开始想J，lxh和tyx开始想L 第四小时：lxh和tyx发现L好像可以做，tyx开始码，码完却发现样例无法通过，出题人发了解释公告后发现读错了题 第五小时：gyp通过了J，lxh和tyx最后没能想出L的正确做法 =====总结===== * 一定要确保题目的意思理解正确