前夜

突击了一下树剖、扫描线和斜率优化，把各种各样的模板打了一遍，学了一下对拍。

准备了一盒薄荷糖，准考证和身份证。和宝高学长约好了明天面基，考完试之后一起去附近玩。

实话说，已经紧张到胃里翻江倒海了。

该做的准备都做好了，目前来看，只要正常发挥，切掉 T2 不是问题。T3 碰运气，大概十分之一的概率能出，应该能打到一个不错的部分分，T4 随缘了。只要不考数论就行，一点也没有复习（

这一把能打到逼近 300 就能去 WC 了，也就是把 T1 T2 切掉，并且把 T3 T4 的暴力打满。这是最好的结局，要对自己有信心。

稍微差一点的结局，T2 刚好考数论 / 数数或是由于不可抗力没有切掉，但是把 T1 切掉了，并且把 T2 T3 T4 的暴力打满，那 S 一等也是随便拿，并且还能再停课一个月打 NOIP 玩（

再次的结局就有点过分了，T1 切不出来那有点离谱，感觉不用做讨论。

感觉拥有光明的未来啊。今年省选之前应该能做到稳切蓝？算法都学的差不多了，思维还差一点，码力差的有点大。

只要发挥好，WC 不是问题啊。注意多放空，红温了就上个厕所，卡题了就跳题，总之要相信自己，我写不出来的题目大部分人也不会做出来的。

如果，我说万一，题目特别特别难，那也一定要把暴力打满。

写题的时候想清楚再写，如果觉得自己想出来了，不要立刻动手写，千万千万要看看自己的思路是不是错误的。

发现自己的思路假了也不要紧张，立马跳题，不要在一道题目上卡 30 分钟还没有进展，这个时间够你想一个 20 pts 的暴力了。不要被压力裹挟大脑，你不差那点时间。

虽然现在说这些完全是在宣泄压力的，对考试没啥帮助，反正明天还会再总结（

仔细想想，我的未来竟然如此美丽。

不管怎样，我一定不会再后悔了吧。

当天

早晨

下午考试，直接睡到 9.40，精神状态良好，昨晚靠着数羊的方法硬是给大脑强制睡眠了（

打了一下主席树板子，开了云斗 S 模拟赛的 T1 T2，居然很快被我秒了，我好强！

然后再整理一下思绪。

考场策略

先想所有题，每道题最多想半个小时，没想出来也跳，回头再想。

最后 1.5h 一定要开始写代码，先写有把握的分。感觉没把握就写个暴力对拍，很快的，最多 10 分钟。

如果大脑空转，就让自己停下来，上个厕所，吃点东西休息一下。

千万不要因为 T1 没想出来就死磕，万一 T1 就是很难想到的神秘贪心呢。

做题方法

考虑方向：从左往右 / 按位考虑 / 子树 / 深度 / 排名 / 神秘顺序 / 倒着考虑

视角：过程 / 结构 视角。

常见方法：考虑 dp，分析答案组成，正难则反，预处理思想，先考虑好考虑的，关注奇怪的地方。

先用直觉创，直觉没用就机械式地思考，在深入之前，好好想想这一步值不值得 / 应不应该深入。万一这个前提就是假的呢？

先尝试模拟过程，如果很困难就去考虑结构，或者换一种考虑方向。

多放空。

剩下的，听天由命吧，rp++。

千万千万不要考数论啊！！！！！！！！！！！！

考试中

开局 T1 看错题，想了一想感觉好复杂，卡住了，开 T2 去了。

结果 T2 那个题目难读程度堪比文言文，读了 15 分钟有了大概的意思之后回来写 T1。

推翻了之前那个复杂思路，然后把错题的解法想出来了，写代码的时候才意识到看错题了，火速想正解，结果发现这就是个弱智题，秒掉了。此时时间已经过去了 1h。

心态稍微稳了一点之后过来想 T2，顺着之前的思路理解，再读了一会儿，把玩了一下样例，终于把题目读懂了。

然后被数据范围启发，5 分钟想出了正解。（读题 20 分钟，想题 5 分钟有点绷不住了），然后就是写代码，还算比较快吧。写完 T2 大概已经过去了 1.5h。

然后开 T3，T3 的暴力很显然，然后继续想，这个时候有些体力不支了，去上了个厕所。

回来想特殊性质，很快想出来了 AB，C 感觉是 B 进一步的推广，有大概方向，但是细节太多了，果断放弃。

然后就去开 T4 了。首先指数写法很容易想到，试图 dp，从子树角度考虑，但是发现转移不了。放弃了。

这个时候体力已经明显不行了，回来想 T3，但是这个 T3 刚好又是那种细节多多的题目，结果越想越晕，直接给我干红温了。

此时还剩下 1h 左右，开始写代码了。想用一个统一的方法把 T3 部分分都拿下（就是红温的时候想的那个），结果发现细节太多根本调不出来（其实那个算法好像是有点错误的，非常复杂）。

然后就一直磨，剩下最后 40 分钟的时候发现自己玩脱了，此时的 T3 T4 的暴力一个没打，只有 100+100+0+0=200 分。

然后就火速把 T3 n^2 暴力写了，写 AB 性质的时候遇到了突发情况，一读那个样例就死机，不知道为什么，这导致我在完全没有样例辅助的情况下只能借助理论硬写。（结局是写挂了呜呜呜，细节太多了！根本考虑不过来。）。

