CCPC-Final 2018
Replay
ultmaster:
- 两小时就结束了。
Problem A
Solved by zerol. 00:14 (+)
Problem B
Solved by kblack. 01:31 (+)
题意:骑士站边,贡献不同,有些其实合不拢,求最大值与最小值差的最小值。
题解:先并查集求出所有联通块的站边方案,然后二分差值,把所有骑士分身两边后排序,滑动窗口划过去,判断所有联通块是否有机会全部满足。
Problem D
Unsolved. (-3)
ultmaster: 代码相当宏伟。
kblack: 不甘心!ciya.gif
Problem G
Solved by ultmaster. 00:36 (+)
题意:求 $n \times m$ 的棋盘上,选两个长方形,使得第一个长方形完全包含于第二个长方形之中,边界不能重合,的方案数。
题解:在一维上考虑,方案数是 $\binom{n}{4} + \binom{n}{3}$。两维的问题分开算乘一乘就好。
Problem H
博弈真好玩。
Problem I
Solved by zerol. 01:51 (+)
Problem K
Solved by kblack. 00:29 (+1)
题意:破解 RSA,离散数学期中考试题。
题解:暴力破出 $n=pq$,求个幂,指数是 $2^{30}+3$ 对 $\phi(n) = (p-1)(q-1)$ 的逆元。
Problem L
Solved by ultmaster. 00:55 (+)
题意:把一个数拆成六个素数的和。
题解:同拆成两个、拆成三个的做法。小的情况暴算,大的话分出 2 2 2 2 或 2 2 2 3 来使得剩下一个不小于 4 的偶数。然后利用哥德巴赫猜想,枚举小的那个质数,暴力判断大的那个是否是质数就可以了。比赛中为了稳健写了 Miller-Rabin,其实根本不需要。