OI知识点总结（不拿S 250分不改此名）

目录

• CSP复赛应考策略
  • 一、J组
    • 1.目标分数：350分
    • 2.时间分配
    • 二、S组
    • 1.目标分数：200+分
    • 2.时间分配（按题目难度重新排序）：
  • 三、高难度情况应对方案
  • 四、做题优先级
  • 五、心态
  • 六、避坑指南
• OI学习知识点总结
  • 创作者
  • 建设帮助
  • 算法指导
  • 感谢墙
  • 前言：
  • 更新情况：
    • 2026/4/12
    • 2026/4/14
    • 2026/4/16
    • 2026/4/26
• 动态规划部分
  • 算法简介
  • 动态规划基础
    • 算法介绍
      • 引入
      • 动态规划原理
        • 最优子结构
        • 无后效性
        • 重叠子问题
      • 做题思路
    • 技巧点
  • 记忆化搜索
    • 算法介绍
      • 定义
      • 引入
      • 优化
    • 技巧点
  • 状压 \(\text{DP}\)
    • 算法介绍
      • 引入
      • 算法本质及基础算法讲解
      • 轮廓线
        • 引入
        • 算法过程
    • 技巧点
  • 背包 \(\text{DP}\)
    • 算法介绍
      • 简述
      • 01背包
• 一些零散的技巧
  • 关于最优方案计算

CSP复赛应考策略

一、J组

1.目标分数：350分

具体构成：

• 方案一：100+100+100+50

• 方案二：100+100+90+60

• 方案三：100+100+80+70

  后两题平衡150分+

2.时间分配

8:30~8:20 通读题面并分析

8:40~9:00 T1

9:00~9:20左右 T2

9:20~10:30 T3（对拍）

10:30~11:50 调试题目以及暴力

11:50~12:00 检查

二、S组

1.目标分数：200+分

具体构成：

• 按照难度由简到难，方案一：100+60+20+20

• 方案二：100+40+40+20

2.时间分配（按题目难度重新排序）：

2:30~2:50 通读体面（确定思路方向，思考准确后再打代码，提前整理思路）

2:50~3:50 T1正解+对拍程序

3:50~5:30 从暴力难度和分数平衡后由简到难拿部分分，平均每道题分配30分钟的暴力时间，时间一到强行跳过

5:30~6:20 调试代码

6:20~6:30 检查代码

三、高难度情况应对方案

1. 心理状态调整（稳住别慌）
2. 以部分分为主，不贪图正解

四、做题优先级

1. 简单且有信心实现
   • 确保不丢分，避免低级失误
   • 尽量快速 A 掉，不浪费时间
2. 难但有信心实现
   • 先理清楚思路细节，不要盲目下手
   • 拆分、转化问题，向自己擅长的领域靠拢
3. 简单没有信心实现
   • 想清楚实现细节，不要盲目下手
   • 重点关注数据范围，实时更新策略
4. 难且没有信心实现
   • 快速完成暴力、空出时间给其他性价比高的题目

五、心态

1. 即使考砸也不用有心理负担，再练、再战

2. 战略上藐视它，战术上重视它

3. 我不会的很多人都不会

4. 我已经复习的非常全面了，正常发挥即可

5. 考试只有四道题，比拼的不是知识量，而是谁少犯错、失误

6. 步步为营（增强心理暗示的正反馈）

六、避坑指南

1. 十年\(OI\)一场空，不开\(LongLong\)见祖宗
2. 不要快速决策，先把题想清楚
3. 代码也许是对的，错的也可能是思路
4. 通过上厕所、吃东西等方式放松神经
5. 代码检查项：文件名、时空大小 、注释、Linux下编译环境、输入输出格式、变量类型、多测清空

OI学习知识点总结

作者： By Rylanf
看不到也正常，这是私人 \(OJ\) 的主页。所以在下我也会列出作者以及帮助者的主页（洛谷上的）。

创作者

Rylanf

建设帮助

暂无

算法指导

暂无

感谢墙

暂无

前言：

这是一个 \(OI\) 学习者的算法以及技巧整理，希望有能够帮助到你的地方。这里会包括所有算法，不用担心没有你想要的，如果真的没有，那可以稍等一下，将来一定会有的。（其实是想让你点赞收藏，以后应该是用得到的）
下面的讲解我将会用红、蓝、黑三种颜色标注一些文段， 被红色标注 的代表：知识点、需要着重关注的点； 被蓝色标注 的代表：算法判断、对比判断、总结；被引用了的代表：选学/看（不重要，也有提示的意义）。

