P9622 [ICPC2020 Nanjing R] Ah, It's Yesterday Once More 题解

· · 题解

路径越曲折，空格越多，那么这些袋鼠就越不可能走到同一个格子上。这很容易看出，因为路径曲折说明（第一次）所有袋鼠一起移动时有大约一半原地不动，袋鼠多就说明要实现让更多的袋鼠走到一个格子上，就更难让随机程序通过。

所以尝试构建一个路线曲折、空格尽可能多的地图。

首先先搞一个全是墙的地图，接着将左上角填成 1。在一个 4\times4 的小方格中，L 形是空格最多的，应优先使用。所以在左上角摆几个 L 形。接着继续向外延伸，延伸的过程中时刻注意不要出现环，且路径尽可能曲折即可。接下来就凭直觉搞就好了。尽量不要把多个 0 连在一起，尽量不要把多个 1 连在一条直线上。

如果不是程序生成的，那么提交上去时未免可能会有一些 bug，比如所有空洞连起来不是一棵树，出现了循环。下面是判断循环的一种方法。

假如有 0 的联通块没有接到最外面，则它周围一圈就是一个循环，要将其打断。

为了不伤眼睛，有一种办法是在 Excel 里面先用给单元格涂色的方法搞好，接着再把颜色转换成 0 或 1。全选复制之后记得把 Tab 删掉。

按照上面的方法硬构造比较难把 hack 成功率凑到 25\%。这里提供一个符合条件的构造方法，直接搞一个像下图一样从左上折到右下又折回左上的图。

上图是一个 10\times10 的示例，但是为了满足题目要求，数据规模要扩大到 20\times20 才行。

一个符合要求的地图如下：

PHP AC 代码：

20 20
11101111101111101111
10110010110010110010
11011011011011011011
01101101101101101101
10110110110110110111
10011011011011011001
11101101101101101101
10110110110110110110
11011011011011011011
01101101101101101101
10110110110110110111
10011011011011011001
11101101101101101101
10110110110110110110
11011011011011011011
01101101101101101101
10110110110110110111
10011011011011011010
11101001101001101001
10111110111110111111

AC 记录：https://www.luogu.com.cn/record/137495731。