算法竞赛中的过程视角与结构视角

发表于 2026-10-14 分类于方法论

前言

笔者将研究 OI 题的视角分成两类：

过程视角：研究动态的过程，与决策 / 行为有关。
- 例子：考虑当前状态下的最优决策、考虑博弈题中某方策略、DP 的转移、构造具体解。
- 优点：直观具体，对于简单的题目能够快速得到题解，也能帮助理解困难的题目。
结构视角：研究静态的结构。
- 例子：刻画解结构、分析上下界、分析产生贡献的量。与某个量有关。
- 优点：通常能得到更强的性质，是解出难题的关键。

对过程与结构的考察往往是交替进行的。下面我们来看看这两种视角的实际应用。

过程视角发挥了作用

Looking at Towers (difficult version)

从过程视角出发，想象自己往左右“看”这一行为的过程，会发现左右端点的视线最终都会落在数列最大值那里，且左边的最大值位置 $\le$ 右边最大值位置。

这就是过程视角的优势：可以直观快速地理解题目约束。

之后就可以根据上面提到的性质做 DP 了。因为不是本文重点，所以不再赘述。

Fair Elevator

首先对题目做一个简单抽象：在数轴上放区间，相交的区间长度要相同。

从过程视角出发，每放上一个区间，由于坐标是连续紧凑的，所以一定会形成一个一个的“块”，块的大小等于区间长度 $\times 2 - 2$。

处理一个一个块拼接的结构，我们会考虑划分 DP。同样地不再赘述。

AB

考虑生成字符串的过程。初始时是 AB，分类讨论：

若 AB 生成 A：
1. 若 AA 生成 A：那么只能让左边全是 A，右边一个 B。
2. 若 AA 生成 B：
  1. 若 BA 生成 A：观察发现只能是多个 A 后面跟着一个 B。直接枚举 B 的数量，插空法即可。
  2. 若 BA 生成 B：发现从 AAB 开始的任意字符串都可生成，考虑归纳法证明。
    1. 最终的串结构一定是 A + s + AB。
    2. 考虑给 s 加入一个 A：直接用 AB 生成 A 即可。
    3. 考虑给 s 加入一个 B：不论 s 以什么结尾，都一定能和 A 生成 B。
    4. 归纳法成立，答案即为 $2^{n-3}$。
若 AB 生成 B：论证是对称的。

上述分析从过程出发，省下了很多讨论量。如果直接从结构入手，可能需要做一个 $2\times2\times2\times2$ 的大讨论。因此过程视角往往是简化问题的关键。

结构视角发挥了作用

Mafia

从过程视角出发，理解游戏如何进行：选出一个监督者，令除它以外的所有人 $-1$，问使得序列全不超过 $0$ 的最小操作次数。

如果沿用过程视角分析，研究在当前状态下做什么决策最优，发现很难构造出一种方案。于是我们转化视角，从结构视角看问题。

设第 $i$ 个人担任了 $x_i$ 次监督者，总共进行了 $T$ 轮，则有

$$
\sum_i x_i=T,\qquad x_i\le T-a_i.
$$

结合两个式子，有

$$
T=\sum_i x_i\le \sum_i (T-a_i)=nT-\sum_i a_i
\Rightarrow (n-1)T\ge \sum_i a_i
\Rightarrow T\ge \left\lceil\frac{\sum_i a_i}{n-1}\right\rceil.
$$

因为 $x_i$ 非负，所以 $T\ge a_i$，也就是 $T\ge a_{\max}$。所以

$$
T=\max\left(a_{\max},\left\lceil\frac{\sum_i a_i}{n-1}\right\rceil\right).
$$

复盘上述分析，我们首先通过研究过程，抽象 / 理解了题目；在发现继续研究过程无果后，转向了对结构的研究。

在这里用到了两个研究结构的常见技巧：

把要研究的量用符号表达；
分析上下界，并证明它是紧的。

廊桥分配

一个比较自然的思路是处理出 $f_i$ 和 $g_i$，分别表示国内 / 国外分配 $i$ 个廊桥能停放的飞机数量。

从过程视角看，我们需要基于当前的廊桥数量与飞机停放情况，对每一架飞机“分配”一个廊桥。（这种对“状态”与“决策”的考察，是经典的过程视角。）这是一个经典的区间贪心问题，对于每一个 $i$ 都模拟一遍分配过程即可。

