专栏文章

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

FFelix72
算法·理论参与者 44已保存评论 52

文章操作

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

当前评论
52 条
当前快照
1 份
快照标识符
@mlia3fug
此快照首次捕获于
2026/02/12 01:03
上周
此快照最后确认于
2026/02/19 01:13
11 小时前
查看原文
防伪标识 / 一点闲话
（小作文，可跳过）
起这个标题的原因是，今天是我曾经天天看的五人组解散一周年，也是我曾经最喜欢的 MC up 主「黑猫大少爷」塌房一周年，也是我曾经第二喜欢的 MC up 主「大炒面制造者 Cen」被开团一周年。
同时，本文讲述的「影跃技巧」对应的例题有一道 P1173。相信许多人萌新时都被同学恶搞过以至于提交的该题的题解，这道题也顺理成章地成为了许多萌新「两年的梦魇」（没错标题是双关语）。
随着时间流逝，五人组的事情逐渐无人问津，原班人马各自找到了新的伙伴；学习信息学竞赛的大家也在逐渐提升水平，“机房惨案”一类的恶搞不再发生。
笔者认为，对于过去不算高兴的种种事情，即使它们当时给我们留下了创伤，但是我们总有一天会走出来，微笑着面对它们。因此笔者打算向大家普及 P1173 的真正做法以及这类题目的思维技巧，希望这篇文章可以帮助更多人重新认识这道抄题解重灾区，也希望更多人在成长过程中可以重新面对属于自己的「梦魇」，破除自身的心魔。
谨以此文，与广大 OIer 共勉。
注意
本文旨在介绍 Trick，因此并没有对于每个例题都给出其完整的做法。建议结合各题的题解食用，以更好地理解该思维方式与具体算法的有机结合。
影跃技巧，又称桑格莉娅 Trick，是笔者“发明”的一类处理网格图问题时的思考方式。并非特定算法。
笔者一开始想出这个技巧时觉得其可能仅在某些题目中有应用前景，但是后来又见到了许许多多需要用这种方式思考的题目，故给这个 Trick 命了个名字总结一下，并写此文进行推广。

什么是影跃 Trick？

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

灵感来源（可以跳过）

注意
下面这个“展示”是存粹 OI 无关内容，请不要在学校机房观看，否则可能被误认为摸鱼。但是笔者很推荐大家看一看，知道了这个角色的设计基本上就能完全通晓这个 Trick 的原理了。
笔者在做一道题时想到了某个角色（见下面视频）的技能“影跃”，然后发现这个技能的核心逻辑可以用来解这道题。
展示
可以发现，这个仅“渲染”建模边缘的方法极大地减少了信息量，但是并不影响图的可达性等性质。

零阶：基础应用

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)，如果以 (x,y)(x, y) 为中心的九宫格和以 (x+1,y)(x + 1, y) 为中心的九宫格完全相同的话，就钦定它们在同一个长条。不难证明这样做的正确性。
于是我们假设有 nn 个障碍，对于宽度 ≤O(n)\leq O(n) 的情况，我们已经找到了建图方法。不难把宽度更大的情况归约到前者。
这篇题解 指出，长条之间不需要连边。这样我们暴力建边后跑 tarjan 便做出了这道难题。

二阶：思想运用

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

P14952 过河卒

这题的做法很没意思，多次随机调整即可。有意思的地方在于证明。
下面给出我的感性证明（摘自我的题解）：
首先来说明这道题不能拆进制位：计算得知 (5829)58 \choose 29 约为 3×10163 \times 10^{16}，而这题的限制是 101610^{16}，就算能找到一种方法构造斐波那契或者 kk 进制等指数增长的数列，把它们导出到一条路径上也会有至少 2×10162 \times 10^{16} 的损耗。（(5628)56 \choose 28 小于 101610^{16}，则一个 29×2929 \times 29 的棋盘已经非法）
接下来说明随机化算法本体。尝试重复以下步骤知道找到答案：
  • 构造一个 n=30n = 30 且全都是 11 的棋盘，并随机把 [1,5][1, 5] 个数字变为 00；
  • 重复找出变为 00 不会使方案数小于 LL 中方案数最接近 LL 的位置，并把该位置变为 00；
  • 无法找出这类位置时，判定方案数是否恰好等于 LL。
最后感性说明随机化的正确性。拿我自己的代码举例子，加上每次输出方案数、选出的位置和减去的方案数这一调试代码后标准错误流输出如下：
TXT
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=1016L = 10^{16} 的一次随机。随机化正确性的道理就藏在最后一行上面。我们用这个代码多跑几次，会发现最后一次减掉的方案数（上面那个 4646 的位置）通常不大于 999999，而多数情况下是个两位数，甚至会有个位数的情况出现。
这是因为，当一开始只有不到 55 个 00 时，把边界线上的 11 改为 00 对答案的影响可以视作 (n1){n \choose 1} 或者 (n2){n \choose 2} 量级（类比全 11 棋盘即可理解），而由于最后几步之前，方案数快速逼近 LL，修改的都是对答案影响很大的位置，并不影响上述位置对方案数的影响力。
因此，最后一步可以视作方案数随机减一个小数字，那么假设数字的分布多数在 [1,V][1, V] 之间，则随机的正确性近似视作 1V\frac{1}{V}。上文已经说明 VV 一般在 nn 到 n2n^2 之间（实际情况表现更好），所以随机的正确性可得。
可见，看似不靠谱的随机化有着不错的正确性。这就是因为网格的“边缘”相比其中心的重要性过小，在本题中是“不平凡”的。

P4858 [PA 2013] Karty

与前面相同，我们发现对于一个给定的尺寸，越靠近边缘的点，其不可被覆盖的“可能性”越大。
于是我们产生一个大胆的猜测：是否只检验与边缘相邻的点就可以了呢？尝试写一个暴力算法，事实告诉我们这个结论是正确的！
因此，我们可以对四个方向考虑四次，每次仅考虑某一边贴着障碍 / 边缘的点对尺寸的要求是什么。这可以通过建笛卡尔树并做一个类似树形 DP 的信息合并过程得到。

评论

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

正在加载评论...