[技巧] 当你「使用影跃」就可以解决你「两年的梦魇」？！

· · 算法·理论

::::info[防伪标识 / 一点闲话]{open}

（小作文，可跳过）

起这个标题的原因是，今天是我曾经天天看的五人组解散一周年，也是我曾经最喜欢的 MC up 主「黑猫大少爷」塌房一周年，也是我曾经第二喜欢的 MC up 主「大炒面制造者 Cen」被开团一周年。

同时，本文讲述的「影跃技巧」对应的例题有一道 P1173。相信许多人萌新时都被同学恶搞过以至于提交的该题的题解，这道题也顺理成章地成为了许多萌新「两年的梦魇」（没错标题是双关语）。

随着时间流逝，五人组的事情逐渐无人问津，原班人马各自找到了新的伙伴；学习信息学竞赛的大家也在逐渐提升水平，“机房惨案”一类的恶搞不再发生。

笔者认为，对于过去不算高兴的种种事情，即使它们当时给我们留下了创伤，但是我们总有一天会走出来，微笑着面对它们。因此笔者打算向大家普及 P1173 的真正做法以及这类题目的思维技巧，希望这篇文章可以帮助更多人重新认识这道抄题解重灾区，也希望更多人在成长过程中可以重新面对属于自己的「梦魇」，破除自身的心魔。

谨以此文，与广大 OIer 共勉。

::::

::::warning[注意]{open}

本文旨在介绍 Trick，因此并没有对于每个例题都给出其完整的做法。建议结合各题的题解食用，以更好地理解该思维方式与具体算法的有机结合。

::::

影跃技巧，又称桑格莉娅 Trick，是笔者“发明”的一类处理网格图问题时的思考方式。并非特定算法。

笔者一开始想出这个技巧时觉得其可能仅在某些题目中有应用前景，但是后来又见到了许许多多需要用这种方式思考的题目，故给这个 Trick 命了个名字总结一下，并写此文进行推广。

什么是影跃 Trick？

具体来说，当我们在处理网格图（即英文“grid”或者“cell”一类的题目）时，如果整个图较大而非平凡的地方（可能是周围存在障碍、边界等情况，又或者是可达的部分等等）不多，我们可以考虑仅渲染出这些非平凡的部分，然后在这些部分上模拟暴力算法求得答案。

灵感来源（可以跳过）

::::warning[注意]{open} 下面这个“展示”是存粹 OI 无关内容，请不要在学校机房观看，否则可能被误认为摸鱼。但是笔者很推荐大家看一看，知道了这个角色的设计基本上就能完全通晓这个 Trick 的原理了。 ::::

笔者在做一道题时想到了某个角色（见下面视频）的技能“影跃”，然后发现这个技能的核心逻辑可以用来解这道题。

::::info[展示] ::::

可以发现，这个仅“渲染”建模边缘的方法极大地减少了信息量，但是并不影响图的可达性等性质。

零阶：基础应用

P5983 [PA 2019] Osady i warownie 2

这道题是这个 Trick 的来源，笔者身边应该有很多同学都通过模拟赛知道了这道题。

我们从左上角走到右下角的方式有很多，如何刻画一个格子是否是关键的？

可以想到，关键的格子一定是位于某种“窄道”，只要我们能刻画哪些位置等价于一个宽度为一的窄道，就能维护关键的格子了。

渲染建模边缘的方法启发我们，我们可以维护最靠上 / 靠下的两条路径，如果这两条路径有交，说明相交的位置是关键的。我们会发现这与游戏中的情况如出一辙。

动态维护这两条路径相比这个 trick 本身比较平凡，我们可以略过。

QOJ 833. Cells Blocking

这是一道集训队作业题，题目本身挺难的，但是存在用影跃 Trick 分析的做法（同上一题），如果真的想用这个做法通过此题，可以先去看一看 AT_agc028_f [AGC028F] Reachable Cells。

一阶：渲染更多区域

如果你看了上面的视频，你会发现桑格莉娅解锁一阶技能之后，为了方便行动可以人为地创造一片被渲染的区域。我们是否也可以学学网易的这个设计，给我们的模型上加一些“辅助”点方便讨论呢？

其实，影跃技巧的实质是删除某些不影响模型性质的信息。因此我们没有必要只拘泥于“保留贴边的点”，对于其他部分只要复杂度正确，你都可以为了方便讨论而保留它们。

P1173 [NOI2016] 网格

希望这部分能帮到一些萌新时期被 jc 还没有补这题的 OIer。

