题解：P7255 [BalticOI 2012 Day2] 俄罗斯方块

while_0 · 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 的操作见附件。

我的代码在这里