[NOI 2012] 三重镇题解

Into_qwq · 2023-04-24 16:33:24 · 题解

[NOI 2012] 三重镇题解

由三个人共同完成，@liuyuzhuo，@HBWH_zzz，@Into_qwq。

用来手玩的代码，输入每个测试点对应的 .in 文件即可食用，操作格式与题目中相同，并增添了 REJECT 操作（撤销上次放置操作，注意无法撤销星星和炸弹）。

测试点 1：

3 3
0 0
.1.
.11
...
30

首先初始局面有三个 1，可以多放一个让他们合成一个 2。

然后采取策略：尽量让相同的数相邻，且大的放边角。

建筑序列很小，大概手玩一下就可以了。

注意这个点合满才能拿到 10 分。

测试点 2：

只有一排三个点，说明显然只有一种升级建筑的途径，需要巧妙地利用星星和炸弹。

其实可以直接 dp，记录状态：当前操作到序列的第几个，还有多少个星星，多少个炸弹，当前局面为啥的最大得分。

状态数：80\times40\times60\times10^3\approx2\times10^8。

这里写了个记忆化搜索。

code

测试点 3：

和测试点 2 一样，就是范围更大。

采用手动 wqs 二分的方法，不记星星这维（因为程序很能把握住炸弹的使用），然后再看这个最优解用的星星数，通过星星数二分给星星附的权值。

code

但是这样要么多 3 个星星，要么少 1 个星星。

但是我们还有第二个点的记忆化搜索！

让 wqs 跑出多 3 个星星的解，然后选取较后一段来跑记忆化，调整最优解。

最终把两个答案拼起来，得到了结果。

测试点 4：

1 100
0 0
....................................................................................................
360

观察可知：序列全是 1。

可以发现，三个 1 拼成一个 2，这个 2 可以在这三个 1 的最左边或最右边，我们可以通过放连续三个最左或最右的 2 来拼出一个 3，如图：

111
 111
  111

容易发现，这样会花费横向 5 个格子的代价在最中间生成一个 3，我们就可以每隔两个格子生成一个 3，然后把剩下的位置填满 1，最后的位置填不了 3，可以填 2。

最后就是这样的形式：

113113...1131122

code

测试点 5：

20 20
0 0
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
11000

这是对测试点 4 进行了升维。

我们定义生成一个数字消耗的格子为合成它所放过的格子，一个数字如果最后合成在所有消耗的格子中角落里的格子则我们称它能在角上合成，如果最后合成在所有消耗的格子中边上的格子则我们称它能在边上合成。

比如 111 合成一个 2，我们称左边的 1 和右边的 1 为角落里的格子，他们三个都是边上的格子。

容易发现，3 可以在角上合成，但 4 就只能在边上合成（连续三个都在角上的 3），因此 5 就不能在边上合成（因为 4 不能在角落合成），因此二维中最多合成出 5，不可能合成出 6。

如：

111
...
...

2..
111
...

2..
2..
111

...
...
3..

这样合成一个 3 相当于消耗了一个 3\times3 矩形内的所有格子，并且 3 能在矩形的角落（左下角）合成。

由于二维相对一维可能性太多，因此需要写一个程序来合成 5，然后贪心地先尽量放 5，再 4，…… 直到 1。

code

测试点 6：

1 20
2383 0
....................
0

该测试点一维，且只有星星。

由于只用考虑一维，我们设 \text{op}(num,x) 表示要在第 x 个点合成一个为 num 的建筑的操作，\text{star}(x) 表示在 x 的位置放一个星星，那么 \text{op}(num,x) = \text{op}(num-1,x+2),\text{op}(num-1,x+1),\text{star}(x)，\text{op}(1,x) = \text{star}(x)。

递归即可。

code

测试点 7：

6 6
0 0
......
......
......
......
......
......
1231

经过计算发现第 7 个点的最大答案就是把所有数合并成一个 9。由于正向合并十分复杂，所以我们考虑最后有一个 9 时如何将其拆分成题目给定的序列。

由于出题人十分善良，所有的拆分都是连续的（即对于每个数都存在一种拆分方案对应了原序列的 [l,r] 区间）。所以我们可以搜索一下，设 \text{trybuild}(l,r,x,y,sum) 表示现在如果有位于 (x,y) 的数 \log_3(sum)，是否能拆成原序列 [l,r] 区间。那么找到三等分点就可以通过枚举放数的方案递归下去寻找，实测跑得飞快。

code

测试点 8：

8 8
0 0
........
........
........
........
........
........
........
........
7948

该测试点从测试点 7 的合成一个 9 变成了合成 4 个 9，做法同理。

测试点 9：

6 6
0 0
112..1
....12
.21...
2....1
1....1
......
3000

这个点没有星星和炸弹，但是序列没有什么特殊性质。

对于测试点 7，你会发现有一个跑得比较优秀的随机化——如果连续 3 次操作没有合并则直接剪枝，这样可以获得 9 分的好成绩。我们保留了这个程序的骨架部分（即爆搜），并把所有剪枝删掉，改成一个随机撒点，就过掉了第九个点。

code

测试点 10：

6 6
200 200
......
1....1
.11222
11.122
22.2..
.2....
30000

该测试点没有任何特殊性质。

该测试点只需要在测试点 9 的基础上把星星和炸弹加上，再加上一个比较智慧的剪枝（每 40 次操作左右使用一次炸弹和星星）就可以获得满分。

code

用时接近一个月，终于拿下了这道题。

可喜可贺。

[NOI 2012] 三重镇 题解