自动搬运

查看原文

来自洛谷，原作者为

	while_0 我是玉瞐

搬运于2025-08-24 22:28:06，当前版本为作者最后更新于2024-11-28 13:57:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很毒瘤的提交答案题。

题目大意：给你一个 $1 \sim 9$ 的序列，每一种数字分别代表一种 $1 \sim 3$ 块的俄罗斯方块。方块不能被旋转，只能硬降（即没有下落到一定高度再左右移动钻缝的操作。

我们称实格为包含方块的方格，空格为不包含方块的方格。

一共五个点，其中：

• 第一个点长度 $1000$，只有横着的二连、三连块。
• 第二个点长度 $5000$，由 $1 \sim 9$ 的循环、$1 \sim 3$ 的循环以及一点点偏随机的块组成。
• 第三个点长度 $20000$，由各种复杂的全清循环以及一些精心构造的非循环块组成。
• 第四个点长度 $50000$，由看上去很随机的块组成。
• 第五个点长度 $100000$，由看上去很随机的块组成。

我的做题顺序：$5\rightarrow 4\rightarrow 2\rightarrow 1\rightarrow 3$

对于测试点 $4$、$5$，数据比较随机，写一个 $dfs\space+$ 估价函数就能通过。具体地，搜 $3$ 步，$3$ 步之后哪个局面最好，就往那个局面走一步。

估价函数包含以下几点：

• 一个空格上方有实格，扣分；
• 有大裂谷，扣分（大尖塔其实还好）；
• 当前地形无法与特定块的下轮廓贴合，扣分。

这样可以通过测试点 $2$、$4$、$5$。

能通过测试点 $2$ 的原因是其中包含了很多 $1$块（即一个点），容错率很高。

对于测试点 $1$，观察到所有方块的高度均为 $1$，我们设计如下的估价函数：

• 一个空格上方有实格，扣分；
• 一个空格左右都是实格或墙壁，扣很多很多分（这一行永远都不能被消除了）；
• 当前地形无法与特定块的下轮廓贴合，扣分。

这样就能通过测试点 $1$。

最后是测试点 $3$。它包含7个全清定式，其中 $5$ 个是可做的。我们称它们为 $loop1\sim loop7$。各个 $loop$ 的操作见附件。

• $loop1$：$675675675\dots6753533$ 思路是一个循环每列恰好两个实格，这样可以无限堆叠。
• $loop2$：$797979\dots7944797979\dots79885421$（重复两遍）这个定式我是手玩的，第一次重复会有一行加一格垃圾，第二次重复会消除。注意它们的形式都是左一右二，第一列一定会缺少材料，用 $4$ 去填。
• $loop3$：很多个 $8$、很多个 $4$，再交替出现，每次 $8$ 串和 $4$ 串的长度不尽相同。思路：用 $4$（即竖三）占据 $2$、$4$、$6$、$8$、$9$ 或 $1$、$3$、$5$、$7$、$9$ 列，达到用 $8$ 插缝的效果。
• $loop4$：$895895895\dots8953533$ 同 $loop1$。
• $loop5$：很多个 $6$、少量 $4$，再交替出现，每次 $6$ 串和 $4$ 串的长度不尽相同。思路：用 $14725836$ 的列顺序循环堆叠，用 $4$ 填两边空余。
• $loop6$、$loop7$：位于数据中间的不可名状之物。毫无规律，且循环块后的散块是为作者做法留下的地形量身定制的，不可做。在阅读作者解法一部分的中间状态后，我勉强花了一整天手玩出了这两个表。

我的代码在这里