P8154 「PMOI-5」C 棋盘 题解

· · 题解

「PMOI-5」C 棋盘题解

是出题人题解。

题外话：本篇题解中所有构造的时间复杂度都不超过 O(n)，但是因为出题人太逊，SPJ 是 O(n^2\log n) 的，还带巨大常数，所以只开到了 n\le 10^3。

Subtask 1（10 pts）：

该段分数满足：n\equiv0\pmod{7}。

考虑到样例中已经给出了 n=7 时的构造，于是直接在平面内摆放多个 n=7​ 位移后的解即可。

需要注意的是这些解不仅直线不能有重叠，解和解之间的点也不能连成一条符合条件的直线。

std 的做法是每次画一个 n=7 的解以后将当前 x 坐标向右位移较大值，然后将 x,y 同时向正方向位移 n 单位，再将 n 减 7。可以保证这样做在 n\le 10^3 时不出错。

Subtask 2（20 pts）：

该段分数满足：40\le n\le 400。

将样例中的点 D 和点 M 拿掉以后就形成了一组合法的 n=6 的解。

观察到 Subtask 2 中所有的数都可以表示成 6 和 7 的和，于是拆分成 6 和 7 的和后摆放多个 n=6 和 n=7 的解即可。

Subtask 3（30 pts）：

该段分数满足：1\le n\le 9。留给一些乱搞选手。真的有人乱搞过了这档分么？

$5\le n\le 9$ 时，拿起笔分别画出 $n$ 角星，你会发现刚好满足条件。 赛后 upd：还真有不少人只过了这档分没过其他的。 ~~其实感觉样例给的提示就比较明显了~~ ## Subtask 4（40 pts）： 该段分数无特殊限制。 难道要拿出笔画出 $n(n\le 10^3)$ 角星么？其实大可不必。 将你所得的 $n=5\sim 9$ 的解按照 Subtask 1 的方法拼接起来即可。 std 做法是以 $n=6$ 时的解作为基本图形，然后 $n=7,9,10,11$ 的构造则由 $n=6,8$ 时的构造转变而来。 [spj/std/tester/mkdt/n=5~9的图片构造 地址](https://www.luogu.com.cn/paste/03iq64y2)