发现实在没招了，最后 20 分钟把 T4 指数暴力写了，最后 10 分钟极限检查收尾。

最后预估：100+100+56+15 = 271

夜晚

和几个宝高的学长拍了合照，去外面一起吃了一顿饭。本来打算玩一会儿的但发现没啥好玩的（逃。

然后回来测民间数据了，T1 T2 没出锅，T3 那个样例测不出来的原因找到了——CCF把所有下发样例的测试点编号都设为 0，我还以为只有 pdf 上面的才是 0，难受了，这下痛失 16pts。

T4 的指数暴力也写错了（连通块判错了，唉，只能说当时太着急了，没有留够时间吧），这下又挂掉了 15pts。

最终预估：100+100+40+0=240，这下真是大众分了，合计着这场比赛只有前 2h 有得分呗（哭）。

如果，我是说如果我借助样例调出了 T3 的 ABC 性质，T1 没看错题，T4 暴力没写挂，甚至还有时间把 k=2 的部分分打出来，结果会不会不一样呢？那样的话我甚至可以打到 293 吧，这个分数够去 WC 了。

但懊悔没有持续太长时间，追求在赛场上的完美发挥是不可能的，并没有什么好懊恼的。就算一切顺顺利利，我的上限也只是低分飘进 WC 而已。这个分数实际上已经非常不错，1=，NOIP 参赛资格，七级钩都保住了。仔细想想，比赛还是反应出许多问题：

• 开考时太紧张，看错题了
• 对细节耐受度太低了
• 想出复杂解法时没有及时怀疑自己，这个方向应该是错误的
• 时间分配存在问题，实际上时间是充裕的，至少 T4 的 15 pts 是可以通过合理分配时间拿到的
• 红温的时候没有找到合适的解决方法（比如，红温的时候就不应该想题目解法，特别是细节）。
• 没想清楚就开始写代码了，浪费了很多时间

这是一次非常完美的试错，我并没有什么损失，还得到了许多经验。

如果按照平均水平而不是完美发挥来衡量实力，那这一次还算是正常发挥吧。

这个结果还是可以接受的吧。

NOIP，我来了！

和教练一起去逛了大学城，聊的挺愉快的。社交还是有好处的嘛。

可以认识到不同的人，见到不同的观点。而且和人交流也会带来学习心理学的动力。

对于恋爱不要太保守了，失败是正常的，想追就去追，这是有助于自身发展的。

感觉要多思考一些这种问题，不然人会变得平庸。

也要多了解一下自己，对自己有清晰的认知。

前言

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

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

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

过程视角发挥了作用

Looking at Towers (difficult version)

Looking at Towers (difficult version)

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

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

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

Fair Elevator

Fair Elevator

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

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

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

AB

AB

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

1. 若 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}$。
2. 若 AB 生成 B：论证是对称的。

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

结构视角发挥了作用

Mafia

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

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

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

.

写题的时候，如果要探索某个方向，不要沉迷其中的细节，粗略地看一看，假设能做到这个前提，能不能简化问题？

多训一些青题蓝题。

.

我讨厌过节，说不清为什么，就是讨厌。

中午吃饭时，家人们齐聚一桌让我倍感不适。但家人们看起来挺快活，声音的语调都快乐不少。

我只是低着头，这样的氛围让我窒息且害怕。

毫无疑问我的父母是优秀的，有时候我甚至希望他们做的不要那么好，对我少些关心和鼓励。他们总是见缝插针地和我攀谈，尽管我每天都摆着一副臭脸，爱答不理的样子。倘若我主动开口说话，那他们也非常乐意回应。只要我提什么要求，他们都会答应。

奶奶也很爱我，有东西总是让我先吃。

奶奶是个乐观的人，或者说，是个幸福的人。她时常像小孩子那般闹乐，在抖音制作自己的视频（都是些特效大杂烩），中秋夜的时候还笑嘻嘻地拜月光（也许是老一辈独有的仪式），那时我在她身后看着，她笑得浑身发抖。

毫无疑问我应当是幸福的。我拥有美满的家庭，有机会在自己喜欢的事情上努力拼搏，每天早上起来都期待着新的一天。

应当是这样的。

但我仍然觉得我是残缺的，脆弱的，悲观的。我会在深夜疲惫地望着电脑屏幕上的标签页，色彩斑斓的代码，难懂的理论，庞大的笔记。这时候我感觉我是孤独的。

我没有朋友。或者说，我没有足够亲密的情感链接。我没有能力与我的父母交好，我在和父母交流的时候会控制不住自己的焦虑，总想快点逃脱对话。

我好像没有爱人的能力。每当我和某个人深交的时候，我总会发现他们的缺点，那些缺点是那么的引人注目，令人厌烦。每当和人的交往深入到一定程度时，矛盾就会接踵而至。

但这无妨，我不需要与某人深交也能存活。或许我只是不喜欢深度的关系。浅浅的、若隐若现、求之不得的关系才好。我是这样认为的。

我仍然迷茫，我仍然自卑，我仍然颓废，我仍然焦虑，我仍然会失败。但这又怎样呢？或许它们将相伴我一生，那也没关系。

我还是会走下去，独自一个人。

我诉说我的焦虑。

我真的做得到吗？

我是不是一个无能的人？

我会失败吗？

我能做到什么程度？

我这么做是对的吗？

好颓废的一周。

训练量很饱和啊。