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

博弈真好玩。

题意：在基环树上有若干终点，A 先手，A B 轮流移动，A 不能移动到 B 经过过的点上，当 A 到达若干个终点之一时即可获胜。

题解（伪）：如果存在一个终点离 A 更近，那么 A 稳赢了。否则 A 想要赢，必须借助那个环（因为在某些情况下，B 会选择等待从而浪费了优势）。如果 A 先到达环那么就凉了，因为 B 肯定不会等而且离终点更近。如果 B 先到达环，它的目标是对与 离 A 近的那两个环上的终点都比 A 近，或者直接把 A 进入环的入口封住，或者把终点封到只剩环的一侧有终点且离自己更近。

Problem I

Solved by zerol. 01:51 (+)

题意：在平面上有一些不重叠的整点。一次十字斩可以砍掉一行一列的点，问最多能砍掉多少点以及在砍掉点最多的情况下被砍掉的不同点集个数。

题解：ｙ 用 set 维护，x 扫一遍求出最多砍掉的点和不同的十字斩的中心。在答案是 2 或 n 的时候，点集个数和十字斩中心数不同，进行特判。

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，其实根本不需要。