专栏文章

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

wwhile_0
P7255题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqyreki
此快照首次捕获于
2025/12/04 12:56
3 个月前
此快照最后确认于
2025/12/04 12:56
3 个月前
查看原文
很毒瘤的提交答案题。
题目大意：给你一个 1∼91 \sim 9 的序列，每一种数字分别代表一种 1∼31 \sim 3 块的俄罗斯方块。方块不能被旋转，只能硬降（即没有下落到一定高度再左右移动钻缝的操作。
我们称实格为包含方块的方格，空格为不包含方块的方格。
一共五个点，其中：
  • 第一个点长度 10001000，只有横着的二连、三连块。
  • 第二个点长度 50005000，由 1∼91 \sim 9 的循环、1∼31 \sim 3 的循环以及一点点偏随机的块组成。
  • 第三个点长度 2000020000，由各种复杂的全清循环以及一些精心构造的非循环块组成。
  • 第四个点长度 5000050000，由看上去很随机的块组成。
  • 第五个点长度 100000100000，由看上去很随机的块组成。
我的做题顺序：5→4→2→1→35\rightarrow 4\rightarrow 2\rightarrow 1\rightarrow 3
对于测试点 44、55，数据比较随机，写一个 dfs +dfs\space+ 估价函数就能通过。具体地，搜 33 步，33 步之后哪个局面最好，就往那个局面走一步。
估价函数包含以下几点：
  • 一个空格上方有实格，扣分；
  • 有大裂谷，扣分（大尖塔其实还好）；
  • 当前地形无法与特定块的下轮廓贴合，扣分。
这样可以通过测试点 22、44、55。
能通过测试点 22 的原因是其中包含了很多 11块（即一个点），容错率很高。
对于测试点 11，观察到所有方块的高度均为 11，我们设计如下的估价函数：
  • 一个空格上方有实格，扣分；
  • 一个空格左右都是实格或墙壁，扣很多很多分（这一行永远都不能被消除了）；
  • 当前地形无法与特定块的下轮廓贴合，扣分。
这样就能通过测试点 11。
最后是测试点 33。它包含7个全清定式，其中 55 个是可做的。我们称它们为 loop1∼loop7loop1\sim loop7。各个 looploop 的操作见附件。
  • loop1loop1：675675675…6753533675675675\dots6753533 思路是一个循环每列恰好两个实格，这样可以无限堆叠。
  • loop2loop2：797979…7944797979…79885421797979\dots7944797979\dots79885421（重复两遍）这个定式我是手玩的，第一次重复会有一行加一格垃圾，第二次重复会消除。注意它们的形式都是左一右二，第一列一定会缺少材料，用 44 去填。
  • loop3loop3：很多个 88、很多个 44，再交替出现，每次 88 串和 44 串的长度不尽相同。思路：用 44（即竖三）占据 22、44、66、88、99 或 11、33、55、77、99 列，达到用 88 插缝的效果。
  • loop4loop4：895895895…8953533895895895\dots8953533 同 loop1loop1。
  • loop5loop5：很多个 66、少量 44，再交替出现，每次 66 串和 44 串的长度不尽相同。思路：用 1472583614725836 的列顺序循环堆叠，用 44 填两边空余。
  • loop6loop6、loop7loop7：位于数据中间的不可名状之物。毫无规律，且循环块后的散块是为作者做法留下的地形量身定制的，不可做。在阅读作者解法一部分的中间状态后，我勉强花了一整天手玩出了这两个表。
我的代码在这里

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...