OI 后日谈 1

· · 个人记录

更新一下证明自己还活着（

序言. 斐波那契数列

省流：我在数学课上开挂了。

我们的数学一轮进度很快啊，已经复习到数列了。

感觉 OIer 在数论和组合这方面具有天然的优势啊（甚至和数学组相比）。毕竟是打了六年交道的东西，确实很难不熟悉。

一节数学课上面，数学老师让我们证明这样一个式子：

a_{m+n}=a_{m-1}a_n+a_ma_{n+1}

其中 a 是斐波那契数列。

正常的做法是先观察出来 a_{m+1}=a_{m-1}+a_m，a_{m+2}=a_{m-1}+2a_m，然后观察到 a_{m+k}=A\times a_{m-1}+B\times a_m 的形式，进行递推。

不过我们当时确实没人观察到这一点啊。

然后这个时候我就开挂了。

不知道为啥，我就想到了用矩阵来推这个东西。写了一下之后，发现还真可以！

然后就抱着跃跃欲试的心态进行了登台展示。

（配图：“老师，我有一个非常大胆的想法”）

\begin{aligned} \begin{bmatrix}a_{n-1} & a_n\end{bmatrix}\times \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}=\begin{bmatrix}a_n & a_{n+1}\end{bmatrix}\\ \end{aligned} \begin{aligned} \begin{bmatrix}a_{m-1} & a_{m}\end{bmatrix}\times \begin{bmatrix}a_{n} \\ a_{n+1}\end{bmatrix}&=\begin{bmatrix}a_{m-1}a_n+a_ma_{n+1}\end{bmatrix}\\ &=(\begin{bmatrix}1 & 1\end{bmatrix}\times \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}^{m-1})\times (\begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}^{n}\times \begin{bmatrix}1 \\ 1\end{bmatrix})\\ &=\begin{bmatrix}1 & 1\end{bmatrix}\times \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}^{m+n-1}\times \begin{bmatrix}1 \\ 1\end{bmatrix}\\ &=\begin{bmatrix}a_{m+n-2} & a_{m+n-1}\end{bmatrix}\times \begin{bmatrix}1 \\ 1\end{bmatrix}\\ &=[a_{m+n}] \end{aligned}

（配图：用了两块黑板推这个东西）

推的时候非常激动啊，推完之后直接把粉笔一扔然后扬长而去了。当时自己确实有一种事了拂衣去，深藏功与名的感觉（）而且这个解法确实非常妙啊，非常的有美感。

也是在那一刻，我充分认识到了 OI 生活给我带来的宝贵收获。退役了并不意味着从零开始学文化课。相反，在 OI 中学到的解决问题的能力和思考问题的方法都是非常重要的宝藏。（比如数学最后一题可以直接秒杀），在 OI 中锻炼出来的耐心和直觉也是在文化课过程中十分稀缺的。

正比如这次用矩阵递推的方式来求这个公式，相信这个不仅是在数学竞赛还是平常的文化课学习都是一个比较刁钻的角度，但是在 OI 确实比较习以为常的。作为五大竞赛里面唯一不跟文化科目相挂钩的科目，其必有自身的灵活性和特殊性。不管是退役了还是继续在信息学竞赛发光发热，六年的学习过程所带来的无形的财富也一定会成为自己的加分项和高光点。

Part I. 高考中的 OI

省流：典

说实话，感觉我在学 OI 的时候，很多时候期望题都变成一个非常套路化的题目了，无非就是用线性性瞎搞搞，或者找个组合意义，然后结合一些 DP 或者计数或者组合的知识来解决。

没想到这个东西在高考更加典啊。

甲口袋有一白两黑三个球，乙口袋有一黑两白三个球，每次操作随机旋转甲中一个球和乙中一个球交换。问 E(X_n) 表示 n 次操作之后甲口袋中球的期望。

如果这是一道 OI 题，第一步显然就是利用线性性分别计算每个球的贡献。在这里也一样。

设 a_n 表示一个黑球 n 次后还在原位置的概率。a_0=1。

a_n=\dfrac{2}{3}a_{n-1}+\dfrac{1}{3}(1-a_{n-1}) 3a_n=a_{n-1}+1 a_n-\dfrac{1}{2}=\dfrac{a_{n-1}-\frac{1}{2}}{3} a_n=(a_0-\dfrac{1}{2})\times \dfrac{1}{3^n}+\dfrac{1}{2}=\dfrac{1}{2\times 3^n}+\dfrac{1}{2} E(X_n)=a_n+2(1-a_n)=2-a_n=\dfrac{3}{2}-\dfrac{1}{2\times 3^n}

