OI与布丁

读到一本很有意思的书，突发奇想把它搬进了 OI。原作者【美】吉姆·亨勒。下文的“我”均不只本专栏作者。原书是关于数学的，感兴趣的可以阅读原书。由于本土化困难（？）的原因删减了一些章节。本文不会涉及具体的某个算法或者数据结构，大部分题目都是偏数学化的，但是它们仍然值得思考。

你可能会在这里看见：

本文针对水平在蓝钩以下的读者，如果有较强 OI 能力的读者们饿了可以直接跳到食谱部分。

如果您打算复刻文中的食谱，请注意减少部分调料的用量，使其更适合中国口味。同时，请注意本地法律法规对饮酒和罂粟籽的规定。顺带一提，成功了一定要告诉我！

阅读这本书的前提是，如果你能正确看待 OI 和烹饪，你会发现两者之间有着惊人的相似之处。这本书旨在探讨 OI 和美食烹饪法，揭示出两者本质上的相似之处。

当然，OI 和烹饪是两码事。即使你把菊花图吞下肚，也算不出一块英格兰松饼的最大流。对大多数用餐者来说，一碗实实在在的意大利细面条比任何理论盛宴中的算法更令人心满意足。但这是错误的观点。

相反，我们要思考烹饪和计算机科学有何共同之处：它们都是从手摸开始，简单而实用。它们逐渐发展成艺术，复杂多样而又令人愉快。通常，它们以指导清单的形式呈现在你的面前，都会带给你特殊的体验，都会产生困难，都会赞颂胜利者，也都会令新手胆怯。

这只是开始。

但是我必须提醒你，这是一本关于 OI 和烹饪的书，但不会引出两者之间的关联，尤其是 OI 对烹饪是没有什么用途的。有时，智商可以在厨房发挥作用，但这不是这本书要说的。

此外，OI 本身不是这本书的要点，我会让你看到一些 OI 内容，真的是很酷的题目（实际上是一些令人难以置信的东西），目的是向你说明 OI 的特点。但这不是一本“信息学竞赛”书。

食物也不是这本书的要点。这本书里有食谱，好的食谱，令人震惊不已的好食谱，但它们是为了更高等级的目的而存在的，所以这也不是一本烹饪书。

读了这本书之后，你可能会更了解 OI，也可能更了解烹饪，但这都是次要的。这本书的目的是让你以一种新的方式看待 OI 和美食学，就像看异卵双胞胎那样。

我想要让你相信：

1.（大部分人）接触 OI 和烹饪的原因或多或少是相同的。

2.我们解答好题所持的观点、态度以及所使用的方法与我们解决厨房中的问题时所用的是一样的。

3.我们判断解法和评判食物的很多标准是相同的。

4.总的来说，信竟和美食里的生活惊人地相似。做题家和厨师拥有相似的梦想、相似的担忧，也有相似的令他们产生负罪感的秘密。

关于 OI 和烹饪我要说的还有很多。从 OI 和美食学的角度，我对美学、创造力、灵感、策略、天赋和堕落有自己的看法。我想要把它们放到一本书里。

还有一点要说明的是这本书有一个更深层次的目的。在 Ad-hoc 题和油酥糕点的背后是这本书真正的主题——乐趣。

从事 OI 和烹饪都是有原因的，但是在这两个领域里，主要动机都是快乐。从美食学的角度看，这并不难理解，但是令人惊讶的是，大神们也是菠萝派。

我无意表现得不够谦逊，但是我的确认为自己很擅长找乐子。你可以问问我那些朋友。他们都会告诉你相比那些应该有的，我还有更多有趣的事。

我能从重复的工作中发现乐趣，我对看似毫无希望的任务乐在其中，就算出了大错，我也能从中找到兴趣点。如果有什么是我感兴趣的，我会毫无保留地投入其中，可能一整段快乐时光里有的只是画满有权图的纸、和着一小块黄油的面团。

我并不清楚这到底是怎么回事，但就像参禅，我的内心有这样的激情，我愿意与你们分享。

我要向很多人表达谢意。

