CSP-J复赛|常用代码模板复习手册
- 2026-10-13 04:33:54
CSP-J 复赛代码模板
考前复习代码，需要确认三件事：模板在什么条件下成立，状态或区间表示什么，边界怎样处理。
例如，同样是区间和，静态查询可以用前缀和；区间加法、最后统一求值可以用差分。数组含负数时，“和过大就移动左端点”的双指针做法可能失效。背包容量从大到小枚举与从小到大枚举，只差一个方向，物品的使用次数就变了。
这份手册按 CSP-J 复赛复习场景整理：基础操作与数据处理、枚举与搜索、数论与高精度、贪心与动态规划。范围参考《NOI 大纲（2025 年修订版）》入门级；具体例题和复习顺序是本文的安排，不代表当年命题预测。
代码统一采用 C++14。除完整程序外，其余代码为局部片段：共用头文件与 ll 别名，变量含义在相邻文字中说明。各段独立使用，不将整篇代码直接拼成一个程序。
先从数据规模判断做法
枚举所有子集有 
种选择，枚举排列有 
种；两重循环通常是 
，三重区间转移通常是 
。遇到十万规模的数据，不能照搬平方 DP；遇到数位上千的大整数，也不能把竖式乘法当作线性算法。
复杂度要把状态数、每个状态的转移数、单次转移代价一起计算。背包的容量上界也参与复杂度，数值很大时，物品少并不代表容量 DP 可行。内存同样先算元素个数：一个 
的 long long 矩阵仅数据就约占 32 MB，多开几个同规模数组会继续累加。
01｜程序骨架与基础操作
完整程序：先检查类型与初始化
下面的程序读入若干整数并输出总和，可作为本地练习的程序骨架。计数器、累加器和答案变量都明确初始化。
#include<bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; ll ans = 0; for (int i = 1; i <= n; i++) { ll x; cin >> x; ans += x; } cout << ans << '\n'; return 0;}ll ans = a * b; 不会让两个 int 的乘法自动变成 64 位运算。应写成 ll ans = 1LL * a * b;，并确认最终结果没有超过 long long 的范围。数组值能用 int，不代表区间和、方案数与乘积也能用 int。
文件输入输出以题面要求为准。题面要求读写 task.in、task.out 时，在 main 开头使用以下两句；task 必须替换为题面指定的名字。标准输入输出题不添加重定向。
freopen("task.in", "r", stdin);freopen("task.out", "w", stdout);关闭流同步后，本篇统一使用 cin/cout，不混用 scanf/printf。有返回值的函数，每条正常执行路径都要返回对应类型的值；数组、容器和每组测试的状态要按实际需要重新初始化。
排序、去重与查找
a 为从下标 0 开始的 vector<int>，x 为查询值。排序后去重，再查询第一个不小于 x、第一个大于 x 的位置：
sort(a.begin(), a.end());a.erase(unique(a.begin(), a.end()), a.end());int l = lower_bound(a.begin(), a.end(), x) - a.begin();int r = upper_bound(a.begin(), a.end(), x) - a.begin();bool ok = l < (int)a.size() && a[l] == x;cout << ok << '\n';排序耗时 
；一次二分查找耗时 
。unique 只处理相邻重复项，返回的是新的逻辑结尾；没有 erase，容器长度不会缩短。需要统计原数组中 x 的出现次数时，在去重前计算 r - l。
查找函数返回 end() 是正常情况，不能直接解引用。自定义排序比较器要满足严格弱序，不能把 < 写成 <=。
字符串也需要分清输入方式：cin >> s 读一个不含空白的词，getline(cin, s) 读整行。若整行的前导空格有意义，从 cin >> n 切换到整行输入时，可先用 cin.ignore 丢弃这一行剩余内容，再调用 getline；忽略长度应足以覆盖行尾剩余字符。
离散化：保留大小关系，压缩值域
数值可达十亿、实际只有几万个不同值时，可排序去重后映射到连续编号。a 为 vector<ll>，以下生成与原顺序对应的 0 下标编号 id。
vector<ll> b = a;sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());vector<int> id;for (ll x : a) { id.push_back(lower_bound(b.begin(), b.end(), x) - b.begin());}时间 
，空间 
。100, 1000, 1000000 会变成 0, 1, 2，相等和大小关系保留，原来的距离没有保留。计算长度或差值时仍应使用原值。
02｜前缀和、差分与双指针
一维前缀和：静态区间求和
a[1..n] 为原数组，s[0] = 0。区间两端均包含在答案内：
vector<ll> s(n + 1, 0);for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i];}ll ans = s[r] - s[l - 1];cout << ans << '\n';预处理 
，每次查询 
，额外空间 
。例如数组为 2 3 5 7，查询闭区间 [2, 4]，答案为 15。
这个模板用于预处理后数组不变的场景。每次修改一个元素，都可能影响后面的所有前缀和，不能把动态修改也当成常数时间操作。
前缀和的另一种用途是转化条件：区间 [l, r] 的和等于 k，等价于 
。扫描右端点时，统计此前有多少个前缀和等于 
即可。这里要先放入 s[0] = 0，并且先查询、后加入当前前缀，避免把空区间算进去；含负数也成立。
二维前缀和：矩形求和
a[1..n][1..m] 为矩阵，s 的第 0 行、第 0 列保持为 0。查询左上角 (x, y)、右下角 (u, v) 的闭矩形。
vector<vector<ll>> s(n + 1, vector<ll>(m + 1, 0));for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; }}ll ans = s[u][v] - s[x - 1][v] - s[u][y - 1] + s[x - 1][y - 1];cout << ans << '\n';容斥中，重叠部分被减了两次，需要加回来一次。预处理时间与空间均为 
，每次查询 
。第一行、第一列和整个矩阵都应单独自测。
若原矩阵只记录每格是否满足某性质，二维前缀和就变成“矩形内满足条件的格子数”。更换每格的贡献可以复用同一套容斥，改变查询对象为最值时则不能直接相减。
一维差分：多次区间加，最后统一还原
初始数组 a[1..n] 使用 long long，共有 q 次操作，每次给闭区间 [l, r] 加 x。差分数组多开到 n + 2，为 r + 1 留出位置。
vector<ll> d(n + 2, 0);for (int i = 1; i <= n; i++) { d[i] = a[i] - a[i - 1];}for (int i = 1; i <= q; i++) { int l, r; ll x; cin >> l >> r >> x; d[l] += x; d[r + 1] -= x;}ll cur = 0;for (int i = 1; i <= n; i++) { cur += d[i]; cout << cur << " \n"[i == n];}这里要求 a[0] = 0。区间内部的相邻差不变，只修改两个端点；再求一次前缀和就能还原。总时间 
，额外空间 
。若操作与查询交替发生，不能每次都重新还原整个数组而仍声称线性总复杂度。
双指针：非负数组中，区间和不超过上限
a[1..n] 的元素均非负，k >= 0。统计所有和不超过 k 的非空连续子数组，答案用 long long。
int l = 1;ll sum = 0;ll ans = 0;for (int r = 1; r <= n; r++) { sum += a[r]; while (l <= r && sum > k) { sum -= a[l]; l++; } ans += r - l + 1;}cout << ans << '\n';固定右端点时，合法左端点恰好是 [l, r]，因此新增 r - l + 1 个答案。两个指针各向右移动至多 
次，总时间 
，额外空间 
。
非负性是成立条件。数组含负数时，窗口扩大后和可能减小。比如 2 -3、上限 0，先丢弃 2 就会漏掉整个区间。全零数组、上限为零和单个元素大于上限也要测试。
03｜二分答案：先写清可行性
最小分段容量
n >= 1 个非负整数按原顺序划分成不超过 k 个非空连续段，k >= 1，求各段和最大值的最小值。a 使用 0 下标。
容量越大，越容易完成划分，具有“不可行 → 可行”的单调性。给定容量时，尽量向当前段装入元素，放不下才另开一段，这样得到所需的最少段数。
练习输入：第一行 n k，第二行是 n 个非负整数；输出最小容量。下面是一份可直接运行的完整程序，使用标准输入输出。
#include<bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vector<ll> a(n); for (ll &x : a) { cin >> x; } ll l = *max_element(a.begin(), a.end()); ll r = accumulate(a.begin(), a.end(), 0LL); auto chk = [&](ll lim) { int cnt = 1; ll sum = 0; for (ll x : a) { if (sum > lim - x) { cnt++; sum = x; } else { sum += x; } } return cnt <= k; }; while (l < r) { ll mid = l + (r - l) / 2; if (chk(mid)) { r = mid; } else { l = mid + 1; } } cout << l << '\n'; return 0;}搜索下界是最大元素，故每个元素都能单独装下；上界是总和，必然可行。要求总和能够由 long long 表示。设总和为 
，时间为 
，额外空间 
。
例如 7 2 5 10 8 分成不超过两段，答案为 18。还应检查只有一段、每个元素单独一段、所有元素为零。
这套循环维护的是最小可行值位于闭区间 [l, r]。找最大可行值时，需要重新确定取中点方式和区间更新，不能只把一个比较符号反过来。
以输入 5 2、数组 7 2 5 10 8 为例：初始 [10, 32]，依次判断容量 21、15、18、17，对应需要 2、3、2、3 段，区间最后缩为 [18, 18]。容量 18 时划分为 7 2 5 与 10 8，最大段和为 18。
判定中的贪心也需要证明。固定容量后，贪心第一段的末端不会早于任何合法划分的第一段末端；归纳可得，贪心前若干段覆盖的前缀不短于其他合法划分的同样段数。因此贪心所需段数最少，段数仍超过 k 就确实不可行。非负性保证一段加入元素后，和不会下降。
最大可行值：木材切割
a 为 n >= 1 根非负整数长度的木材，k >= 1。切出至少 k 段等长木材，求最大的正整数长度；无法切出时输出 0，不计锯缝损耗。长度增大，可切段数不增。下段中长度均不超过 1e9。
ll l = 0;ll r = *max_element(a.begin(), a.end());while (l < r) { ll mid = l + (r - l + 1) / 2; ll cnt = 0; for (ll x : a) { cnt += x / mid; } if (cnt >= k) { l = mid; } else { r = mid - 1; }}cout << l << '\n';时间 
，空间 
，
为最大木材长度，累计段数须能用 long long 表示。使用上取整中点，确保 l = mid 时区间缩小；只在 l < r 时计算，故 mid >= 1，不会除零。长度 4, 7, 9、需求 5 段，答案为 3。
04｜栈、递归与搜索
栈：三种括号匹配
字符串只包含 ()[]{}。遇到左括号入栈，遇到右括号必须与栈顶对应；扫描结束后栈为空才合法。
bool chk(const string &s) { string st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push_back(c); } else { if (st.empty()) { return false; } char t = st.back(); if ((c == ')' && t != '(') || (c == ']' && t != '[') || (c == '}' && t != '{')) { return false; } st.pop_back(); } } return st.empty();}时间 
，额外空间 
。([)] 的左右括号数量相同，仍不匹配；不能只数数量。取栈顶和出栈之前必须判空。
DFS：排列与回溯
生成 1..n 的全部排列。以下变量与函数放在 main 外，读入 n 后调用 dfs(1)。这里限定 n <= 10，是否能输出全部排列还要看时间与输出规模。
int n;int p[11];bool vis[11];void dfs(int u) { if (u > n) { for (int i = 1; i <= n; i++) { cout << p[i] << " \n"[i == n]; } return; } for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = true; p[u] = i; dfs(u + 1); vis[i] = false; } }}u 表示正在填写的位置，vis[i] 表示数字是否已经选过。返回上一层后恢复标记，保证不同分支互不影响。包含输出的时间为 
，额外空间 
。
组合枚举要限制下一个数大于上一个数；每个元素选或不选则是另一棵搜索树。加入剪枝时，必须说明被剪掉的分支为何不可能产生所需答案，不能仅凭“当前看起来较差”删除分支。
例如从 1..n 选 k 个数：固定递增选择顺序，避免同一组合出现多个排列。当前已选 c 个、还剩 r 个候选时，若 c + r < k 就无解，可直接返回。求最小代价时，若剩余代价均非负，当前代价可作下界；不小于已有最优值即可剪枝。
BFS：网格最短路
g 是 n 行、m 列的字符串网格，# 表示障碍。起点 (sx, sy) 与终点 (tx, ty) 均合法且可通行，采用 0 下标。每步上下左右移动一格，代价均为 1。
vector<vector<int>> d(n, vector<int>(m, -1));queue<pair<int, int>> q;int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};d[sx][sy] = 0;q.push({sx, sy});while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int u = x + dx[i]; int v = y + dy[i]; if (u < 0 || u >= n || v < 0 || v >= m) { continue; } if (g[u][v] == '#' || d[u][v] != -1) { continue; } d[u][v] = d[x][y] + 1; q.push({u, v}); }}cout << d[tx][ty] << '\n';队列按距离递增处理格子，第一次到达就是最短路。入队时标记，保证每个格子最多入队一次。不可达输出 -1，起终点相同输出 0。时间与空间均为 
。
连通块染色、Flood Fill 也可以使用这种遍历，每次从未访问的可通行格子启动一次。普通 BFS 求最短路要求每条边代价相同，不能直接处理任意带权图。
树与图：邻接表、访问标记和父节点
图可用 vector<vector<int>> g(n + 1); 存储邻接表。无向边 (u, v) 要分别执行 g[u].push_back(v);、g[v].push_back(u);。下面的函数用于一般图遍历，g、vis 在函数外定义，并提前分配长度。
void dfs(int u) { vis[u] = true; for (int v : g[u]) { if (!vis[v]) { dfs(v); } }}非连通图需要枚举所有顶点，从每个未访问顶点重新启动遍历。完整遍历时间与存储均为 
，其中 
是边数。
若输入保证是一棵树，只跳过父节点即可统计子树大小。以下函数与上一段二选一使用，根调用 dfs(1, 0)，sz 与 g 在函数外定义。
void dfs(int u, int fa) { sz[u] = 1; for (int v : g[u]) { if (v != fa) { dfs(v, u); sz[u] += sz[v]; } }}子树包括顶点自身，初值为 1。树有 
条边，时间和存储均为 
。只跳过父节点不能防止一般图中的环。
递归深度可能达到顶点数，链形树会暴露栈空间问题。深度较大时可用显式栈记录遍历顺序，再逆序累加子树大小；不能仅凭随机树测试就忽略最深情况。
非递归树遍历：逆序计算子树大小
树采用上述邻接表、根为 1。数组 p 记录父节点，ord 保存父节点先于子节点出现的遍历顺序；逆序处理时，所有孩子已经累加完毕。它可替换前面的递归子树统计。
vector<int> p(n + 1, 0), ord = {1};for (int i = 0; i < (int)ord.size(); i++) { int u = ord[i]; for (int v : g[u]) { if (v != p[u]) { p[v] = u; ord.push_back(v); } }}vector<int> sz(n + 1, 1);for (int i = n - 1; i > 0; i--) { int u = ord[i]; sz[p[u]] += sz[u];}时间与空间均为 
，额外空间位于容器中，不依赖深递归。这里只保证父子先后关系，ord 不是 DFS 后序；也不能把树的“跳过父节点”直接用于有环图。
05｜基础数论与倍增
最大公约数与质因数分解
欧几里得算法用于非负整数，约定 gcd(0, b) = b。下面的 gcd 时间为 
，额外空间 
。
ll gcd(ll a, ll b) { while (b != 0) { ll t = a % b; a = b; b = t; } return a;}正整数最小公倍数可写成 a / gcd(a, b) * b，先除后乘减少中间值，但仍需确认结果不会溢出。含零时另按定义处理，不能让 gcd(0, 0) 进入除法。
对正整数 x 进行试除分解，输出每个质因子及其指数：
for (ll p = 2; p <= x / p; p++) { if (x % p == 0) { int cnt = 0; while (x % p == 0) { x /= p; cnt++; } cout << p << ' ' << cnt << '\n'; }}if (x > 1) { cout << x << ' ' << 1 << '\n';}循环结束后剩余的大于 1 的数一定是质数。使用 p <= x / p 避免判断中的平方溢出。最坏时间 
，此处的 
指原始输入；额外空间 
。输入 1 时没有质因子。
埃氏筛与线性筛
需要求出 1..n 中的全部质数时，可先筛一次。埃氏筛如下，n >= 1，vis[i] 表示 i 被标记为非质数。
vector<bool> vis(n + 1, false);vis[0] = vis[1] = true;for (int i = 2; i <= n / i; i++) { if (!vis[i]) { for (ll j = 1LL * i * i; j <= n; j += i) { vis[j] = true; } }}小于平方起点的合数已经由更小的质因子标记。时间 
，空间 
。
线性筛额外保存质数表 p，每个合数只由它的最小质因子筛到一次：
vector<int> p;vector<bool> vis(n + 1, false);vis[0] = vis[1] = true;for (int i = 2; i <= n; i++) { if (!vis[i]) { p.push_back(i); } for (int x : p) { if (x > n / i) { break; } vis[i * x] = true; if (i % x == 0) { break; } }}时间 
，空间 
。i % x == 0 后的 break 是线性复杂度的重要条件，不能遗漏。两种筛法独立使用。
快速幂：倍增思想的一种实现
计算非负底数 a 的非负整数次幂并模 mod。这里限定 1 <= mod <= 1e9，使两个模内数的乘积可以用 long long 表示。
ll qpw(ll a, ll b, ll mod) { ll ans = 1 % mod; a %= mod; while (b > 0) { if (b & 1) { ans = ans * a % mod; } a = a * a % mod; b >>= 1; } return ans;}按指数的二进制位拆分，底数每轮平方一次。时间 
，额外空间 
。指数为零时返回 1 % mod，模数为 1 时返回 0。模数显著变大时，乘法可能先溢出再取模，这段代码的取值前提不能忽略。
06｜高精度：先约定数位方向
高精度模板统一处理非负整数，用十进制数位数组、低位在前，零统一保存为 {0}。例如 1203 保存为 {3, 0, 2, 1}。以下函数可放在同一份程序中。
输入、输出与表示
num 将不带正负号的非空数字串转换为数位数组，并去掉多余前导零；str 转回正常阅读顺序。
using V = vector<int>;V num(const string &s) { V a; for (int i = (int)s.size() - 1; i >= 0; i--) { a.push_back(s[i] - '0'); } while (a.size() > 1 && a.back() == 0) { a.pop_back(); } return a;}string str(const V &a) { string s; for (int i = (int)a.size() - 1; i >= 0; i--) { s.push_back(char('0' + a[i])); } return s;}调用示例为 V a = num(s);、cout << str(a) << '\n';。转换时间与结果空间均为 
，其中 
是数位数。
高精度加法：逐位相加与进位
V add(const V &a, const V &b) { V c; int t = 0; for (int i = 0; i < (int)a.size() || i < (int)b.size() || t; i++) { if (i < (int)a.size()) { t += a[i]; } if (i < (int)b.size()) { t += b[i]; } c.push_back(t % 10); t /= 10; } return c;}时间与结果空间均为 
。最后一位处理完仍可能有进位，999 + 1 = 1000 可以检查这个边界。
高精度减法：要求被减数不小于减数
下面的 sub(a, b) 要求 a >= b。比较大小时先比较数位数，相同时从最高位向最低位逐位比较；负数结果需另行处理符号。
V sub(const V &a, const V &b) { V c; int t = 0; for (int i = 0; i < (int)a.size(); i++) { int x = a[i] - t; if (i < (int)b.size()) { x -= b[i]; } t = x < 0; c.push_back((x + 10) % 10); } while (c.size() > 1 && c.back() == 0) { c.pop_back(); } return c;}时间与结果空间均为 
。1000 - 1 = 999 检查连续借位，123 - 123 = 0 检查结果去零后仍保留一位。
高精度乘法：竖式乘法
V mul(const V &a, const V &b) { V c(a.size() + b.size(), 0); for (int i = 0; i < (int)a.size(); i++) { int t = 0; for (int j = 0; j < (int)b.size() || t; j++) { t += c[i + j]; if (j < (int)b.size()) { t += a[i] * b[j]; } c[i + j] = t % 10; t /= 10; } } while (c.size() > 1 && c.back() == 0) { c.pop_back(); } return c;}第 i 位与第 j 位的乘积贡献到第 i + j 位。代码逐行进位，避免一个位置长期累积过大的值。时间 
，结果空间 
。检查乘零、乘一以及 99 * 99 = 9801。
高精度除以小整数：从高位向低位
quo(a, b, rem) 返回商，并通过引用参数 rem 返回余数。要求 1 <= b <= 1e9，rem 为 ll 变量。
V quo(const V &a, int b, ll &rem) { V c(a.size(), 0); rem = 0; for (int i = (int)a.size() - 1; i >= 0; i--) { rem = rem * 10 + a[i]; c[i] = rem / b; rem %= b; } while (c.size() > 1 && c.back() == 0) { c.pop_back(); } return c;}时间与结果空间均为 
。例如 12345 / 67 得到商 184、余数 17。还要检查被除数小于除数、恰好整除以及被除数为零。
加减乘从低位处理，除法从高位处理。每个函数的数位顺序必须一致；不能把正常字符串顺序直接传入这些函数。
07｜贪心：区间选择需要交换理由
有若干半开区间 [l, r)，均满足 l < r。选出最多个互不重叠的区间，端点相接允许同时选择。用 pair<int, int> 保存区间，第一项为左端点，第二项为右端点。
sort(a.begin(), a.end(), [](const pair<int, int> &x, const pair<int, int> &y) { return x.second < y.second;});int ans = 0;int ed = 0;for (auto x : a) { if (ans == 0 || x.first >= ed) { ans++; ed = x.second; }}cout << ans << '\n';优先选择结束最早的区间。任取一个最优方案，将首个区间换成结束最早的区间，后续可选择范围不会缩小；之后对剩余区间重复同样的论证。
时间 
，排序之外的额外空间 
，排序实现还需栈空间。闭区间且端点相接也算重叠时，条件应改为 x.first > ed。带权区间选择通常不能直接使用这个贪心。
08｜动态规划：状态、初值与枚举方向
最大连续子段和
a[1..n]，n >= 1，子段不能为空。cur 表示以当前位置结尾的最大子段和；只有“单独从当前位置开始”和“接在前一段后面”两种选择。
ll cur = a[1];ll ans = a[1];for (int i = 2; i <= n; i++) { cur = max((ll)a[i], cur + a[i]); ans = max(ans, cur);}cout << ans << '\n';时间 
，额外空间 
。若初值设为零，全负数时会错误地选出空段。例如 -5 -2 -8 的答案是 -2。
0/1 背包：容量倒序
w[i] 是正整数体积，v[i] 是价值，每件物品最多使用一次。f[j] 表示已处理物品中，总体积不超过j 的最大价值，允许不选物品，所以初值为 0。
先保留物品维度：
表示只考虑前 
件物品、容量不超过 
的最大价值。不选第 
件，继承 
；选它，则从 
转移。两项都必须来自上一层，转移为：
仅在 
时有第二项。压缩成一维后，倒序枚举容量就是为了保留这个“上一层”的语义。
vector<ll> f(m + 1, 0);for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { f[j] = max(f[j], f[j - w[i]] + v[i]); }}cout << f[m] << '\n';倒序保证 f[j - w[i]] 还没有用过当前物品。若改为正序，一件物品可能被反复加入。例如只有一件体积 2、价值 3 的物品，容量为 4，0/1 背包答案是 3。
时间 
，空间 
。如果要求恰好装满，应把除 f[0] 外的状态初始化为不可达，并在转移前检查前驱可达；不能沿用全零初值。
恰好装满：不可达不能设为零
仍是每件最多使用一次，价值允许为负。要求总体积恰好等于 m。下段中所有可达价值及中间和的绝对值均小于 
；练习约定无解输出 Impossible。
ll neg = -(1LL << 62);vector<ll> f(m + 1, neg);f[0] = 0;for (int i = 1; i <= n; i++) { for (int j = m; j >= w[i]; j--) { if (f[j - w[i]] != neg) { f[j] = max(f[j], f[j - w[i]] + v[i]); } }}if (f[m] == neg) { cout << "Impossible\n";} else { cout << f[m] << '\n';}时间 
，空间 
。只有体积 2、价值 5 的一件物品、目标容量 3 时无解，全零初始化却会错误地给出价值 5。目标容量为 0 时空集可行，答案为 0。实际题目的无解输出应按题面调整。
完全背包：容量正序
每种物品可以使用任意次，体积仍为正整数。状态含义继续采用“不超过容量的最大价值”。
vector<ll> f(m + 1, 0);for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= m; j++) { f[j] = max(f[j], f[j - w[i]] + v[i]); }}cout << f[m] << '\n';正序使前驱可以已经使用当前物品，从而继续取同一种物品。时间 
，空间 
。每种物品有数量上限时，需要重新处理次数限制；体积为零也不满足这里的前提。
完全背包的选取项来自本层：
，因此容量正序。0/1 背包与完全背包的区别落在前驱所属层，枚举方向只是实现这个区别。若每种物品最多 c[i] 件，朴素方法要枚举取用次数，总时间上界为 
，其中 
为最大次数，不能直接改一处循环就沿用原复杂度。
方案计数：组合与排列的循环不同
w[1..n] 是互不相同的正整数面值，每种面值可使用任意次。求恰好组成金额 m 的组合数，不计取用顺序。mod 为正整数且不超过 1e9。
vector<ll> f(m + 1, 0);f[0] = 1 % mod;for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= m; j++) { f[j] = (f[j] + f[j - w[i]]) % mod; }}cout << f[m] << '\n';时间 
，空间 
。面值在外层，相当于固定各面值的加入次序，1 + 2 与 2 + 1 不重复计数。若统计有序序列，应把金额放在外层、面值放在内层，状态转移的解释也要随之改变。
例如面值为 1, 2，金额为 3，组合数是 2，有序序列数是 3。f[0] = 1 表示构造空金额只有一种初始方案，不能设为 0。
最长严格上升子序列：平方 DP
f[i] 表示以 a[i] 结尾的最长严格上升子序列长度。子序列不要求连续。
vector<int> f(n + 1, 1);int ans = 0;for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { if (a[j] < a[i]) { f[i] = max(f[i], f[j] + 1); } } ans = max(ans, f[i]);}cout << ans << '\n';时间 
，空间 
。严格上升使用 <；不下降使用 <=。答案是所有结尾的最大值，不一定是 f[n]。全相等数组的严格上升答案为 1。
以 3 1 2 2 4 为例，五个结尾的长度依次是 1, 1, 2, 2, 3，答案为 3。两个 2 不能互相接续。若需要输出方案，转移改善时记录前驱下标，从最优结尾反向追溯，再翻转顺序；只保存长度不足以恢复方案。
记忆化搜索：严格下降路径
非空矩阵 a 大小为 
，每步只能走到四邻中数值严格更小的格子，求最长路径的格子数。严格下降保证无环；不同起点可以共享后续路径，缓存的是最优长度，不能把已算过的格子当作禁止进入。以下变量与函数放在 main 外，读入后分配 a 和全零的 f，枚举所有格子调用 dfs 并取最大值。
int n, m;vector<vector<int>> a, f;int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};int dfs(int x, int y) { if (f[x][y] != 0) { return f[x][y]; } f[x][y] = 1; for (int i = 0; i < 4; i++) { int u = x + dx[i]; int v = y + dy[i]; if (u >= 0 && u < n && v >= 0 && v < m && a[u][v] < a[x][y]) { f[x][y] = max(f[x][y], dfs(u, v) + 1); } } return f[x][y];}每个状态只展开一次，每次看四个方向，时间与空间均为 
，递归深度最坏也可达 
。按值排序递推可避免深递归，排序需 
时间；条件改成“不大于”会产生环，原记忆化写法不再成立。
网格 DP：向右或向下的最大路径和
n, m >= 1，每个格子都有权值，允许负数。从 (1, 1) 走到 (n, m)，每步只能向右或向下，路径包含起终点。
vector<vector<ll>> f(n + 1, vector<ll>(m + 1, 0));f[1][1] = a[1][1];for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (i == 1 && j == 1) { continue; } if (i == 1) { f[i][j] = f[i][j - 1] + a[i][j]; } else if (j == 1) { f[i][j] = f[i - 1][j] + a[i][j]; } else { f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]; } }}cout << f[n][m] << '\n';时间与空间均为 
。首行只能从左侧到达，首列只能从上方到达，单独处理后不会让不存在的零权路径干扰负数答案。有障碍时，还需要记录不可达状态；不能仅给障碍格赋零。
简单区间 DP：相邻石子合并
n >= 1 堆石子排成一行，每次合并相邻的两堆，代价是两堆石子数之和，求合成一堆的最小总代价。a[1..n] 非负，s 为前缀和。f[l][r] 表示将闭区间 [l, r] 合成一堆的最小代价。
最后一次合并必然把区间分成 [l, k] 和 [k + 1, r]。分别合并两侧，再支付整个区间的石子总数。按区间长度递增计算，保证子区间已经求出。
这与“先选最便宜的相邻两堆”不同。例如 6 4 4 6：先合并中间两堆，代价为 8，再合并总代价最少也为 8 + 14 + 20 = 42；先分别合并左右两对，则为 10 + 10 + 20 = 40。局部最便宜的操作会改变之后的邻接关系，不能据此贪心。
区间 DP 枚举最后的切分点，覆盖了所有合法合并方案；对固定切分点，两侧分别取最优即可。若某侧不是最优，就能替换它而不影响另一侧与最后一次合并，从而降低总代价。这是转移能成立的原因。
vector<vector<ll>> f(n + 1, vector<ll>(n + 1, 0));ll inf = 1LL << 62;for (int len = 2; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; f[l][r] = inf; for (int k = l; k < r; k++) { f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + (s[r] - s[l - 1])); } }}cout << f[1][n] << '\n';时间 
，空间 
。单独一堆不需要合并，故 f[i][i] = 0。这里要求所有可能的合并代价小于 inf，并保证中间求和不会溢出。
石子围成环时，需要重新定义状态范围。
09｜考前按这些边界复查
模板默写完成后，至少用一组能暴露错误的数据检查含义。
- 区间与下标
：首元素、末元素、长度为 1、整个区间；确认 0 下标与 1 下标没有混用。 - 数值与初值
：全零、全负、最大乘积与总和；确认空答案是否允许、不可达状态是否被当成零。 - 搜索与图
：起点等于终点、终点不可达、多个连通块、存在环、链形树；确认标记时机和递归深度。 - 二分与双指针
：答案在两端、全零数组、单个元素超过限制；确认单调性与非负性等前提。 - 高精度
：连续进位、连续借位、相等相减、乘零、被除数小于除数与整除。 - 背包与计数
：只有一件物品、无法恰好装满、金额为零、重复面值；确认枚举方向与是否计顺序。
模拟、枚举、递推、字符串处理也属于普及组复习内容。这些题更依赖题目中的规则：循环范围、操作顺序、取整方式和输出格式需要逐项对应，不能靠一份固定程序覆盖。
复习完成的标准，是能解释每个变量的含义，并根据题目改变边界和转移。比赛中使用模板前，先核对输入条件、状态定义与复杂度，再决定是否适用。
资料参考：CCF《NOI 大纲（2025 年修订版）》发布页；官方 PDF。完整网址：https://www.noi.cn/xw/2025-04-18/841584.shtml 。
微信 · 果壳一只羊
长按识别二维码，添加微信；请注明来意。