然后就解决了。

不过这还不是最典的。

抵制手推动态规划题进入高考。

不过我们实际上还有更典的。

（3）：注意到 a_1 一定在 a_1,a_2,a_3 中的第二个，这个的概率为 \dfrac{1}{3}，所以 P_m<\dfrac{1}{3}。

证毕。

无语住了。

Part II. 数学高联：猜结论人生巅峰

刚才的那些都只能算是 OI 的一点小技巧。

真正发挥出 OI 思想的，还得是数学高联。

2024 数学高联一试压轴

两个复数 z,w 满足 z+w=2，最小化 |z^2-2w|+|w^2-2z| 的值。

\begin{aligned} |z^2-2w|+|w^2-2z| &=|z^2-2(2-z)|+|(2-z)^2-2z|\\ &=|z^2+2z-4|+|z^2-6z+4|\\ &=|(z+1)^2-5|+|(z-3)^2-5|\\ &=|(z+1+\sqrt 5)(z+1-\sqrt 5)|+|(z-3+\sqrt 5)(z-3-\sqrt 5)|\\ &=|(t+2+\sqrt 5)(t+2-\sqrt 5)|+|(t-2+\sqrt 5)(t-2-\sqrt 5)| && (t=z-1)\\ &=|(t+2+\sqrt 5)|\times |(t+2-\sqrt 5)|+|(t-2+\sqrt 5)|\times |(t-2-\sqrt 5)| \end{aligned}

然后你注意到这四个向量都是 t 左右平移之后的结果。根据调整法，显然将 t 纵向平移至 x 值最优，此时 t 是实数。

然后你把那四个向量对应的点和 t 对应的点标出来，考虑 y 轴在哪里是最优的。根据调整法 y 轴肯定在 [t+2-\sqrt 5,t-2+\sqrt 5] 这一段最优。

一个经典的错误就是令 t=0 得出来最小值为 2，实际上这并不是最优的。

考虑继续调整。每次让 y 轴向 t 移动 \Delta y 的距离算变化量，发现还得是取到两端最优。

然后就可以得到 8\sqrt 5-16 的最小值。

然后就是下午的二试。

说实话，我在学 OI 的时候自认为自己：构造依托答辩，根本找不到性质，根本猜不出结论，罚坐大师。

但是在二试，我达到了自己猜结论实力的巅峰。

2024 数学高联二试 A

给定正整数 r，构造一个公比为 r 的无穷等比数列，要求里面每一项其权值最小值最大。定义一个数的权值为离它最近的整数到它的距离。

实际上我二试一开始因为太困了（当天晚上凌晨三点睡的）然后就趴了两个小时。

一觉醒来，发现自己好像会 r 为奇数的情况了。不就是 a_1=\dfrac{1}{2} 吗？这样就能达到最大值 \dfrac{1}{2}。

然后 r 为偶数的情况，就猜一个跟 \dfrac{1}{2} 尽量接近的数字，尝试去构造一个分数。

注意到 r 跟 r+1 互质，然后就猜一个 \dfrac{\frac{r}{2}}{r+1}=\dfrac{r}{2r+2}，这个数字在等比数列会左右横跳，而且超级接近 \dfrac{1}{2}。

但是由于我确实不会证，所以装模作样的写了点过程。

出完考场之后，发现自己居然对了！！！

有点太厉害了。

2024 数学高考二试 C

有一个 3\times n 的网格，定义一个联通块的权值是黑格子减去白格子个数的绝对值。你需要构造一个网格，使得最大权值最小。

说实话，我是完全不会的。

但是我知道网格图可以黑白染色。

我也知道黑白染色之后可以取到 n。

然后我就写上去了。

你知道的，我在考场上一刻都没有以为这个东西是正确答案。

但是它确实是的。So Surprise。

补一个完整证明：

若第二行黑白分别有 a,b 个，一三行合起来黑白共有 c,d 个。如果我们全选第二行，然后分别选择第一三行的所有黑色 / 所有白色，那么两种方案就是 a+c-b 和 d+b-a。注意到两个加起来等于 2n，说明如果这两个不相等，那么必有一个绝对值大于 n。黑白染色对应着两个相等的方案。然后就证完了。

没准我把过程补了还能混个省队