那些帮助我寻找论据的人，那些帮我做布丁的人，那些对我的计划和想法提供支持，对最终实现起到至关重要作用的人。还有在这本书里走个过场，露脸或者没有露脸的我的家人们。最后，正如那位诗人所说，他们还提供坐下来吃的服务。

我尤其想感谢比尔·兹维克和凯西·布罗迪、大卫和桃瑞丝·科恩、卡特波托和尤兰达·加尔萨、约翰和马特·索恩、卡洛琳·考克斯和山姆·伯金斯、史蒂夫·斯皮茨和辛西娅·因戈尔施塔特、玛乔丽·辛妮切尔和斯坦·谢勒、罗恩和戴尔·布兰科、克劳斯·彼得、薇琪·凯尔恩、我的学生们，以及汉勒斯·艾莉森、弗莱德、波西娅和希达。

在本书完成前的最后阶段，普林斯顿大学出版社的工作人员——迪米特里·凯尔特尼科夫、卡罗尔·施瓦格尔、马克·贝里斯，还有我之前提到的薇琪·凯尔恩给予我的关心、理解和热忱的帮助鼓励了我。

最后，要感谢利昂·斯坦梅茨，他画的插图惊人的好，虽然本专栏作者并不打算吧插图也给搬过来。

吉姆·亨勒

2014年7月

【还感谢原作者，和正在阅读的你。】

【Nuclear_Fish_cyq】

【2025/11/29】

我们先从两个小调查开始，分别是 OI 和烹饪方面的。从表面上看，它们有些许相似之处，但没有更恰当的词来形容这些相似之处，暂且称它们为“精神”相通，我会在最后详细说明。

几年前我开始涂鸦，我拿着纸和笔坐下来时会毫无目的地画一些线。我画了一个由方格组成的三角形。

我在下面的格子上涂上颜色。

我开始把这些颜色想象成咒语。我定义了一种运算，如果将白色定义为 $0$，蓝色为 $1$，红色为 $2$，他们遵循 $(6 - a - b) \bmod 3$我们可以有一个运算表：

我想象把两个方块运算产生的结果放在它们上面会发生什么：

我注意到最顶上的方块颜色完全由底部的方块决定。我那是很好奇它们到底具有什么样的关系。你可能已经意识到自己正在面对一个对简单、原始的纸笔运动乐此不疲的人。当我最初想到在正方形里放上镜子的时候，我一个接着一个地画了一个又一个三角形。

我最开始画了个两层的三角形，它很简单，只需要一次运算。

然后思考三层的三角形。它底层中间的三角形参加了两次运算。

四层的三角形中最底层中间的两个方块都影响了答案三次。

1 2 1 和 1 3 3 1 的规律让我想起了组合数，但一直有点遗憾，不是吗？我一直在猜测，而不是证明。

一番思考后，我确定了每个方块影响答案的次数的确是组合数。

你可能会怀疑：“这真的是电子竞技吗？”

这的确是信竟。我以宽泛的态度看待这一竞赛，于我而言，任何可以被完整、清楚地用代码描述出来的结构都是信竟的结构，而任何可以准确解决关于这个结构的代码都是答案。算法是数学的一大成就。创造这样一个结构，对其进行探索，证明关于它的各种命题——这就是出题与做题。

三角形的颜色可以用代码模拟出来，在挖掘它的规律之后还可以进行各种优化，这就是 OI。

以下是我对于每个方块影响答案次数是组合数的证明：

每个方块都会对它左上和右上的方块造成影响，因此一个方块的贡献是左上方块和右上方块贡献次数的和。边上的方块肯定只能贡献一次，而这听起来非常向杨辉三角，而事实上它就是。

因此，我们可以用 Lucas 定理算出每个底边方块的贡献，然后加起来取负数就是答案。

我称它为“涂鸦”。还有更多种涂鸦，任何人都能创造出自己的涂鸦——仅仅是按照自己的意愿制定规则。比如说我，对这种与这题形似的涂鸦乐在其中。它是这样的：

画一个杨辉三角，然后圈出所有是二的倍数的点。它们会形成一个分形！