如果我们考虑零阶影跃 Trick，对所有贴着蛐蛐（八联通）的点建图，你会发现图可能是不连通的，相比原图缺少了一些信息。

那么我们何不像上面视频中的一阶技能一样，再多刻画一些点来“辅助”建图呢？

我们发现，我们要让新图的信息和原图相等，就需要处理一些两个连通块“隔空”相连的情况，如果这些隔空相连的边都是直来直去的，那么我们建图就很方便了。因此我们考虑 这篇题解 中的建图方式，通过在网格边缘的某些地方增加一些“中转”点，把一条拐弯相连的边拆成了两条直着连的边。

CF2041G Grid Game

是上一道题的加强版。

我们改进上一题的做法：不难想到可以把所有点拆成一个个竖着的长条。为了方便计数，我们显然希望每个长条只能同为割点或平凡的点。

因此我们可以对于两个一上一下的格子 (x, y), (x + 1, y)，如果以 (x, y) 为中心的九宫格和以 (x + 1, y) 为中心的九宫格完全相同的话，就钦定它们在同一个长条。不难证明这样做的正确性。

于是我们假设有 n 个障碍，对于宽度 \leq O(n) 的情况，我们已经找到了建图方法。不难把宽度更大的情况归约到前者。

这篇题解 指出，长条之间不需要连边。这样我们暴力建边后跑 tarjan 便做出了这道难题。

二阶：思想运用

影跃不只是一种 Trick，更是一种思考方式。当一道题提供的模型的信息量很大时，我们只聚焦其中“最有含金量”的部分，往往能起到出奇制胜的效果。

P14952 过河卒

这题的做法很没意思，多次随机调整即可。有意思的地方在于证明。

下面给出我的感性证明（摘自我的题解）：

首先来说明这道题不能拆进制位：计算得知 58 \choose 29 约为 3 \times 10^{16}，而这题的限制是 10^{16}，就算能找到一种方法构造斐波那契或者 k 进制等指数增长的数列，把它们导出到一条路径上也会有至少 2 \times 10^{16} 的损耗。（56 \choose 28 小于 10^{16}，则一个 29 \times 29 的棋盘已经非法）

接下来说明随机化算法本体。尝试重复以下步骤知道找到答案：

最后感性说明随机化的正确性。拿我自己的代码举例子，加上每次输出方案数、选出的位置和减去的方案数这一调试代码后标准错误流输出如下：

29865688825486580 29 29 15208068435764600
14657620389721980 5 5 4312998318967380
10344622070754600 8 2 339317801864496
10005304268890104 11 1 5289940382551
10000014328507553 23 5 14055035040
10000000273472513 3 24 230323800
10000000043148713 24 3 42682724
10000000000465989 1 24 380742
10000000000085247 2 27 84709
10000000000000538 28 2 336
10000000000000202 29 3 156
10000000000000046 3 30 46

以上是 L = 10^{16} 的一次随机。随机化正确性的道理就藏在最后一行上面。我们用这个代码多跑几次，会发现最后一次减掉的方案数（上面那个 46 的位置）通常不大于 999，而多数情况下是个两位数，甚至会有个位数的情况出现。

这是因为，当一开始只有不到 5 个 0 时，把边界线上的 1 改为 0 对答案的影响可以视作 {n \choose 1} 或者 {n \choose 2} 量级（类比全 1 棋盘即可理解），而由于最后几步之前，方案数快速逼近 L，修改的都是对答案影响很大的位置，并不影响上述位置对方案数的影响力。

因此，最后一步可以视作方案数随机减一个小数字，那么假设数字的分布多数在 [1, V] 之间，则随机的正确性近似视作 \frac{1}{V}。上文已经说明 V 一般在 n 到 n^2 之间（实际情况表现更好），所以随机的正确性可得。

可见，看似不靠谱的随机化有着不错的正确性。这就是因为网格的“边缘”相比其中心的重要性过小，在本题中是“不平凡”的。

P4858 [PA 2013] Karty

与前面相同，我们发现对于一个给定的尺寸，越靠近边缘的点，其不可被覆盖的“可能性”越大。

于是我们产生一个大胆的猜测：是否只检验与边缘相邻的点就可以了呢？尝试写一个暴力算法，事实告诉我们这个结论是正确的！

因此，我们可以对四个方向考虑四次，每次仅考虑某一边贴着障碍 / 边缘的点对尺寸的要求是什么。这可以通过建笛卡尔树并做一个类似树形 DP 的信息合并过程得到。