但是这样的时间复杂度是不优的。尝试跳出动态的分配过程，从结构视角看问题。

直接考察每架飞机会停在几号廊桥，发现这可以直接预处理出来。由于“先到先得”的限制，方案的结构实际上是确定的，不受分配过程的影响。于是这题就结束了。

复盘上述分析，我们首先从过程出发，找到了最优的分配策略；然后再从结构出发，发现结构是固定的，只需做一次分配即可。

Narrow Passage

对于操作题，第一步要分析操作的影响，将影响聚焦到具体的量上：

正常移动：将排名为 $p$ 的点坐标 $\pm1$。
交换移动：将排名 $p\pm1$，点坐标不变。

从过程视角出发，会发现由于“交换位置”这一特殊操作的存在，很难直接构造出一种最优方案。

于是我们跳出动态的“移动过程”，转而分析静态的结构，考察答案的组成。一个自然的想法是根据操作类型划分。

先来考察正常移动的次数。对于每个点，用总位移减去交换移动的位移，就能得到正常移动的次数。所以这部分贡献为

$$
\sum_i \left|(t_i-s_i)-(rt_i-rs_i)\right|.
$$

其中 $rs_i$ 表示初始排名，$rt_i$ 表示移动后的排名，可以通过排名的变化量反映交换移动的位移。

再来考察交换移动的次数。需要注意的是，上文提到 $rt_i-rs_i$ 是交换移动的位移，而不是交换移动的次数，这两者是不同的。

考察 $i$ 会和哪些 $j$ 发生交换：

$$
\begin{cases}
s_j<s_i \ \land\ t_j>t_i, \\
s_j>s_i \ \land\ t_j<t_i.
\end{cases}
$$

只需要统计其中一类即可；如果两类都统计的话，每一组 $(i,j)$ 恰好被记 $2$ 次。我们选第一类统计。

对于这种二维偏序的问题，我们通常在坐标轴上考虑。将 $s$ 当成 $x$ 轴，$t$ 当成 $y$ 轴，则满足条件的点数就是每个点左上方的点数。这个可以直接树状数组做。

如果你的注意力足够好，会发现这本质就是将点按 $s$ 排序后，计算 $t$ 数组的逆序对个数。这是因为逆序对本质上就是二维偏序。

复盘上述分析，我们首先分析操作会影响哪些量，然后尝试用过程视角构造最优解，失败后转而使用结构视角分析答案如何产生，分开计数。

这里用到的结构视角的技巧有：

在坐标轴上考虑二维偏序问题；
分析答案组成。

总结

过程视角可以让我们直观快速地把握一些性质，它们往往是解题的基础。结构视角可以让我们得到更强的性质和理解，是解题的关键。通常我们都会从过程视角出发，碰壁了再考虑结构视角。

本文用到的技巧汇总

通用技巧：

分类讨论；
猜测结论然后证明；
操作题考虑操作对具体量的影响；
将二维偏序问题放到坐标轴上考虑；
钦定一些量。

研究结构的一些常见技巧：

用符号表达操作量 / 研究对象；
分析上下界，再证明它是紧的；
刻画最优解结构；
分析答案组成，拆贡献。

闲话

呀，虽然笔者在上文将“过程视角”和“结构视角”写得那么泾渭分明，但实际上做题过程中根本不会清晰地意识到自己处于哪种视角。

上文提到的两种视角只是笔者对自己思维过程的粗略整理，实际做题过程中并不会这么完美，它们只能作为一个思维的起点。解出题目是需要题量的积累的，不会因为掌握了两种视角就有很大提升，就比如上文中提到的那么多技巧，都需要一次一次地失败才能提炼出来。

如果把解题比作筑楼，那么方法论只是蓝图和施工方向；做题的经验，对技巧的整理才是真正用到的建筑材料。

在我看来，OI 是一门很灵活的学问，没有什么机械的方法论能囊括它所有题目的解法，但其中有一些大方向是可以确定的。就比如，在思考题目的起步阶段，要从过程视角出发，调用自己的直觉，大刀阔斧地做简化，这一阶段重要的是“感觉”；然后再用结构视角分析问题，此时的重心就要转移到“严谨”上了。

曾经读到过一本书，书里讲述了人类直觉的强大，我如今是认同的。需要相信的是，直觉的背后是经验的累积，而不是智商或天赋。还请继续保持对自己的信心，加油吧！