有很多乐趣在其中。圈三的倍数、四的倍数，或者完全不同的小思考题……

还有各种各样的涂鸦，我建立了一个网站，原书里大部分章节都在网站上有注释说明：

【原网站似乎已经失效】

我请各位读者来网站看看，特别要告诉你们的是，那里有很多涂鸦。

【本专栏作者也请你与他分享你的涂鸦：here（已停止更新）。】

这个标题看起来有点突兀。面条和涂鸦看起来完全没有共同之处，但我会在这一章节结束的时候再说。

事情源于几年前，当时我正为朋友们准备晚餐。我原本计划做意大利面。

但是当我知道有一位客人有乳糜泻症，对小麦蛋白过敏时，我的计划就被打乱了，她不能吃小麦做的意大利面。

这真是个坏消息，但我还是决定做意大利面。在杂货店我发现了一种玉米做的意大利面条，就买了一箱，做好之后就招待我那些困惑不已的朋友们吃了一顿面糊糊。

可能是因为煮过头了，但是我想不将玉米意大利面条煮透的唯一方法就是把它留在杂货店里。我的客人尴尬地向我表示了感谢。我本来可以将这事就此忘掉，但是我看到了令我好奇着迷的挑战。有什么可以替代意大利面呢？我能不能找到一种物质是：

不是饺子，不是团子，也不是蒸粗麦粉，这些都含有小麦。 我想要的是一种用途很多的人造意大利面，可以轻松取代通心粉或斜管面。法式炸薯条、球芽甘蓝、玉米片……我几乎都试过了。

这似乎是艰难无比的挑战，甚至可能毫无意义，但这确实令我着迷。

而且这项挑战让我乐在其中。如果我告诉你们，经过几年的尝试，我的意大利面替代品已经上桌了，你们会被吓到吧。我在成功和失败间游走，除了我的家人，没有人受到伤害。

我做过最快乐的实验是需要剥玉米粒的。以下是一个可行的范 例。

有人可能会抱怨说“玉米不像意大利面那样软，而且玉米也不如意大利面那样入味儿”。确实是这样，但是这是一道绝佳的美食。

如果你想要一种口感软的意大利面替代品，用米就可以了，但是，我说的不是意大利调味饭。意大利调味饭不是意大利面的替代品。无论你用什么酱料，真正的意大利面的烹饪过程几乎是一样的。

意面替代品的烹饪其实就是与酱料进行混合，而不同的意大利调味饭有不同的烹饪方法。

米的种类很重要，好的泰国香米可以带给你松软的口感，但米粒和许多意面酱料一起咀嚼时的口感就不一定软了。

除了英文读音（noodles and doodles），面条和涂鸦没有什么共同之处。我想通过它们证明 OI 和美食烹饪学之间的共同特征，而这些特征会在本书中反复出现。

首先，它们都是充满乐趣的事，当然，有时候我们做饭只是因为饿了，而有时候我们进行编程是因为没法玩网页游戏。但是真正的烹饪和 OI 确实是一大乐事。它们是结构和材料的游戏，伴随它们的是能够深深吸引你的创意和美味。

其次，尽管吸引力与审美有关，但是也与智力相关。我们都是好奇宝宝，我们想去品尝味道，想自己动手修修补补；我们想去探索，有所发现。我们尽情享受未知的一切。

第三，也是最重要的一点，我们常常不知道自己在做什么。我们踯躅徘徊。OI 和美食学是难以理解的混乱邪恶事物，我们必须在不断犯错中成长、进步。我们成为实验者，尝试这个，尝试那个。看上去我们好像没什么章法，但事实并非如此。出人意料的是，对最优秀的厨师和做题家来说，四处碰壁，在失败中继续尝试也是一种有效的方 法。

下一章节我们会关注在失败中进步。

告诉我们如何解开 OI 题的书成百上千（其实屈指可数），而讲述烹饪方法的书成千上万。下一章我（可能）会说服你相信一把钥匙有时不止开一把锁。

我不时会听到有人说：“我肯定不会烤面包”。

