简介信息学奥赛NOIP作为中学生算法竞赛的核心入口以C为语言载体重点考察算法与数据结构的代码实现能力。其考点分布相对稳定基础算法占比最高动态规划与图论搜索紧随其后理解这些模块的命题逻辑与解题模板是提升竞赛成绩的关键。从原理层面看二分答案、背包DP、区间DP、并查集等经典模型本质上都是对问题规模与状态空间的优化掌握它们不仅能应对赛场题目也能迁移到工程中的复杂逻辑处理。基于历年真题的易错点复盘如数据溢出、二分死循环、读入截断等能够帮助学习者在真实场景中少走弯路。围绕信奥赛考点布局、高频题解与备考节奏这份整理适合备赛学生与竞赛教练参考。1. 信奥赛NOIP考点布局先看清这张分布图再刷题刷了几百道题结果连普及组第二题都卡住——这种情况在信奥赛赛场太常见了。问题不在题量而在很多人根本没弄清NOIP到底考什么。信奥赛全称全国青少年信息学奥林匹克竞赛分区联赛省选国赛都从这里走核心语言是C考的是算法与数据结构的代码实现能力。从历年题目拆开看基础算法模拟、枚举、二分、贪心占40%动态规划占20%图论与搜索占25%剩下的才是数学与字符串处理。这份信奥赛代码合集把四类模块的代码模板和题解按这套比例整理适合正在备赛、想冲一、二等奖的中学生也适合带学生的信息学竞赛老师。下面按考试占比从高到低把高频考点、真题思路和易错点一条条捋清楚能背的模板直接背能练的题直接练。2. 基础算法模块模拟、枚举与二分答案的高频题解2.1 模拟与字符串送分题为什么总翻车模拟题在NOIP里几乎每年都出难度不大却是翻车重灾区。以普及组那道经典字符串题为例给定一行字符串统计其中数字字符的个数。看似简单十个人里有三个人写错问题出在读入环节字符串可能含空格。int n 0; char c; while (scanf(%c, c) ! EOF) { if (c 0 c 9) n; } printf(%d, n);用scanf配%c逐字符读入能完整处理含空格与换行的输入如果换成cin s遇到空格就停后面字符全部漏掉。统计类的模拟题先确认输入流里有空格还是纯单词再决定读入方式。这类题在考场上占分少但丢了就是批次线。合集的模拟模块还整理了字符串替换、日期计算、进制转换几类高频子题它们的共性是状态变量多循环边界容易错答题时先在纸上列清变量名和更新顺序再写码。2.2 二分答案跳石头与最低值最大化二分答案是信奥赛提高组的常客也是区分度所在。以经典题「跳石头」为例河面上有若干石头移除M块后让最短跳跃距离尽可能大。题目问的是最大化最小值直接贪心是错的正确套路是二分这个最短距离再验证可行性。int check(int x) { int cnt 0, last 0; for (int i 1; i n; i) if (a[i] - last x) cnt; else last a[i]; // 保留这块石头 return cnt M; } int l 1, r L; while (l r) { int mid l (r - l 1) / 2; // 向上取整防死循环 if (check(mid)) l mid; // 距离够大试着再大点 else r mid - 1; } printf(%d, l);这类题答题模板固定五要素缺一不可单调的判定函数比如最短距离越大能保留的石头越少边界设成1和总长Lmid取向上取整配合lmid才不死循环答案存最终l加法用long long防溢出。check函数里last记录上一块保留石头位置遇到距离小于x就移除一块。面试官最想听的是你能说出为什么要向上取整因为当区间只有两个数时向下取整会让mid卡在左边界配lmid直接死循环。这套「二分答案贪心验证」的思路不只是跳石头进击的奶牛、数列分段这类题全是同一个套路代码差别只在check函数内部逻辑。2.3 枚举与剪枝暴力里的复杂度意识枚举题看着无脑实际考的是复杂度估算。比如给你一个数列求所有连续子段中满足某种条件的最小长度最容易想到的是两层for枚举起点终点复杂度O(n^2)当n到10^5直接超时。解法是在枚举中加剪枝或改用双指针。实际赛场上遇到这类题先算数据范围对应的量级n1000用O(n^2)n10^5必须优化到O(nlogn)或O(n)。for (int i 0, j 0, sum 0; i n; i) { while (j n sum S) sum a[j]; if (sum S) ans min(ans, j - i); sum - a[i]; // 左端点右移 }这是尺取法的标准写法起点i不动终点j不断右移直到满足条件记录一个答案后把a[i]从总和里减掉i前进。每个元素最多进出一轮总代价就从O(n^2)降到O(n)。剪枝的核心逻辑就一条已经超长的区间不必继续扩展因为继续扩展只会更长直接跳过。把这个「先暴力再剪枝」的思路写熟枚举类中档题基本稳拿。3. 动规优先背包、区间DP与状态设计的高频考点3.1 背包问题采药与货币系统的变体动态规划是信奥赛真正的分水岭模块其中背包又出镜率最高。以「采药」为例给定时间限额T和每种药的采集时间与价值每棵药只能采一次求最大总价值。这就是最标准的01背包n件物品、容量为T、体积是时间、价值是药的价值。模板如下int dp[1005] {0}; for (int i 1; i n; i) for (int j T; j t[i]; j--) dp[j] max(dp[j], dp[j - t[i]] v[i]); printf(%d, dp[T]);两层循环的含义外层遍历物品内层逆序遍历容量。逆序是01背包的关键保证dp[j - t[i]]取自上一件物品没被选过的状态如果正序会出现一件物品被选多次的效果。很多人背模板却说不清逆序原因这在面试或复盘中一问就露馅。记忆技巧是01背包逆序完全背包正序。信奥赛还爱把背包包装成奇怪的形式比如「货币系统」给出一组面额问哪些面额可以被其他面额组合出来。这题表面是数论、核心仍是完全背包设dp[x]表示面额x是否能被当前系统凑出外层循环面额内层正向遍历满足dp[j - coin[i]]为真就把dp[j]置真最后统计无法被凑出的面额个数。这一小节的代码模板配合合集里的变式练习背包类题型基本包圆。3.2 线性与环形DP传球游戏的状态设计传球游戏的题面是这样n个人围成一圈从1号开始传球每次可以传给左边或右边的人求传m次回到1号的不同方案数。状态设计是这类DP的核心考察点。int dp[35][35] {0}; dp[0][1] 1; for (int i 1; i m; i) { for (int j 1; j n; j) { int l (j 1) ? n : j - 1; int r (j n) ? 1 : j 1; dp[i][j] dp[i-1][l] dp[i-1][r]; } } printf(%d, dp[m][1]);dp[i][j]存的是第i次传球后球到j号手里的方案数。l和r是j的左右邻居处理环形边界时1号左边是n号、n号右边是1号这种取模或if判断的边界处理在环形数据结构里反复出现。状态转移讲起来很直白第i次球到j号手里方案数等于上一次在j左邻居手里的方案数加右邻居手里的方案数。这类题的关键区分点是阶段维度传了几次放在外层位置维度放内层。题面稍加改造就变成传成环的线性递推、或是矩阵加速但状态定义永远围绕「第几步、在哪个位置、累计什么值」三要素展开。回答这类题时先讲状态含义再讲转移方向答完这个框架一般连追问都省了。3.3 区间DP与记忆化搜索石子合并的化简套路区间DP是把一个区间作为状态通过枚举分割点合并小区间的结果得出大区间答案典型题是石子合并排成一圈的若干堆石子相邻两堆可以合并代价为两堆重量之和问最大或最小总代价。int dp[305][305]; for (int len 2; len n; len) // 区间长度 for (int i 1; i len - 1 n; i) { // 左端点 int j i len - 1; // 右端点 for (int k i; k j; k) dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum[j] - sum[i-1]); }第一层循环枚举区间长度从2到n这保证计算大区间时所有小区间已被算过是区间DP的固定顺序。内层枚举左端点、再枚举分割点k最后用前缀和sum快速计算合并代价。写成dp[i][j]代表合并第i堆到第j堆的最小代价。配合记忆化搜索写起来更直观solve(i,j)表示合并这个区间的最小代价递归边界是ij返回0状态转移就是枚举k取min。区间DP的难点在于看清题目是不是环是环就先遍历一遍把序列复制成两倍长再用同样的区间DP模板跑。这类题从状态定义、转移方程到复杂度O(n^3)都能完整说出来基本就是满分回答。3.4 真题实测挖地雷与DAG最长路挖地雷是普及组常考的DP题型一座山上有编号1到n的地窖每个地窖有一定数量的地雷地窖间存在单向通道规定只能从编号小的地窖走到大的求从任意地窖出发最多能挖到的地雷数和对应路径。这其实是DAG上的最长路问题。int ans 0, start 1; for (int i 1; i n; i) { for (int j 1; j i; j) { if (conn[j][i] f[j] a[i] f[i]) { f[i] f[j] a[i]; pre[i] j; } } if (f[i] ans) { ans f[i]; start i; } }f[i]记录到i号地窖为止能挖到的最大地雷数pre[i]记录最优方案中i的前驱节点用于最后从start向前回溯打印路径。因为通道只能从小号到大号天然无环所以按编号顺序递推即可这也是DAG最长路比最短路好写的原因不用Dijkstra也不用Bellman-Ford一层循环搞定。输出路径时从终点start开始顺着pre一路走回起点倒序输出就成。信奥赛对这种动态规划加上路径输出的组合题偏爱有加因为既考状态设计又考对前置状态存储的使用。实际考场里路径输出写成数组、递归、栈三种方式都行最推递归输出代码最短。4. 图论与搜索DFS/BFS、最短路与并查集的实战题解4.1 搜索题的三个必背常数优化搜索题从迷宫寻路到数独求解DFS和BFS两大框架几乎不缺席。很多题目本身不难难点全在剪枝和常数优化上任何一步漏了都会从AC变成TLE。三个必背优化如下。int vis[105][105]; int dx[4] {1,-1,0,0}, dy[4] {0,0,1,-1}; void dfs(int x, int y, int step) { if (step best) return; // 最优性剪枝 if (x tx y ty) { best step; return; } for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 1 nx n ny 1 ny m !vis[nx][ny] mp[nx][ny] ! #) { vis[nx][ny] 1; dfs(nx, ny, step 1);vis[nx][ny] 0; } } }第一个优化是方向数组dx/dy比if四连判断速度快且不易写错第二个优化是最优性剪枝搜索到当前点消费的步数已经不小于已知最优值时这个分支直接砍掉在求最短路的搜索里收益巨大第三个优化是访问标记vis的撤销时机回溯时必须复原否则虽避免重复却丢失了其他路径的探索机会。BFS与DFS解题边界的判断求最短路径用BFS层级天然递增判断是否存在解、枚举所有方案用DFS。对DFS这类题面试官常追问入口边界答案是入队或进入函数前把起点vis打上标记防止起点被再次访问这是初学者最容易漏的一行。4.2 并查集路径压缩与按秩合并并查集看似简单却是图论模块的保底分来源尤其擅长处理「若干个点分属几个连通块」和「判断两点是否连通」两类问题。经典真题「关押罪犯」是二分答案加并查集的组合题有若干对罪犯有恩怨值把罪犯分到两个监狱要求最大怨气值最小化。思路是二分这个最大怨气值根据配对关系用并查集检查是否可行。int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unionSet(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; }unionSet合并时如果不做按秩合并极端情况会退化成一条链导致find变慢比赛中一般路径压缩已经够用想更稳就加一个rank数组记录树高始终把小树挂到大树下。关押罪犯的完整逻辑是二分最大怨气值limit把怨气大于limit的每对罪犯放入不同监狱用并查集表示「敌对关系」——每个罪犯拆成两个节点i和ina和b有冲突就把a与bn合并、b与an合并当出现a与an在同一个集合就说明无法安排此时调大limit。并查集常与二分答案绑定的原因在于check函数天然对集合的合并拆分有需求而并查集能在近乎O(1)时间内完成这些集合操作。能把这个组合思路复述清楚并查集这部分就稳了。4.3 最短路与拓扑排序场景选择大于模板背诵最短路问题年年有但考法灵活有的直接给图求最短路径有的需要先建图再处理。n很小几百用Floyd的O(n^3)三重循环n大但边权非负用Dijkstra堆优化版本是标配边权存在负数时Dijkstra失效改用Bellman-Ford或SPFA。考场判断最短路算法的依据不是题目难度而是数据规模。Dijkstra堆优化模板里有一个高频易错点加入堆时的pair顺序必须让距离在前、节点编号在后否则排序的优先级反了导致出堆的不是距离最小的节点。while (!pq.empty()) { pii cur pq.top(); pq.pop(); int d cur.first, u cur.second; if (d ! dist[u]) continue; for (auto e : G[u]) if (dist[e.v] d e.w) { dist[e.v] d e.w; pq.push({dist[e.v], e.v}); } }if (d ! dist[u])这行懒删除标记是最容易漏的一个节点可能被多次入堆旧记录出堆时直接跳过配合vis数组二选一即可少写会平白多出一大截常数。拓扑排序则常以「做某事前必须完成若干前置任务」的形式出现Kahn算法维护BFS队列入度为0的节点依次出队并减少后继入度。考前把Dijkstra和拓扑排序两个模板默写三遍笔误在考场上是玄学问题但模板熟能降低概率。4.4 真题实测矩阵搜索与链表模拟搜索和模拟结合的题目在历届比赛中不少见。一个典型题目是给定一个矩阵某些格子是墙从起点到终点恰好走k步有多少种走法。BFS按步数分层但步数k在10^9量时要用矩阵快速幂优化状态转移而k只有1000时简单DP更好写。矩阵快速幂建的是邻接矩阵MM[i][j]1表示i到j有边走k步的路径数就是M^k的对应元素。这类题核心难点不在模板而在识别看见「恰好走k步」「路径条数」就应想到用DP或邻接矩阵的幂而不是硬套BFS。链表模拟的典型是约瑟夫环问题n个人围成一圈按1到m报数数到m的人出列问最后一个出列的人的编号。递推公式f(n,m)(f(n-1,m)m)%nO(n)搞定考场里别真的写链表去模拟每轮删一个点是O(nm)n一大直接超时。搜索、模拟、数学递推三类解法摆在一起能训练出「先看数据范围再定解法」的赛场习惯。5. 信奥赛失分点与易错五类最常见翻车现场5.1 数据范围爆炸long long并不是万灵丹错在哪两个10^5量级的int相乘得到10^10直接溢出变成负数最终答案错得离谱。为什么错NOIP题目数据范围经常卡在10^9以上很多同学只在最终答案是long long时开long long中间运算过程却用的是int临时变量乘法溢出发生在赋值之前。怎么答对一开始就按数据范围预估最大中间值凡是涉及乘法或累加的一律写long long读入时如果题目明确说有10^9以上的数scanf用%lldprintf也要匹配%lld%d和%lld混用会导致输出错乱。养成习惯是开数组前先算一遍最大值的量级写在注释里这个习惯比任何模板都值钱。5.2 二分死循环mid取整方向与区间更新不配套错在哪while(l r)循环里写出int mid (l r) / 2当l和r相差1时mid等于l又配上l mid区间永远不变程序死循环。为什么错向下取整配左移型更新lmid是最经典的死循环组合。区间只剩两个数时mid落到左端点检查后如果走lmid新区间还是[l, r]白绕一圈。怎么答对两个模板分别记死。求最小值最大用mid l (r - l 1) / 2配l mid求最大值最小用mid l (r - l) / 2配r mid。写完后脑内模拟一遍只剩两个数的情况确保区间一定收缩。l (r - l) / 2的写法同时防了(lr)的int溢出一举两得。5.3 数组越界与编号习惯错在哪数组开成n5却在循环里访问下标a[n1]或者n100000时只开100000容量的数组最后一个元素写到a[n]直接越界。为什么错信奥赛数组普遍从1开始编号循环用到i n存储容量必须n5起步。很多题目还需要0号元素做哨兵或前缀和起点容量只会更大。越界不报错时结果随机报错就是RE丢分最冤。怎么答对无脑开成全局数组大小比题目上限多5到10个不用局部数组栈空间不够凡是涉及前缀和、差分、邻接表头数组下标从0和1哪个顺手就用哪个但全篇必须统一不准混用。5.4 读入坑换行符与字符串空格错在哪cin s读一个单词可题目里字符串含空格读入就截断了。用scanf(%s)同样踩坑接下来所有字符偏移一位后面全错。为什么错和%s按空白符分隔遇到空格是天然截断信号。题目里「一行字符串可能包含空格」这句描述出现就必须换读入方案。怎么答对C选手用getline(cin, s)读整行注意如果在它之前用过cin n要先getchar()或cin.ignore()把上一行行尾的换行符吃掉C选手用fgets或者while配合scanf(%c, c)逐字符处理。五个字符以内的小字符串处理怎么读都行但一涉及整行先想换行符再写代码。5.5 DP初值与状态维度错位错在哪求方案数的DP初值设成dp[0]0而不是dp[0]1或者从上到下的搜索型DP缺少记忆化数组的初始判断结果第一层就全错。为什么错初值表达的是「什么都不做的时候有多少种方案」。没有任何物品、传0次球都在原地理应是一种方案写成0则所有状态都变0。搜索型DP若记忆化数组默认0和真实答案0冲突每次都会重复算。怎么答对方案数DP一律问两个问题——空状态下是0还是1目标状态是数组的哪个位置背包方案数、路径方案数、传球方案数起始状态全是dp[0][0]1或dp[0][1]1。记忆化搜索就单独用一个vis数组标记是否已算过初始置0算过后置1避免和答案0混淆。6. 最后半年的信奥赛备考节奏刷题梯度、对拍调试与押题方向6.1 三分法刷题把时间分给产出最高的地方如果你的目标是普及组一等时间分配建议是五成给基础算法与模拟、三成给DP、两成给搜索和图论冲刺提高组则反过来DP和图论占六成。刷题不要按难度乱跳按模块刷完一个再换下一个每个模块先刷10道入门题建立模板记忆再刷5道真题检验最后回到错题本重做一遍。从我开始带学生起发现按模块刷比随机刷效率高至少一倍前者是构建知识网络后者只是在碰运气。6.2 对拍脚本用一份小数据找出所有逻辑错血泪经验告诉我交上去WA的题90%靠对拍才能查出来。准备一个几千行的小数据生成器写完正解后和暴力的朴素算法跑同样的随机数据输出不一致就说明正解有隐性bug。一个最小可用对拍脚本比任何调试器都直观for i in $(seq 1 1000); do ./data input.txt ./std input.txt out1.txt ./force input.txt out2.txt if diff out1.txt out2.txt; then echo pass $i else echo fail case $i; break fi donedata生成器负责产出随机小规模数据std是待查解force是保证正确的暴力解。实际做的时候先生成n不超过10的小数据让暴力解能在毫秒级跑完再逐步调大数据量检查超时问题。考场写不出对拍脚本没关系但平时训练必须跑因为自己造的样例永远覆盖不到边界情况。6.3 押题方向近三年趋势与今年重点从近几年的题目走向看纯模板背写类题在减少组合型题在增多最常见的是二分答案套贪心检验、并查集套二分、DP套路径输出。押题可以盯三个方向字符串处理与排序的结合原题率极高区间DP的合并模型几乎每年在提高组出现一次以及最短路加二分答案的双重嵌套题。考前两周不要再碰新题把错题本里的题按「数据范围爆掉」「边界写错」「读入错误」三类各过一遍比刷十套新题更有用。从那以后我每次带备赛班都强制学生赛前留三天时间只干一件事把之前所有错题的易错点写在十张卡片上进考场前只看卡片。这套路已经让不少人稳稳守住该拿的分。希望帮到你。本文还有配套的精品资源点击获取
简介信息学奥赛NOIP作为中学生算法竞赛的核心入口以C为语言载体重点考察算法与数据结构的代码实现能力。其考点分布相对稳定基础算法占比最高动态规划与图论搜索紧随其后理解这些模块的命题逻辑与解题模板是提升竞赛成绩的关键。从原理层面看二分答案、背包DP、区间DP、并查集等经典模型本质上都是对问题规模与状态空间的优化掌握它们不仅能应对赛场题目也能迁移到工程中的复杂逻辑处理。基于历年真题的易错点复盘如数据溢出、二分死循环、读入截断等能够帮助学习者在真实场景中少走弯路。围绕信奥赛考点布局、高频题解与备考节奏这份整理适合备赛学生与竞赛教练参考。1. 信奥赛NOIP考点布局先看清这张分布图再刷题刷了几百道题结果连普及组第二题都卡住——这种情况在信奥赛赛场太常见了。问题不在题量而在很多人根本没弄清NOIP到底考什么。信奥赛全称全国青少年信息学奥林匹克竞赛分区联赛省选国赛都从这里走核心语言是C考的是算法与数据结构的代码实现能力。从历年题目拆开看基础算法模拟、枚举、二分、贪心占40%动态规划占20%图论与搜索占25%剩下的才是数学与字符串处理。这份信奥赛代码合集把四类模块的代码模板和题解按这套比例整理适合正在备赛、想冲一、二等奖的中学生也适合带学生的信息学竞赛老师。下面按考试占比从高到低把高频考点、真题思路和易错点一条条捋清楚能背的模板直接背能练的题直接练。2. 基础算法模块模拟、枚举与二分答案的高频题解2.1 模拟与字符串送分题为什么总翻车模拟题在NOIP里几乎每年都出难度不大却是翻车重灾区。以普及组那道经典字符串题为例给定一行字符串统计其中数字字符的个数。看似简单十个人里有三个人写错问题出在读入环节字符串可能含空格。int n 0; char c; while (scanf(%c, c) ! EOF) { if (c 0 c 9) n; } printf(%d, n);用scanf配%c逐字符读入能完整处理含空格与换行的输入如果换成cin s遇到空格就停后面字符全部漏掉。统计类的模拟题先确认输入流里有空格还是纯单词再决定读入方式。这类题在考场上占分少但丢了就是批次线。合集的模拟模块还整理了字符串替换、日期计算、进制转换几类高频子题它们的共性是状态变量多循环边界容易错答题时先在纸上列清变量名和更新顺序再写码。2.2 二分答案跳石头与最低值最大化二分答案是信奥赛提高组的常客也是区分度所在。以经典题「跳石头」为例河面上有若干石头移除M块后让最短跳跃距离尽可能大。题目问的是最大化最小值直接贪心是错的正确套路是二分这个最短距离再验证可行性。int check(int x) { int cnt 0, last 0; for (int i 1; i n; i) if (a[i] - last x) cnt; else last a[i]; // 保留这块石头 return cnt M; } int l 1, r L; while (l r) { int mid l (r - l 1) / 2; // 向上取整防死循环 if (check(mid)) l mid; // 距离够大试着再大点 else r mid - 1; } printf(%d, l);这类题答题模板固定五要素缺一不可单调的判定函数比如最短距离越大能保留的石头越少边界设成1和总长Lmid取向上取整配合lmid才不死循环答案存最终l加法用long long防溢出。check函数里last记录上一块保留石头位置遇到距离小于x就移除一块。面试官最想听的是你能说出为什么要向上取整因为当区间只有两个数时向下取整会让mid卡在左边界配lmid直接死循环。这套「二分答案贪心验证」的思路不只是跳石头进击的奶牛、数列分段这类题全是同一个套路代码差别只在check函数内部逻辑。2.3 枚举与剪枝暴力里的复杂度意识枚举题看着无脑实际考的是复杂度估算。比如给你一个数列求所有连续子段中满足某种条件的最小长度最容易想到的是两层for枚举起点终点复杂度O(n^2)当n到10^5直接超时。解法是在枚举中加剪枝或改用双指针。实际赛场上遇到这类题先算数据范围对应的量级n1000用O(n^2)n10^5必须优化到O(nlogn)或O(n)。for (int i 0, j 0, sum 0; i n; i) { while (j n sum S) sum a[j]; if (sum S) ans min(ans, j - i); sum - a[i]; // 左端点右移 }这是尺取法的标准写法起点i不动终点j不断右移直到满足条件记录一个答案后把a[i]从总和里减掉i前进。每个元素最多进出一轮总代价就从O(n^2)降到O(n)。剪枝的核心逻辑就一条已经超长的区间不必继续扩展因为继续扩展只会更长直接跳过。把这个「先暴力再剪枝」的思路写熟枚举类中档题基本稳拿。3. 动规优先背包、区间DP与状态设计的高频考点3.1 背包问题采药与货币系统的变体动态规划是信奥赛真正的分水岭模块其中背包又出镜率最高。以「采药」为例给定时间限额T和每种药的采集时间与价值每棵药只能采一次求最大总价值。这就是最标准的01背包n件物品、容量为T、体积是时间、价值是药的价值。模板如下int dp[1005] {0}; for (int i 1; i n; i) for (int j T; j t[i]; j--) dp[j] max(dp[j], dp[j - t[i]] v[i]); printf(%d, dp[T]);两层循环的含义外层遍历物品内层逆序遍历容量。逆序是01背包的关键保证dp[j - t[i]]取自上一件物品没被选过的状态如果正序会出现一件物品被选多次的效果。很多人背模板却说不清逆序原因这在面试或复盘中一问就露馅。记忆技巧是01背包逆序完全背包正序。信奥赛还爱把背包包装成奇怪的形式比如「货币系统」给出一组面额问哪些面额可以被其他面额组合出来。这题表面是数论、核心仍是完全背包设dp[x]表示面额x是否能被当前系统凑出外层循环面额内层正向遍历满足dp[j - coin[i]]为真就把dp[j]置真最后统计无法被凑出的面额个数。这一小节的代码模板配合合集里的变式练习背包类题型基本包圆。3.2 线性与环形DP传球游戏的状态设计传球游戏的题面是这样n个人围成一圈从1号开始传球每次可以传给左边或右边的人求传m次回到1号的不同方案数。状态设计是这类DP的核心考察点。int dp[35][35] {0}; dp[0][1] 1; for (int i 1; i m; i) { for (int j 1; j n; j) { int l (j 1) ? n : j - 1; int r (j n) ? 1 : j 1; dp[i][j] dp[i-1][l] dp[i-1][r]; } } printf(%d, dp[m][1]);dp[i][j]存的是第i次传球后球到j号手里的方案数。l和r是j的左右邻居处理环形边界时1号左边是n号、n号右边是1号这种取模或if判断的边界处理在环形数据结构里反复出现。状态转移讲起来很直白第i次球到j号手里方案数等于上一次在j左邻居手里的方案数加右邻居手里的方案数。这类题的关键区分点是阶段维度传了几次放在外层位置维度放内层。题面稍加改造就变成传成环的线性递推、或是矩阵加速但状态定义永远围绕「第几步、在哪个位置、累计什么值」三要素展开。回答这类题时先讲状态含义再讲转移方向答完这个框架一般连追问都省了。3.3 区间DP与记忆化搜索石子合并的化简套路区间DP是把一个区间作为状态通过枚举分割点合并小区间的结果得出大区间答案典型题是石子合并排成一圈的若干堆石子相邻两堆可以合并代价为两堆重量之和问最大或最小总代价。int dp[305][305]; for (int len 2; len n; len) // 区间长度 for (int i 1; i len - 1 n; i) { // 左端点 int j i len - 1; // 右端点 for (int k i; k j; k) dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum[j] - sum[i-1]); }第一层循环枚举区间长度从2到n这保证计算大区间时所有小区间已被算过是区间DP的固定顺序。内层枚举左端点、再枚举分割点k最后用前缀和sum快速计算合并代价。写成dp[i][j]代表合并第i堆到第j堆的最小代价。配合记忆化搜索写起来更直观solve(i,j)表示合并这个区间的最小代价递归边界是ij返回0状态转移就是枚举k取min。区间DP的难点在于看清题目是不是环是环就先遍历一遍把序列复制成两倍长再用同样的区间DP模板跑。这类题从状态定义、转移方程到复杂度O(n^3)都能完整说出来基本就是满分回答。3.4 真题实测挖地雷与DAG最长路挖地雷是普及组常考的DP题型一座山上有编号1到n的地窖每个地窖有一定数量的地雷地窖间存在单向通道规定只能从编号小的地窖走到大的求从任意地窖出发最多能挖到的地雷数和对应路径。这其实是DAG上的最长路问题。int ans 0, start 1; for (int i 1; i n; i) { for (int j 1; j i; j) { if (conn[j][i] f[j] a[i] f[i]) { f[i] f[j] a[i]; pre[i] j; } } if (f[i] ans) { ans f[i]; start i; } }f[i]记录到i号地窖为止能挖到的最大地雷数pre[i]记录最优方案中i的前驱节点用于最后从start向前回溯打印路径。因为通道只能从小号到大号天然无环所以按编号顺序递推即可这也是DAG最长路比最短路好写的原因不用Dijkstra也不用Bellman-Ford一层循环搞定。输出路径时从终点start开始顺着pre一路走回起点倒序输出就成。信奥赛对这种动态规划加上路径输出的组合题偏爱有加因为既考状态设计又考对前置状态存储的使用。实际考场里路径输出写成数组、递归、栈三种方式都行最推递归输出代码最短。4. 图论与搜索DFS/BFS、最短路与并查集的实战题解4.1 搜索题的三个必背常数优化搜索题从迷宫寻路到数独求解DFS和BFS两大框架几乎不缺席。很多题目本身不难难点全在剪枝和常数优化上任何一步漏了都会从AC变成TLE。三个必背优化如下。int vis[105][105]; int dx[4] {1,-1,0,0}, dy[4] {0,0,1,-1}; void dfs(int x, int y, int step) { if (step best) return; // 最优性剪枝 if (x tx y ty) { best step; return; } for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 1 nx n ny 1 ny m !vis[nx][ny] mp[nx][ny] ! #) { vis[nx][ny] 1; dfs(nx, ny, step 1);vis[nx][ny] 0; } } }第一个优化是方向数组dx/dy比if四连判断速度快且不易写错第二个优化是最优性剪枝搜索到当前点消费的步数已经不小于已知最优值时这个分支直接砍掉在求最短路的搜索里收益巨大第三个优化是访问标记vis的撤销时机回溯时必须复原否则虽避免重复却丢失了其他路径的探索机会。BFS与DFS解题边界的判断求最短路径用BFS层级天然递增判断是否存在解、枚举所有方案用DFS。对DFS这类题面试官常追问入口边界答案是入队或进入函数前把起点vis打上标记防止起点被再次访问这是初学者最容易漏的一行。4.2 并查集路径压缩与按秩合并并查集看似简单却是图论模块的保底分来源尤其擅长处理「若干个点分属几个连通块」和「判断两点是否连通」两类问题。经典真题「关押罪犯」是二分答案加并查集的组合题有若干对罪犯有恩怨值把罪犯分到两个监狱要求最大怨气值最小化。思路是二分这个最大怨气值根据配对关系用并查集检查是否可行。int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unionSet(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; }unionSet合并时如果不做按秩合并极端情况会退化成一条链导致find变慢比赛中一般路径压缩已经够用想更稳就加一个rank数组记录树高始终把小树挂到大树下。关押罪犯的完整逻辑是二分最大怨气值limit把怨气大于limit的每对罪犯放入不同监狱用并查集表示「敌对关系」——每个罪犯拆成两个节点i和ina和b有冲突就把a与bn合并、b与an合并当出现a与an在同一个集合就说明无法安排此时调大limit。并查集常与二分答案绑定的原因在于check函数天然对集合的合并拆分有需求而并查集能在近乎O(1)时间内完成这些集合操作。能把这个组合思路复述清楚并查集这部分就稳了。4.3 最短路与拓扑排序场景选择大于模板背诵最短路问题年年有但考法灵活有的直接给图求最短路径有的需要先建图再处理。n很小几百用Floyd的O(n^3)三重循环n大但边权非负用Dijkstra堆优化版本是标配边权存在负数时Dijkstra失效改用Bellman-Ford或SPFA。考场判断最短路算法的依据不是题目难度而是数据规模。Dijkstra堆优化模板里有一个高频易错点加入堆时的pair顺序必须让距离在前、节点编号在后否则排序的优先级反了导致出堆的不是距离最小的节点。while (!pq.empty()) { pii cur pq.top(); pq.pop(); int d cur.first, u cur.second; if (d ! dist[u]) continue; for (auto e : G[u]) if (dist[e.v] d e.w) { dist[e.v] d e.w; pq.push({dist[e.v], e.v}); } }if (d ! dist[u])这行懒删除标记是最容易漏的一个节点可能被多次入堆旧记录出堆时直接跳过配合vis数组二选一即可少写会平白多出一大截常数。拓扑排序则常以「做某事前必须完成若干前置任务」的形式出现Kahn算法维护BFS队列入度为0的节点依次出队并减少后继入度。考前把Dijkstra和拓扑排序两个模板默写三遍笔误在考场上是玄学问题但模板熟能降低概率。4.4 真题实测矩阵搜索与链表模拟搜索和模拟结合的题目在历届比赛中不少见。一个典型题目是给定一个矩阵某些格子是墙从起点到终点恰好走k步有多少种走法。BFS按步数分层但步数k在10^9量时要用矩阵快速幂优化状态转移而k只有1000时简单DP更好写。矩阵快速幂建的是邻接矩阵MM[i][j]1表示i到j有边走k步的路径数就是M^k的对应元素。这类题核心难点不在模板而在识别看见「恰好走k步」「路径条数」就应想到用DP或邻接矩阵的幂而不是硬套BFS。链表模拟的典型是约瑟夫环问题n个人围成一圈按1到m报数数到m的人出列问最后一个出列的人的编号。递推公式f(n,m)(f(n-1,m)m)%nO(n)搞定考场里别真的写链表去模拟每轮删一个点是O(nm)n一大直接超时。搜索、模拟、数学递推三类解法摆在一起能训练出「先看数据范围再定解法」的赛场习惯。5. 信奥赛失分点与易错五类最常见翻车现场5.1 数据范围爆炸long long并不是万灵丹错在哪两个10^5量级的int相乘得到10^10直接溢出变成负数最终答案错得离谱。为什么错NOIP题目数据范围经常卡在10^9以上很多同学只在最终答案是long long时开long long中间运算过程却用的是int临时变量乘法溢出发生在赋值之前。怎么答对一开始就按数据范围预估最大中间值凡是涉及乘法或累加的一律写long long读入时如果题目明确说有10^9以上的数scanf用%lldprintf也要匹配%lld%d和%lld混用会导致输出错乱。养成习惯是开数组前先算一遍最大值的量级写在注释里这个习惯比任何模板都值钱。5.2 二分死循环mid取整方向与区间更新不配套错在哪while(l r)循环里写出int mid (l r) / 2当l和r相差1时mid等于l又配上l mid区间永远不变程序死循环。为什么错向下取整配左移型更新lmid是最经典的死循环组合。区间只剩两个数时mid落到左端点检查后如果走lmid新区间还是[l, r]白绕一圈。怎么答对两个模板分别记死。求最小值最大用mid l (r - l 1) / 2配l mid求最大值最小用mid l (r - l) / 2配r mid。写完后脑内模拟一遍只剩两个数的情况确保区间一定收缩。l (r - l) / 2的写法同时防了(lr)的int溢出一举两得。5.3 数组越界与编号习惯错在哪数组开成n5却在循环里访问下标a[n1]或者n100000时只开100000容量的数组最后一个元素写到a[n]直接越界。为什么错信奥赛数组普遍从1开始编号循环用到i n存储容量必须n5起步。很多题目还需要0号元素做哨兵或前缀和起点容量只会更大。越界不报错时结果随机报错就是RE丢分最冤。怎么答对无脑开成全局数组大小比题目上限多5到10个不用局部数组栈空间不够凡是涉及前缀和、差分、邻接表头数组下标从0和1哪个顺手就用哪个但全篇必须统一不准混用。5.4 读入坑换行符与字符串空格错在哪cin s读一个单词可题目里字符串含空格读入就截断了。用scanf(%s)同样踩坑接下来所有字符偏移一位后面全错。为什么错和%s按空白符分隔遇到空格是天然截断信号。题目里「一行字符串可能包含空格」这句描述出现就必须换读入方案。怎么答对C选手用getline(cin, s)读整行注意如果在它之前用过cin n要先getchar()或cin.ignore()把上一行行尾的换行符吃掉C选手用fgets或者while配合scanf(%c, c)逐字符处理。五个字符以内的小字符串处理怎么读都行但一涉及整行先想换行符再写代码。5.5 DP初值与状态维度错位错在哪求方案数的DP初值设成dp[0]0而不是dp[0]1或者从上到下的搜索型DP缺少记忆化数组的初始判断结果第一层就全错。为什么错初值表达的是「什么都不做的时候有多少种方案」。没有任何物品、传0次球都在原地理应是一种方案写成0则所有状态都变0。搜索型DP若记忆化数组默认0和真实答案0冲突每次都会重复算。怎么答对方案数DP一律问两个问题——空状态下是0还是1目标状态是数组的哪个位置背包方案数、路径方案数、传球方案数起始状态全是dp[0][0]1或dp[0][1]1。记忆化搜索就单独用一个vis数组标记是否已算过初始置0算过后置1避免和答案0混淆。6. 最后半年的信奥赛备考节奏刷题梯度、对拍调试与押题方向6.1 三分法刷题把时间分给产出最高的地方如果你的目标是普及组一等时间分配建议是五成给基础算法与模拟、三成给DP、两成给搜索和图论冲刺提高组则反过来DP和图论占六成。刷题不要按难度乱跳按模块刷完一个再换下一个每个模块先刷10道入门题建立模板记忆再刷5道真题检验最后回到错题本重做一遍。从我开始带学生起发现按模块刷比随机刷效率高至少一倍前者是构建知识网络后者只是在碰运气。6.2 对拍脚本用一份小数据找出所有逻辑错血泪经验告诉我交上去WA的题90%靠对拍才能查出来。准备一个几千行的小数据生成器写完正解后和暴力的朴素算法跑同样的随机数据输出不一致就说明正解有隐性bug。一个最小可用对拍脚本比任何调试器都直观for i in $(seq 1 1000); do ./data input.txt ./std input.txt out1.txt ./force input.txt out2.txt if diff out1.txt out2.txt; then echo pass $i else echo fail case $i; break fi donedata生成器负责产出随机小规模数据std是待查解force是保证正确的暴力解。实际做的时候先生成n不超过10的小数据让暴力解能在毫秒级跑完再逐步调大数据量检查超时问题。考场写不出对拍脚本没关系但平时训练必须跑因为自己造的样例永远覆盖不到边界情况。6.3 押题方向近三年趋势与今年重点从近几年的题目走向看纯模板背写类题在减少组合型题在增多最常见的是二分答案套贪心检验、并查集套二分、DP套路径输出。押题可以盯三个方向字符串处理与排序的结合原题率极高区间DP的合并模型几乎每年在提高组出现一次以及最短路加二分答案的双重嵌套题。考前两周不要再碰新题把错题本里的题按「数据范围爆掉」「边界写错」「读入错误」三类各过一遍比刷十套新题更有用。从那以后我每次带备赛班都强制学生赛前留三天时间只干一件事把之前所有错题的易错点写在十张卡片上进考场前只看卡片。这套路已经让不少人稳稳守住该拿的分。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
