开头我先说点心里话。做信息学奥赛这几年被问得最多的问题之一就是“《信息学奥赛一本通》的题解该怎么看”市面上的题解资源其实不少洛谷上有讨论区GitHub上有人整理过题解仓库各大博客也有一堆“一本通xxx题题解”。但真正看过的人心里都清楚绝大多数的题解只贴了一份能AC的代码注释都少的可怜更别说什么“为什么这个状态要这样设计”“为什么这个双指针是对的”。我当年刷这本书的时候也是一行一行对着别人的代码抠抠了半天以为自己懂了结果合上题解过两天同样的题型换个数据照样卡住。这篇内容不是去罗列一堆题的答案而是把我自己刷《信息学奥赛一本通》主要覆盖基础篇到提高篇的经典题目时沉淀下来的思考方式、解题模板、以及“题解到底该怎么看”的经验一起拆开讲。适合刚入门准备系统刷题的新手也适合刷了一遍但总觉得没抓到本质、想回头梳理体系的老手。1. 先弄明白《信息学奥赛一本通》在整个OI学习路线里的位置1.1 这本书不是用来“学语法”的而是用来“搭思维骨架”的很多人拿到《信息学奥赛一本通》就开始从第一章顺序往后撸撸到循环结构觉得“太简单了跳过”撸到数组觉得“不就是下标存数吗”撸到函数觉得“也没啥”。这种刷法其实是在浪费这本书最值钱的部分。《一本通》的题目编排是有讲究的。它不是按难度单调递增的而是按“思维模型”分块枚举、递归、贪心、动态规划、图论、数论、搜索这些章节里每一章都是在训练一种特定的思维范式。比如贪心那一章前几道题让你排序取最大中间几道让你想清楚“为什么排序之后贪心是正确”的最后几道其实是归类到“区间问题”。我自己的体会是这本书适合在已经有C基础会输入输出、会用数组、理解函数的传参之后把重点放在“每道题用了什么模型模型还能套到哪里”上。它本质上是给你搭一个“思维骨架”后面的洛谷题目、NOIP真题、ICPC热身题都是在这个骨架上添肌肉。1.2 为什么我刷完提高篇之后又回头刷了一遍基础篇这个事说出来有点丢人但我复刷基础篇的时候真的发现了很多当年“假装懂了”的题目。比如基础篇里的二分查找当年我只记住了“lmid1、rmid-1”的写法遇到“最小值最大化”还是不会。后来刷到提高篇的“进击的奶牛”这类题才发现二分答案的本质不是“在数组里找一个数”而是“把一个求最值的问题转换成判定问题”然后用二分去逼近那个临界点。所以如果让我给一个刷题顺序建议我会说第一遍按章节顺序刷遇到不会的题不要死磕太久先标记看完题解写出来第二遍等你有了一定题量之后回头只看那些标记过的题重写一遍。两遍过后这本书才真正变成你的。2. 从一道“简单题”讲透题解该怎么做以最大公约数和线性筛为例我挑两道题来完整走一遍思考链路因为这两道题在《一本通》里关系很近数论那一章一个是基础中的基础一个是从基础延伸到效率优化。我会把当时的原始思考过程还原出来而不是直接扔一个AC代码。2.1 最大公约数从枚举到辗转相除中间那个“跳跃”才是关键题目一般是这样给定两个正整数求它们的最大公约数。新手上来就枚举#include bits/stdc.h using namespace std; int main() { int a, b; cin a b; int ans 1; for (int i 2; i min(a, b); i) { if (a % i 0 b % i 0) { ans i; } } cout ans endl; return 0; }这代码对不对对。能不能AC小数据能。但它只体现了“枚举”没体现任何“算法思想”。我当年看书上的题解用辗转相除法第一反应是“这个代码怎么背”——现在回头看当时的我完全没抓到重点。辗转相除的核心不是一个公式而是一个观察如果 d 是 a 和 b 的公约数那 d 也一定是 (a - b) 和 b 的公约数。所以可以把问题从“求 a, b 的公约数”缩成“求 b, a mod b 的公约数”不断缩小规模直到其中一个变成 0另一个自然就是最大公约数。书上的代码往往是这么写的int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }但题解只给这一行读者很容易背下来就完事了。真正有价值的题解应该告诉读者这个递归的“状态变化”是怎么来的。“gcd(a, b) gcd(b, a % b)”这句话的本质是“把较大的数换成它对较小数取余的结果”而取余之后数字一定变小所以递归一定会终止。如果让我重写这道题的解题笔记我会额外补一个环节自己把枚举算法改成递归写法再改成循环写法再想想为什么递归不爆栈因为 log 级别。这几个步骤才是题解里最该写而大多数题解没写的东西。2.2 线性筛为什么每个合数只被筛一次代码怎么写出这种感觉《信奥一本通》提高篇的数论部分几乎都会碰到质数筛。埃氏筛很简单for (int i 2; i n; i) { if (!isComp[i]) { for (int j i * i; j n; j i) { isComp[j] true; } } }复杂度是 O(n log log n)看起来已经不错了。但很多进阶题对时间卡得很紧或者后续要做欧拉函数需要用到最小质因子这个先按住不表这时候就必须上线性筛。线性筛的代码初看非常劝退const int MAXN 1000000; vectorint primes; bool isComp[MAXN 5]; void linearSieve(int n) { for (int i 2; i n; i) { if (!isComp[i]) { primes.push_back(i); } for (int p : primes) { if (i * p n) break; isComp[i * p] true; if (i % p 0) break; } } }我当时盯着“if (i % p 0) break”这一行看了很久最后才捋明白其中的道理。核心在于每个合数只会被它的最小质因子筛掉。举个例子12 的最小质因子是 2它只会被 2 筛掉6 * 2不会被 3 筛掉。所以当循环枚举到 i 时如果 i 能被某个质数 p 整除就说明 p 已经是 i 的因子那 i * p 的最小质因子就是 p不会更小。再继续枚举更大的 p比如 i * next_p虽然 next_p 也是质数但 next_p 大于 pi * next_p 就有更小的质因子 p这个数应该让“某个带因子 p 的组合”去筛而不是在“当前这一层”筛。如果题解只说“线性筛是 O(n) 的”读者抓不住性能来源如果只说“每个合数只被最小质因子筛一次”读者还是不知道怎么写的。这两个点必须合起来讲代码才不是死记硬背。我就是在这里想明白的很多看起来玄的优化都是在问“同一个结果有没有被重复算过”没重复算过复杂度自然降下来。3. 动态规划从读懂题到写出状态转移方程一条完整的思路链《信息学奥赛一本通》的动态规划章节是整本书的重头戏。很多人在这一章崩溃是因为直接去背“dp[i][j] 表示前 i 个物品容量为 j 时的最大价值”这类模板但题目稍微改一下又不会了。3.1 从最长上升子序列到“状态设计观”最长上升子序列LIS是一道很经典的题。书里的 O(n²) 写法大家都会dp[i] 1; for (int j 1; j i; j) { if (a[j] a[i]) dp[i] max(dp[i], dp[j] 1); }但很少有人问为什么 dp[i] 非要表示“以第 i 个数结尾的 LIS”换成“前 i 个数的 LIS”行不行答案是可以行但转移就不对了。“前 i 个数的 LIS”丢掉了最后一个数的信息你不知道新来的 a[i] 能不能接上去除非再开一维存最后一个数那复杂度就大了。所以 DP 状态设计的核心原则是状态要保留足够的信息支撑转移但也不要冗余地存一堆用不上的信息。我后来遇到很多提高篇的题做的第一步永远是“读题然后写下这个状态到底存了什么必要信息”。比如区间 DP 的 “dp[l][r] 表示区间 l 到 r 的最小合并代价”它就存了区间边界背包问题里的“容量”就是用来支撑“选或不选”的决策信息。状态设计真的是“信息论”不是“套模板”。3.2 从记忆化搜索到递推两种代码风格一种思维《一本通》动态规划章节里有几道题比如“滑雪”用记忆化搜索往往比递推更好写、更好想。我自己的实践建议是任何 DP 题都可以先用记忆化搜索把转移写对再考虑能不能改成递推、怎么改。记忆化搜索写的就是“当前状态我该怎么算”递推是“哪个状态先算出来才能支撑后算出来的”。很多人一上来就套外层 for 内层 for结果是两层循环的嵌套顺序都搞反了。上面那句话听起来简单但真的很多人栽在这。我举个实际的例子如果状态转移是从小的背包容量往大的容量推那外层循环完全是另一套写法。所以我的习惯是永远在代码注释里先写清楚“dp[i][j] 是什么”再写“dp[i][j] 从哪里来”最后才写循环。3.3 题解里最常见的“偷懒”直接给转移方程不讲怎么来的这个我必须吐槽一句。很多流传很广的题解连伪代码都省了就丢一个转移方程然后说“这个显然”。对博主来说显然对读者来说跟天书一样。“转移方程是压缩过的推理不是推倒重来的起点。”一道题做完之后把状态设计的原因和转移的边界条件记下来这才是自己的题解。你在网上抄来的那些代码过一个月再看和第一次看到没任何区别。4. 从一本通题目到ICPC真题迁移的是“思想”而不是“模板”这本书的问题在于它看起来“只适合入门”。有些刷完的人觉得自己的水平只会在模板题里打转看到ICPC/CCPC的题就发怵。我想说的是恰恰相反一本通里反复训练的那些基础思想才是竞赛题里最难替代的东西。4.1 二分答案从“猜数字”到“最小化最大值”《一本通》提高篇里有一类题比如“数列分段”或者“进击的奶牛”要求最小化/最大化某个指标。我第一次看到“把求最值转成判定问题”的时候觉得这思路太绕了放着最值不直接求非要二分个答案去 check。后来刷了ICPC的一些题才发现这是竞赛里极高频的套路。求“最大的最小值”“最小的最大值”很多都是二分答案套一个贪心或 DP 的判定函数。一本通里的那道“数列分段”其实就是训练这个只是题目包装朴素很多读者刷完就忘了里面的结构看到一个包装成“安排飞船座位”或者“划分日程”的题对应不上。怎么训练这种迁移我自己的办法是“给题目换羊头挂狗肉”——做完一道一本通题自己重新编一个背景然后问自己核心模型变了吗没变就说明我抓住了骨架。4.2 贪心的证明邻项交换在几乎所有“排序型贪心”里都会出现贪心章节我当年刷得最开心因为代码短AC起来快。但代码短不代表不需要证明。比如经典的“国王游戏”也许是你自己排的或者是“打水问题”的某种变体思路是排序但为什么按某个关键字排序对很多初学者直接按直觉排序AC 了就过了。可一旦题目别扭一点——比如有多个排序关键字、还涉及高精度计算——没有证明根本不敢写。一本通里其实有一类题把关窍藏在“邻项交换”里假设两个相邻对象 a 和 b如果 a 在前比 b 在前更优就得到一个不等式这个不等式化简之后就是排序规则的来源。我遇到ICPC的“给若干个二元组排序然后计算惩罚值”的题立刻想到的就是邻项交换。这个方法在题解里经常被一句“显然按 xx 排序”带过但你如果没有在一本通里亲手推过一次考场上真不敢用。4.3 前缀和、差分、扫描线这些“小结构”为什么总是藏在难题里《一本通》基础篇的“前缀和”看起来太简单了但它其实是很多高阶题的“底料”。比如二维前缀和可以用来快速求子矩阵和这一招在数论、DP 优化、计数题里到处都是。差分则可以在一段区间上做同样的增量变化在“区间加、单点查”的题目里几乎是标配。后来我刷到一些区域赛的题发现一个很常见的设计是先用某种方式把问题转化成若干个“区间贡献”再用扫描线或者差分把区间贡献累积起来。这类题的题解很喜欢说“做一遍扫描线即可”但扫描线这个思想从哪里来就是从“把一维区间加差分、二维矩形加二维差分”这些基础操作发展出来的。如果一本通的基础结构没形成肌肉记忆考场上根本“扫描”不起来。5. 刷题与看题解的正确姿势我踩过的坑和现在的习惯最后这部分是我最想对刚开始刷《一本通》的读者说的因为方法不对刷多少题都白搭。5.1 只追求“AC”是最大的坑你别笑很多人刷一本通其实就是“对着题解抄代码抄完交上去AC了下一题”。这种行为除了骗自己没有任何提高。题解里真正值钱的是“为什么能想到这个解法”而不是“最终代码长什么样”。我以前也是这样。直到有一次做一道贪心题我完全不知道要排序然后看见题解写了一个“cmp”那一刻我猛然意识到我缺的不是代码是代码背后的观察。从那儿以后我改了策略一道题先自己想15分钟想不出来就看题解但只看一两行关键思路不看完整代码然后合上题解自己写。如果写不出来再回来看思路而不是从头到尾看完。5.2 对拍用暴力程序验证高效程序这个习惯我觉得每个想认真学的人都要尽早养成。做一道数据结构的题你的高效算法可能有个隐蔽的边界 bug这时候写一个暴力版和高效版对拍随机造小数据很快就能发现错误。对拍不复杂一个数据生成器、一个暴力程序、一个高效程序、一个对拍脚本。脚本循环跑每次生成一组小数据两个程序都跑一遍比对输出。小数据跑不出问题之后再上大数据测时间。我在刷一本通提高篇的时候有几道递归和搜索的题就是靠对拍发现“递归边界不对”的光看题解根本看不出来。5.3 建立自己的“题型-模型-入口动作”笔记刷题如果只是刷不归纳那到提高篇后期就会觉得题型千变万化永远刷不完。我自己后来整理了一个笔记每道题记录三样东西这个题的题面是什么、我把它抽象成了什么模型、遇到这个模型的“入口动作”是什么。比如“看到最小化最大值第一个入口动作是想二分答案”、“看到环上的问题想能不能断环成链”、“看到子矩阵和想二维前缀和”。这个笔记不是抄题解是给自己看的“条件反射手册”。一本通里的题虽然基础但正好用来提炼这些入口。后面打比赛的时候看到题面不能马上定位模型就翻开笔记找相似入口。5.4 几句话送给不同阶段的读者如果你刚接触信息学奥赛我建议你先别碰提高篇老老实实把基础篇的枚举、递归、搜索、简单贪心这些章节过一遍每道题都自己写写不出来可以看题解但看完用上面说的方法复现。如果你已经刷完一轮但觉得没收获我建议你挑十道当初没想出来的题重新做一遍看看这次能不能不看题解写出来。如果你已经在打竞赛了我还是建议你偶尔回去把一本通的经典题拿出来“速度复刷”当作热身顺便在笔记里补充新的“入口动作”。我个人现在的习惯是无论多忙每周抽一个晚上从一本通里随机抽一道题限时做做完写一点点过程复盘。这套做法坚持下来对保持“模型感”的帮助比想象中要大得多。题解终究是别人的自己写一遍才能变成自己的。也真心希望这篇内容能让你在看《信息学奥赛一本通》题解的时候不再是一个只会抄答案的人。