我常常会听到（我自己也会说）这样的说辞，很熟悉，即使用词不同，但语气一致。

“我肯定不会这题”。

相似的自白，同样的伤感。与缺点无关，也没有焦虑。其实，每一个人都会 OI，而所有人都会烤面包。做 OI 题与烤面包都是在练习解决问题，而最值得我们注意的是解答问题的最佳方法也是解决厨房中烹饪问题的最佳方法。

对于解决问题我有自己的一套简单理论。要解决问题你需要的是人格分裂【非精神病学相关】。首先，你需要自信。好的问题解决者确信自己能解决任何事情。面对一个问题，成功的解决者会无所畏惧，他们相信自己会找到突破口。

但是，你还需要怀疑。一旦你有了一个答案，自信心会变得没什么意义。你需要质疑自己的答案，担心它是否正确。hack 你的答案，模拟它，最终，好的解决者的行为似乎在告诉我们他们已经确信自己的答案有不对的地方。

我想你可以理解这些人格的意义何在。起初，你需要自信，没有自信很难开始。即使你已经开始了，缺乏自信会削弱你的力和决心。

之后，当你有了一个答案时，你需要的是谦虚、具有质疑精神的人格。你想要分析、理解自己的答案，检查是否还有疏漏和欠缺之处，会不会被 hack。

第一种，即自信的人格是最难得的，因为你不能仅靠简单的决定，想要自信就可以自信的。我向我的学生们建议，用一种替代品来代替自信的人格，似乎收效很好。我告诉他们自大、傲慢一些，而绝大多数人都能做到。

我们通过一个例子来看看自大、傲慢如何在厨房里行得通。就一起聊聊面包吧，那么多人写过第一次尝试烤面包的恐怖经历，总是会有各种困难，想要知道的太多，而失败的原因五花八门，至少看起来是这样。酵母放了多少，怎么揉面，如何给面团定形，何时算烤得恰到好处，这些要花很长时间才能学会！

我们来看一位自负（无知）的厨师如何用一个简单的烹饪方法，只尝试一次烤面包就成功的。

谦卑的厨师会说：“这并没说明要加多少面粉或者怎么揉面。我需要提前知道这些，但是我并不知道。真是没什么希望能做成了。”

但是自大的厨师这样想：“食谱里没有说明的部分一定是不太重要的，我要试试看会发生什么。”

让我们也自大地尝试一下吧。

直到加入面粉这一步我们都没有任何问题。我们没有面包粉，用的是多用途面粉。（烤面包不也是多种用途中的一个吗？）我们加面粉直到很难再搅动面和水时，也许是时候揉面了。我们对揉面的概念认识不清。你也许看过“铁厨”如何揉面，或者在 B 站上看过一些相关的视频。无论怎样，我们都要把双手放到碗中，来回揉混面团。面可真黏，看上去不对，可能需要加入更多的面粉。我们再加一些面粉设法解决这个问题，可能会有一些面粉洒在台面上，也可能不会。过了一会儿，我们判断揉面可以结束了。生面团看起来一点都不光滑圆润，但是我们还是把它放到一边发酵。在哪发酵呢？碗里？在操作台上？床下？用碗好像不好，因为有些面粉沾在上边，所以我们把生面团放在操作台上。

我们就这么莫名其妙地按食谱做了一遍。生面团没有发酵好，稍稍摊散开了。我们已经在这上面耗掉几个小时，还是要继续。那我们做粗面包吧，但烤出来的是面包吗？

刚出炉的面包竟然……相当不错！

为什么呢？老实说，我们做得很差劲。我们没把生面团揉好，而我们把它放在操作台上会使它变干。我们参照的食谱是基本的、最原始的指导。我们没给生面团添加任何令它可口或者给人惊喜的东西。

但为什么我们烤出来的面包很好呢？

首先，超市里的面包太难吃了！我们必须经历惨败甚至做出更糟糕的东西。无论我们做什么，我们的面包都会有无与伦比的味道和酵母的芳香。这是真的。

