自动搬运

查看原文

来自洛谷，原作者为

	Loser_King Just stay where you are; Let your fear subside

搬运于2025-08-24 22:36:26，当前版本为作者最后更新于2022-01-02 21:31:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

「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$。留给一些乱搞选手。真的有人乱搞过了这档分么？

$1\le n\le 4$ 时可证明是无解。

$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的图片构造 地址