这里面的一些题目打不开是正常的，可以在洛谷上按照名字搜，以后都如此，故不再声明。当然，点进我的主页里，看我创建的题目也许能发现这些题~~~ 犹豫作者过于慵懒，所以在洛谷上的自创题目没有测试点，如想验证代码正确性，请把代码私信交给我。 温馨提示：请在浅色模式下使用已获得更加好的食用效果。

这篇文章一直会更新，为了方便一些同学的阅读，所以我会在下面总结概括我的更新情况，具体如下（仅保留近三年的更新）：

更新情况：

2026/4/12

完成 \(\text{DP}\) 算法的部分总结，包括：

1. \(\text{DP}\) 基础。
2. 记忆化搜索以及状压 \(\text{DP}\) 。
3. 背包 \(\text{DP}\)​ 。

2026/4/14

重构讲解板块，将算法讲解分为：算法介绍与关键点联想（俗称技巧点）

继续完成 \(\text{DP}\) 的总结，包括（并未完成）：

1. 区间 \(\text{DP}\)​

2026/4/16

继续完成状压 \(\text{DP}\)​ 与背包的总结。优化了一下观看效果与标注，简化了一下语言表达，使表达简介精炼。

2026/4/26

继续完成 \(\text{DP}\) 与背包的总结。新增了一个“零散技巧”的板块，将来会把这些东西放入专题中。

动态规划部分

算法简介

Followwing text is from the OI Wiki。

本章将介绍介绍动态规划（Dynamic Programming, DP）及其解决的问题、根据其设计的算法及优化．

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法．

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂．

在 \(OI\) 中，计数等非最优化问题的递推解法也常被不规范地称作 \(\text{DP}\)，因此本章将它们一并列出．事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同．

动态规划基础

算法介绍

此主题主要讲述了动态规划的使用方法以及基本思想，其中还有状态定义的思路提示。

引入

一道题目

这是一道非常经典的 \(DP\) 题目，分析如下：

首先，不难想到一个贪心策略，每次从当前点前往这个点的下方、右方中点权较大的那个点。但是这不难看出应该是错误的，因为上面说的策略只能保证前面一段是较优的，但是到了后面可能会错过一些更优的选择。这就是动态规划与贪心的区别——贪心讲究步步最优解，全局最优解。而动态规划则是以局面为一个单位，保证每个局面是最优解的。

详细的讲动态规划：设 \(f_{i,j}\) 表示为点 \((1,1)\) 到点 \((i,j)\) 能够获得的最大价值，假设现在已经得到点 \((i-1,j)\) 与点 \((i,j-1)\) 的 \(f\) 值，那么有\(f_{i,j}=\max \{f_{i-1,j}, f_{i,j-1}\} + val_{i,j}\)。那这样做，我们就可以正确的计算出答案了： \(f_{n,m}\)

回顾一下：我们定义了一个局面——到点 \((i,j)\) 能获得的最大价值。如果观察这条最优路线，能发现一定不存在更优的一条路线使得到原路线其中的任意一个点的总收益更大。这就是具象化的 “局面最优解” 。那么这样有什么好处呢？主要分为一下几点：

1. 成功的缩小了问题范围 。比如上述例题：我们把到点 \((n,m)\) 的最优路线分为了到点 \((n-1,m)\) 与 \((n,m-1)\) 的最优路线加上点 \((n,m)\) 的点权。
2. 因为在动态规划的计算下，每一个局面都是最优解，所以我们只用 \(n \times m\) 的时间复杂度解决点 \((1,1)\) 到点 \((i,j)\) 所能获得的最大收益。这对以后总状态一定，多次子问题询问有着很大的帮助。

上面讲述了动态规划的一个基本思路。而下面要讲述的就是动态规划的特征了。

动态规划原理

能用动态规划解决的问题必须满足三个条件：最优子结构、无后效性和重叠子问题 。这三点是用来判断动态规划的底层逻辑，若题目皆满足则可用动态规划。

以下是三个条件的详细介绍。

最优子结构

注意

如果一道题满足最优子结构，那么它也有可能可以用贪心完成。

简单来说，最优子结构就是全局最优解由子问题最优解推来。如下有一个判断最优子结构以及寻找状态定义的方法（**Some parts are from the "OI Wiki"**）：

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解．你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分 ，每个子问题的解就是它本身的最优解．方法是反证法 ，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾．