不过说实话，这些结论放到 OI 题里面应该都是比较浅显的，充分说明了现在我们 OI 真的是太卷啦

所以说 OI 里面专门针对直觉和构造这一类的训练还是比较必要的，以后可能会有大用。

Part III. 回顾与展望

说实话，在我还在学 OI 的时候，常常认为高三是痛苦的，进集训队是快乐的——高三有很大的学业压力，几乎重头开始的文化课，写不完的作业，只有一次机会的高考 \cdots\cdots

不过就现在而言，相比于无止境的内耗和焦虑，OI 现在越来越差的环境和氛围，还有一些抽象的人物（我不好评价，祝高一学弟未来顺利），高三反倒还解决了一些长久以来的问题。有了很多志同道合的，尤其是原信息组几个月没见的同学。文化课的脑力消耗也远远比不上 OI。每天至少能够学习一些新东西，慢慢地精神内耗也就减缓了。

我在 NOI 的那一周根本没有心思打游戏，回来复健的那一周也一样。实际上高三并不是所谓的「没有休息」或者说「玩命学习」，至少我觉得这样一定不是一个高效率的学习方式。现在我每天可能还会上线看一眼，我觉得游戏带来的情绪价值是其它东西比不了的。

不过还好，我算是最早一批开始重返文化课的选手。我有差不多一个月的时间，一天只有四门科目，有一些空闲的时间去赶上物化生的一轮进度。

入学考的成绩也是比较超乎预期的，居然进了年级 600 名，还是化学 28pts 的情况下，很厉害。这次虽然各科挂分都比较严重，但是居然到了 400 名，也是挺意外的。每一科都有至少 5pts 的提升，但是我相信自己真正的进步肯定远不止这 5pts。

最近一个月，我觉得最主要的，也是贯穿始终的一个关键词，那就是「信心」。

这种信心不是盲目的自信，而是在一次次的突破中凝练而成的动力。高三也是我人生中第一次，可能也是唯一一次当上语文课代表（因为一次小小的巧合），受到了我们语文老师和班主任的「特殊关照」。先暂且不谈这种关照我是否喜欢并且愿意接受，能够体会到这种当课代表的感觉还是很奇特的。我的语文作文之前几次总是因为各种各样的原因（偏题，论述不充分等）从 45 一路下滑，不过这次月考居然上了 49.5，属实是意外之喜。默写从之前的一个空都填不出来，再到这次月考的全对，确实对得起我赤壁赋背到凌晨一点。

我刚开始可能和英语老师比较疏远，至少是有些害怕的。尤其是第一节英语课的时候，那节课真的是灾祸频发，包括但不限于单词不会填，句子翻译不出来，还有被同桌 @Sentoayaka 打手板，还有后面作文的「多喝热水」事件。

（配图：下次找个机会把我第一次读后续写贴出来）

不过我们的英语老师确实是一个有意思的人。她的讲课风格很有意思，在渐渐地熟悉之后，上课会有一种非常亲切的感觉。看到自己完型从错一半到错两个，作文从以前写不出来到能够达到 24 分，虽然语法填空 -10.5，但是还是很高兴的。

数学的话，真正到了高三才发现它与 OI 的关联比我想象中要大得多。我退役之后总想着把之前的东西给忘掉，但是现在我又想着尽力把它留存下来。OI 里面很多知识都是相当具有前瞻性的，可能可以切中未来很多年的高考最后一题。当然高考数学跟 OI 也有很多区别，比如圆锥曲线短轴长度应该是 2b。不过这些东西都是简单的，真正难的部分（除了导数）在学 OI 的时候就应该已经把它啃掉了。

物化生的话，我只能说，不急。不过这次化学确实给我了很大的惊喜，最后一道实验题只错了一个空，里面的计算也算对了。（至于它上面一道的有机题，我也是对了一个空）

总的来说，我觉得银牌或者退役绝对不能算是自己没有进队的一种「亡羊补牢」。至少从位移来说，大家起点是一样的，终点也是一样的，位移自然也是一样的，只不过可能有一条狭窄的独木桥，和一旁蜿蜒曲折的山路。我更喜欢把高三看成成年之前的一场「期末考试」，全方位地考验你十八年的成果。99% 的人在高中都会经历这个过程，当然肯定也会有人不需要经历它。既然已经决定踏上高三，那就在分别前祝福他们，然后脚踏实地，给这场「期末考试」交出一张漂亮的答卷。