其次，面包师是最有包容性的。你用的酵母可多可少，糖和油也一样。你揉面的时间可长可短，生面团的发酵时间也没有长短限制，甚至烤制的时间也可以或长或短。你还是可以做出不错的面包。

当然，也会发生奇怪的事情。有一次我做的面包溢出了烤盘的边缘，把面团从烤盘上分离下来是场硬仗，面包的样子可笑至极，但是味道真的很棒。

那如果我们失败了会怎样呢？

一旦失败，我们浪费的食材至多值十块钱。我们没花太多时间（OI 考场上请勿模仿），也没有令任何人失望（请客吃饭的时候我们才不会这么自大）。但是我们学到了一些东西。

我们会从每次烹饪中学习。谦逊的个性会让我们仔细思考自己的好恶。我们搜寻更多知识、食谱和说明书，我们会为可能提升的面包品质而筹划着。

我一周会烤好几次面包，并且坚持了25年。我的基本配方是历经多年总结而成的，难以置信的好，而我也是这么说我自己的。

我会在这本书里把我的配方传给你，并且会谦虚地接受你的表扬。但是另一个我又希望你不理会我的配方，而是自己探索更完美的面包味道。如果你是这样做的，你会感到快乐（也会吃得舒服），而你最终会得到全新的、令人惊叹的烤面包。

在我公布制作方法前还有一点点事情需要说明一下。我想要的是那种以小麦为主、口味清淡的面包。我希望它是有益健康，令人愉快的。我希望它很可口但是容易得到。这种面包绝大部分成分是精白面粉，所以质地清淡。因为有小麦胚芽，所以它有全麦面包的蛋白质，而配方中的其他部分还会有额外的小麦成分。

这个方法简便，烤出的面包很可口。我一共只需花费15分钟的时间，而这些时间可以分散到一天中空闲的时间里去，每天都可以为家人提供新鲜的面包。

诺贝尔物理学奖获得者，物理学家理查德·费曼被视为自信者的典范。他求知好学，但是好奇心很多人都有。他很杰出，但很多人都很出色。让费曼脱颖而出的是无畏。他觉得自己能解决任何问题。对他来说，无知不是障碍。他那本精彩的回忆录《别逗了，费曼先生！》讲述了很多这方面的例子——认知能力、蚁学（蚂蚁）、【无法过审】学、锁匠 行业和【无法过审】学。

伟大科学家与平庸的天才之间的区别就在于：

自信

我们来看看自负的态度对解开 OI 题有什么帮助吧。

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 $i$ ($1 \leq i \leq n$) 个新成员对第 $j$ ($1 \leq j \leq 3$) 个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i$ ($1 \leq i \leq n$) 个新成员分配到了第 $d_i \in \{1,2,3\}$ 个部门，则该分配方案的满意度为 $\sum_{i=1}^{n} a_{i,d_i}$。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 $\frac{n}{2}$ 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

我们来看看自负的难题解决者（我们就叫她斯梅德利吧）是怎么处理的。

一开始，斯梅德利选择了把所有人都分配到他们最满意的部门。

理由呢？ “没有什么理由，真的”，斯梅德利说，“我得做些什么。他们总得去哪里”下一步？……斯梅德利违反了“不存在一个部门被分配多于 $\frac{n}{2}$ 个新成员”的条件。

接下来斯梅德利可以把多出的成员移到别的地方去或者回到起点看看。自负的人从不会回头（除非真的没路了），因此她要找出一些移动的代价最小的成员。

斯梅德利对接下来的谜题的走向有什么预判吗？“没有什么想法，”斯梅德利说。她注意到至多有一个部门人数过多，于是算出了每个人最满意减次满意的差，然后进行排序。

她写了一个可以执行这所有过程的代码，只是稳步前进，没有太费力气思考。一旦你着手解题，你其实没有什么选择，你能做的只有继续前进或者返回原点。

斯梅德利会解出谜题，无论是一次成功还是第二次，她都会解决的，因为她从不往回走。很多人没能解开这个题。