子问题图中每个顶点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。可以先把所有需要用到的信息放进局面中，最后再把冗余的信息删除，这样就得到了动态规划的基本定义。 总结：先判断可用信息，再筛选冗余信息

无后效性

可以理解成一个图论问题，把每个局面定义成一个点，把局面与局面之间的关系当成边（注意一定得是有向边），按照如上生成出来的图如果是一个有向无环图，则原问题满足无后效性 。
用更加简洁的话语表示就是：已经求解的子问题，不会再受到后续决策的影响。

重叠子问题

子问题重叠指的是一些最优解的得出会用到许多相同的子问题 。
如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题 ，从而提升效率。

做题思路

用动态规划可以解决的题目一般的思维方式如下 ：

1. 将题目划分为若干个状态、局面或阶段，然后提取出每个局面的特征（或将他用参数描述出来，这称之为 “状态” ）；
2. 寻找每一个状态可能的决策，或者是状态与状态之间转移的公式（用数学语言表达就是 “状态转移方程” ）；
3. 按顺序求解每一个阶段的问题。

如果用图论的角度去理解，就是建出来了一个 "DAG"（有向无环图） ，然后在上面跑一个最短/长路。（不是所有都可以类比）

技巧点

一些简单且常用的模型： H1.5.1.1. 方格取数、H1.5.1.3. 最长不下降序列

我们实现动态规划会用到三种方式：填表、刷表和记忆化搜索。其中记忆化搜索下节会详细讲到。简单地讲，刷表就是对每个状态考虑它可以从哪些状态过来；而填表则是考虑它能够到达那些状态。这两个方式之间不一定可以轻松转换，有时根据题目要求选用合适的实现方式也是非常重要的。

用方格取数举例子：

• 从刷表考虑：对于一个点 \((i,j)\) ，我能从点 \((i-1,j)\) 与点 \((i,j-1)\) 过来。
• 从填表考虑：对于一个点 \((i,j)\) ，我能去到点 \((i+1,j)\) 与点 \((i,j+1)\)​ 。

状态定义的本质：一些充要的条件（且保证充要条件之间不能互相计算得出）。所以定义“状态”的本质就是寻找充要条件并组成一个”状态“，而一些常见的充要条件：枚举层数、限制次数、选与不选、选取物品信息（如编号等）

记忆化搜索

算法介绍

定义

抛去记忆化，他就是纯搜索。记忆化搜索，望文生义，就是有记忆的搜索。在搜索中，我们可能会遇到许多重叠子问题，这时我们就需要用一个数组把这些子问题记录下来，当搜索重复遇到一个状态时我们搜索一次即可。这也是处理重叠子问题的一种方式 。

正因为有记忆，所以我们能够证明且很好证明 每个状态只会计算一次 。综上，他也是一种 常见实现动态规划的方式 。

引入

NOIP 2005 采药

此题显然有一个朴素的 \(\text{DFS}\) 算法，\(\text{DFS}\)​ 包含三个参数：当前是第几个物品、剩余时间为多少、已经获得的价值。然后枚举当前物品选与不选，转移到相应的状态。

优化

但是这个算法的时间复杂度是指数级别的，所以我们需要考虑优化。考虑为什么这个算法会效率低下？因为同种参数组合会经历多次 ，所以使用记忆化搜索才能让时间复杂度正确。

Q：如何使用记忆化搜索优化搜索？

A：

步骤如下：

1. 先把暴力搜索打出来
2. 再使用一个记忆化数组把每个局面记录下来

或者还可以：

1. 先推出状态转移方程
2. 用 \(\text{DFS}\) 实现出来
3. 加上记忆化数组

技巧点

记忆化搜索有两个优于递推版动态规划的地方：面临的局面都是合法的和一些参数可以不用存入 \(\text{DP}\) 数组（存进递归参数） 。但是记忆化搜索也有一个的劣势：只能用刷表的转移式。但又因为面临的局面都是合法的，所以它一般搭配状压 \(\text{DP}\) ，我们会在下一讲讲到。

状压 \(\text{DP}\)

算法介绍

引入

E3.4.1.1. AC Challenge

先思考 \(\text{DP}\)​ 定义，通过题目发现，我们无法通过之前的学习处理“前置任务”这个事情（因为不好描述），描述出来只能把之前经过的点都记录下来。这里提供一个记录方式：用一个 int 类型的数字存 ，这个数字在二进制下的第 \(i\)​ 位标示着第 \(i\)​ 个问题的完成情况 。（对于这题，我们 只在意一个问题是否完成，故 \(0/1\)​ 即可表示，对于其他题目可能需要改变进制）

算法本质及基础算法讲解

其实这是用了一个技巧来表示集合，实质上我们的定义为：完成问题的集合为 \(S\) 能够获得的最大价值。因为 \(n\) 的范围极小 ，所以我们可以把一个集合压缩成一个数字 。这就是状压 \(\text{DP}\)​ ，它的关键是把一个状态压缩成一个可以当作下标的整数 。

状压 \(\text{DP}\) ，遇到的非法状态一般都会非常多 。比如此题：因为有一个前置条件，所以肯定会导致许多状态冗余，这就是状压 \(\text{DP}\) 适合搭配记忆化搜索的原因。同时，在 \(\text{DP}\) 判断合法性的时候可以利用位运算（如果非二进制需自行手打——因为我们是用一个整数压缩集合，在此举一些常用的例子：按位与等于集合交、按位或等于集合并、按位取反等于补集……

更具体的做法：

在 \(\text{DP}\) 当中，判断合法性也需要用此类方法（大多数）。比如此题，用一个数组 \(P_i\) 表示为点 \(i\) 的前置问题，当原有集合 \(S\) 新加入一个点 \(i\) 时可以用按位与（ \(S \cap P_i = P_i\) ）判断是否合法。下面给出代码片段：

ll f(int S) {
	if (vis[S]) return rec[S]; // vis和rec为记忆化数组
	vis[S] = true;

	ll sum = 0;
	for (int i = 0; i < n; i++) {
		if (!((S >> i) & 1) && (P[i] & S) == P[i]) // 利用位运算判断
			sum = max(sum, f(S | (1 << i)) + a[i] * (cnt[S] + 1) + b[i]); // cnt[S]表示为S在二进制下1的个数
	}

	return rec[S] = sum;
}

时间复杂度： \(\Omega(2^NN)\)

轮廓线

引入

E3.4.2.1. 互不侵犯的国王1

这道题目，按照我们上面的学习能够的到一个定义：设 \(f_{i,k,S}\) 表示为第 \(i\) 行国王排列的状态为 \(S\) ，且已经放了 \(k\) 个国王，有多少种排列方案。对于下一行，我们枚举一种国王的排列，最后再判一下合法性，继续往下递归即可。注意：递归中不可以通过放一个参数 \(nk\) 表示还可以放多少个国王去避免 \(\text{DP}\) 中多一个维度 ，这是错误的 。

这里的 \(S\) 与上文有些不一样，它的第 \(i\) 为表示为是否有国王。

但时间复杂度算出来为 \(\Omega(N^52^N)\) ，显然是无法通过时限为 \(50ms\) 。所以我们需要引入一个新的思考方式：轮廓线。

算法过程

技巧点

背包 \(\text{DP}\)

算法介绍

简述

背包虽然可以通过之前学习的内容直接推导，但是任然是一个重要的板块。它能够高效的计算出在一些维度的限制下能够得到的最大价值。当一道题目归纳后出现：在一堆物品中满足限制的选取若干个物品所能得到的最大价值 ，那么就可以考虑背包了。

01背包

01背包问题

抓住充要条件：选取的物品编号与剩余的背包容量 。

可以推断出状态定义： \(f_{i,j}\) 表示前 \(i\) 个物品选后剩余容量为 \(j\) 的最大价值。

考虑现在的状态 \((i,j)\) 能从那些状态推来（也可以变向的考虑现在可以做什么）：

1. 我不选择第 \(i\) 个物品，没有收益：\((i-1,j)\)
2. 我选择第 \(i\) 个物品，有 \(v_i\) 的收益：\((i-1,j-w_i)+v_i\)​

所以，状态转移方程： \(f_{i,j} = \max\{f_{i-1,j},f_{i-1,j-w_i}+v_i \}\)

一些零散的技巧

关于最优方案计算

• 如果一道题是：有 \(k\) 步，每一步可以进行一次操作，求最后最小代价/大收益。那么我们就可以先判断一下操作的顺序是否会影响最终的答案。再通过题目对操作顺序的依赖设计算法。

  因为有些题目明面上有策略选择，但是不管是什么策略最终得到的代价/收益是一样的，这样的性质可以帮助我们简化问题。
  没有顺序选择的方案计算的题目： Atcoder ABC455 F 有顺序的： P1090 NOIP 2004 提高组 合并果子