为什么？他们选择其中一个解题方向，没多久又开始担心“我是不是错了，我好像看不出一丁点成效。也许我应该退回去！”。他们转向另一个解题方向。很不幸，他们没有之前那么自信了。又过了一会儿，他们又变了，如此反复，来来回回。最后放弃。

缺乏傲慢的态度，这就是问题所在！

但我可能需要为本章节中所有的傲慢态度道歉。你并不自大傲慢，我知道。你和善、谦逊、自信，你可能从未想过傲慢自大地为人处世。你很难成为斯梅德利。

但是，如果你能设法模拟一下自大傲慢的人，你会发现这么做是很有用的。在与难题（食谱）对抗的时候想象一下斯梅德利会做什么，即使毫无头绪，也要保持自信。而我们接下来，在下一章里会谈谈美学。

什么才是真正的信息之美？这是一个难懂的概念，微妙、抽象而又与知识、智力有关。多年来我一直试图描绘出这种美，但是答案却不期而至。

简而言之，这种美就是芝士蛋糕。

我们有时会渴望品尝一些简单纯粹的味道——比如薄煎饼、一个水煮蛋、汉堡、香蕉、玉米棒，或者加冰的沙士饮料。有时我们又会惦念那些熟悉的、天然可靠的食物。

食物的魅力有很多，简单纯粹是其中之一。简单的配料、简单的制作。食物不会欺骗，表里如一。简单的食物未必不精细。我家里至少四本烹饪书的书名里有“简 单”一词。简单纯粹是很难实现的。试想一下，一盘自制的加了帕尔玛干酪的黄油酱汁面条是绝对简单的，我仍在研究怎样才能做好。

简洁也是 OI 中的美。结构简单，表述简单，充满魅力，令人着迷。一个有趣的 trick，一个规则的博弈，一些题目的世界只是几个简单的假设——这些足以让你投身其中。它们像一扇敞开的门，透过此门，你会看到一个秀丽可爱而又神秘的花园。

复杂也很迷人，我们会在下一章详述。

芝士蛋糕体现出了简单食物之美。最好的芝士蛋糕（在我看来）是未加装饰的、没有不相关元素的，能品尝到的只是洁白的、或甜或酸口味的牛奶和奶油芝士，可能还会有脆皮。我逐渐找到一种芝士蛋糕的做法，比较薄，是用做馅饼的烤盘烘焙而成，上面是甜的或者酸的奶油冻。我吃过很多莎莉集团（Sara Loe）出的芝士蛋糕，觉得很好吃。但是当时还年轻的我面对纽约式芝士蛋糕时，立刻被深深迷住了，我觉得我吃到的是奶油的精华。

尽管那时我身在波士顿，却又碰到小沃森出售的这种我认为奶油更浓稠，不那么酸，也不那么干，和真正的纽约式一样的芝士蛋糕。

我真的很喜欢，我太太也喜欢。但是小沃森（Baby Watson）的蛋糕很贵。我们决定想办法自己做。

做芝士蛋糕的方法多得数不清，很多都自称是“最好的”。但是，以下这个才是真正最好的。

现在我们来说说在芝士蛋糕上浇上糖浆、果酱这个习惯，真是毫无意义。芝士蛋糕温和的口感完全被这些黏糊糊的东西掩盖了。

甜酱可能会让芝士蛋糕有一种独特的酸味。但是我 OI 化的灵魂更爱（我的）芝士蛋糕简单纯粹的内心，它在不断低语“奶油、奶油、奶油”。蛋糕的外层脆皮提升了纯粹的味道，它与全麦酥饼过分鲜艳的外形不同，安静地述说着“黄油、黄油、黄油”。这柔和美妙的二重奏会被那些酱汁淹没，让人无法体会得到。

但是，如果你想让味道更饱满、丰富，以下这个方法是极好的。

我认为（至少小学奥数里）一笔画问题是没有意义的。点和边只是杂乱无章的堆砌在一起，通法大家都能很快掌握，点的位置没有任何意义。我看到了手机的解锁画面：

并开始想：我能不能一笔画出最复杂的密码？

严谨起见，我们要定义一个“手机密码”是什么。