CSP-J 复赛必备编程模板（核心代码速查）
搜索知识点 /

CSP-J 复赛必备编程模板（核心代码速查）

本文把近十年 CSP-J（含 NOIP 普及组）复赛反复出现的核心算法整理成"背下来就能套"的代码模板。 所有代码均为 C++17，可直接复制使用；约定数组大小 N 按题目数据范围取够，INF 表示无穷大（0x3f3f3f3f）。

一句话：T1 / T2 拼细节与模板熟练度，T3 / T4 拼"认得出题型 + 套对模板"。把下面这些代码背熟、能默写、能在考场上 5 分钟调通，复赛编程题基本稳过。

真题知识点分布表（2018—2024）

下表统计了近年复赛每题用到的核心模板（来源：CSP-J 历年复赛真题，洛谷题号 P 系列），用以说明"背这些模板到底值不值"。

年份题号题目核心模板难度
2024T1扑克牌桶排序 / 排序★★
2024T2地图探险模拟 / BFS★★★
2024T3小木棍整除求余 / 贪心 / 递推(DFS+剪枝)★★★
2024T4接龙动态规划 / 前缀和★★★★
2023T1小苹果找规律 / 枚举★★
2023T2公路贪心★★★
2023T3一元二次方程大模拟 / 枚举★★★
2023T4旅游巴士最短路 Dijkstra / BFS+二分★★★★
2022T1乘方模拟★★
2022T2解密数学 / 二分★★★
2022T3逻辑表达式大模拟 / 栈★★★★
2022T4上升点列动态规划 / LIS★★★★
2021T1分糖果数学 / 思维★★
2021T2插入排序排序 / 枚举★★★
2021T3网络连接大模拟 / 字符串★★★★
2021T4小熊的果篮模拟 / 队列★★★★
2020T1优秀的拆分位运算 / 进制转换★★
2020T2直播获奖桶排序 / 模拟★★★
2020T3表达式栈 / 深搜★★★★
2020T4方格取数动态规划 / 记忆化搜索★★★★
2019T1数字游戏字符串★★
2019T2公交换乘模拟 / 队列★★★
2019T3纪念品背包(DP)★★★★
2019T4加工零件最短路★★★★
2018T4对称二叉树二叉树 / 递归★★★★

再往前的 NOIP 普及组同样高频：01 背包（2005 采药、2001 装箱问题、2006 开心的金明）、gcd / 进制转换（2014 比例简化、2011 数字反转、2006 数列）、深搜（2004 火星人、2002 选数/产生数）、递推 / DP（2002 过河卒、2001 数的计算）。

一、考场约定与万能骨架

1.1 万能头文件 + 快读快写

复赛允许用 #include <bits/stdc++.h>，省去记一堆头文件。当 cin/cout 超时（大数据量）时改用 scanf/printf，或下面这套快读。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;   // long long 版"无穷大"（约 4.5e18，当 INF 用足够）

// 快读（整数，支持 long long 与负数）
ll read() {
    ll x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

// 快写（整数，支持 long long 与负数）
void write(ll x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    cin.tie(0)->sync_with_stdio(0);   // 关闭同步+解绑，给 cin/cout 提速（等价于 ios::sync_with_stdio(false); cin.tie(nullptr);）
    ll n = read();
    write(n);
    return 0;
}
背什么 / 怎么用
  • cin.tie(0)->sync_with_stdio(0); 放在 main 开头即可给 cin/cout 提速（等价于 ios::sync_with_stdio(false); cin.tie(nullptr);）；用 read()/write() 这套快读写则无需解绑，且速度更快。
  • LLINF = 0x3f3f3f3f3f3f3f3f 是 long long 版无穷大，够当 INF 用；若真要 long long 上界，用 0x7fffffffffffffff（即 LLONG_MAX）。
  • using ll = long long; 之后，凡是可能爆 int 的（乘积、阶乘、路径和）一律用 ll；这里 read() 已返回 ll，正负都能读。

二、数学与数论基础（最高频）

2.1 最大公约数 GCD / 最小公倍数 LCM

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;   // 先除后乘，防溢出
}
对应真题
  • 2014 比例简化（枚举 + gcd 约分）
  • 2001 最大公约数和最小公倍数问题

2.2 快速幂（带取模）

ll qpow(ll a, ll b, ll mod) {
    ll res = 1 % mod;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
背什么 / 怎么用
  • 求 a^b % mod、逆元（qpow(a, mod-2, mod)，要求 mod 为质数）、大数乘模都靠它。
  • 口诀：指数 b 看成二进制，遇到 1 就乘进答案，每轮底数自乘、指数右移。

2.3 质数判断

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * 1LL * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

2.4 埃氏筛 / 欧拉筛

// 埃氏筛：标记合数
const int N = 1000005;
bool isp[N];
void sieve(int n) {
    for (int i = 2; i <= n; i++) isp[i] = true;
    for (int i = 2; i * 1LL * i <= n; i++)
        if (isp[i])
            for (int j = i * i; j <= n; j += i) isp[j] = false;
}

// 欧拉筛：线性，prime[] 里存所有素数
int prime[N], cnt;
bool notPrime[N];
void euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * 1LL * prime[j] <= n; j++) {
            notPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) break;   // 关键：保证每个合数只被最小质因子筛掉
        }
    }
}

2.5 进制转换

// 十进制 n 转 radix 进制字符串（radix 任意，支持到 36）
string toBase(ll n, int radix) {
    if (n == 0) return "0";
    string s;
    while (n) {
        int d = n % radix;
        s += (d < 10 ? char(d + '0') : char(d - 10 + 'A'));
        n /= radix;
    }
    reverse(s.begin(), s.end());
    return s;
}

// radix 进制字符串 s 转十进制
ll fromBase(const string &s, int radix) {
    ll res = 0;
    for (char c : s) {
        int d = isdigit(c) ? c - '0' : toupper(c) - 'A' + 10;
        res = res * radix + d;
    }
    return res;
}
对应真题
  • 2020 优秀的拆分（二进制拆分，位运算）
  • 2011 数字反转（十进制反转）
  • 2006 数列（进制转换）

2.6 位运算技巧速查

x & -x                 // 取出最低位的 1（及后面所有 0），树状数组核心
x & (x - 1)            // 消去最低位的 1；用来数 1 的个数、判断是否为 2 的幂
x >> k                 // 等价于 x / 2^k
x << k                 // 等价于 x * 2^k
__builtin_popcount(x)  // int 中二进制 1 的个数
__builtin_ctz(x)       // 末尾连续 0 的个数
对应真题
  • 2020 优秀的拆分（把数拆成 2 的幂之和，直接枚举二进制位）

三、排序、查找与前缀（T1 / T2 常客）

3.1 sort + 自定义比较（结构体排序）

struct Node { int a, b; };
bool cmp(const Node &x, const Node &y) {
    if (x.a != y.a) return x.a < y.a;   // 第一关键字升序
    return x.b > y.b;                   // 第二关键字降序
}
vector<Node> v(n);
sort(v.begin(), v.end(), cmp);
对应真题
  • 2021 插入排序（手写或利用 sort 判逆序）
  • 2009 分数线划定 / 2007 奖学金（结构体多关键字排序）

3.2 整数二分（查找模板）

// 模板1：找第一个 >= x 的位置（等价于 lower_bound）
int l = 0, r = n - 1, ans = n;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] >= x) { ans = mid; r = mid - 1; }
    else l = mid + 1;
}

// 模板2：找最后一个 <= x 的位置（等价于 upper_bound - 1）
int l = 0, r = n - 1, ans = -1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] <= x) { ans = mid; l = mid + 1; }
    else r = mid - 1;
}
对应真题
  • 2022 解密（在答案区间上二分）
  • 2017 跳房子（二分答案 + DP）

3.3 前缀和 / 差分

// 一维前缀和
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
int sum = pre[r] - pre[l - 1];          // 区间 [l, r] 之和

// 一维差分：区间 [l, r] 全体 +v，最后还原
void add(int l, int r, int v) { d[l] += v; d[r + 1] -= v; }
for (int i = 1; i <= n; i++) d[i] += d[i - 1];
对应真题
  • 2024 接龙（配合 DP 做前缀统计）
  • 2016 魔法阵（前缀和统计）

3.4 桶计数

int cnt[26] = {0};
for (char c : s) if (islower(c)) cnt[c - 'a']++;
对应真题
  • 2024 扑克牌（按牌面桶排计数）
  • 2020 直播获奖（桶排 + 实时统计名次）

四、基础数据结构

4.1 栈（数组实现）

const int N = 100005;
int stk[N], top = 0;
void push(int x) { stk[top++] = x; }
void pop() { top--; }
int topv() { return stk[top - 1]; }
bool empty() { return top == 0; }
对应真题
  • 2022 逻辑表达式（运算符栈 / 表达式树）
  • 2020 表达式（栈处理括号与运算）
  • 2013 表达式求值

4.2 队列（STL / 循环队列）

#include <queue>
queue<int> q;
q.push(x); q.pop(); q.front(); q.empty();

// 双端队列（单调队列 / 滑动窗口用）
#include <deque>
deque<int> dq;
dq.push_back(x); dq.push_front(x); dq.pop_front(); dq.pop_back();
对应真题
  • 2021 小熊的果篮（队列维护水果筐）
  • 2019 公交换乘（队列模拟优惠）
  • 2016 海港（队列维护时间窗）

4.3 优先队列（堆）

#include <queue>
priority_queue<int> pq;                              // 大根堆
priority_queue<int, vector<int>, greater<int>> pq2; // 小根堆
pq.push(x); pq.top(); pq.pop();
对应真题
  • 2015 推销员（贪心 + 优先队列取最值）
  • 2023 公路（贪心选最便宜加油站）

4.4 并查集

const int N = 100005;
int fa[N];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // 路径压缩
void merge(int x, int y) { fa[find(x)] = find(y); }
bool same(int x, int y) { return find(x) == find(y); }
怎么用
  • 判断"两个元素是否在同一集合"、合并集合、求连通块个数。
  • 最小生成树 Kruskal 必用（见第七节），连通性判定、团伙分组题也常用。

五、搜索（DFS / BFS / 回溯）

5.1 DFS 模板（含回溯）

bool vis[N];
void dfs(int step) {
    if (step == n) { /* 到达边界：输出 / 统计答案 */ return; }
    for (int i = 0; i < m; i++) {
        if (!vis[i]) {            // 选 i 的合法性检查
            vis[i] = true;
            dfs(step + 1);
            vis[i] = false;       // 回溯：撤销选择
        }
    }
}

5.2 全排列枚举（next_permutation）

int a[6] = {1, 2, 3, 4, 5};
do {
    // 处理当前排列 a[0..4]
} while (next_permutation(a, a + 5));
对应真题
  • 2004 火星人（给定排列，求往后第 m 个排列）
  • 2002 选数 / 产生数（枚举子集 / 排列）

5.3 组合枚举（DFS 选 k 个）

int ans[15];
void dfs(int pos, int last, int k) {  // 从 last+1 开始选 k 个，不重复
    if (pos == k) { /* 输出 ans[0..k-1] */ return; }
    for (int i = last + 1; i <= n; i++) {
        ans[pos] = i;
        dfs(pos + 1, i, k);
    }
}

5.4 BFS 模板（最短路 / 扩散）

#include <queue>
struct Node { int x, y, step; };
queue<Node> q;
q.push(start); vis[start.x][start.y] = true;
while (!q.empty()) {
    Node u = q.front(); q.pop();
    for (每个相邻位置 v) {
        if (合法且 !vis[v]) {
            vis[v] = true;
            dist[v] = dist[u] + 1;   // 第一次到达即最短
            q.push(v);
        }
    }
}
对应真题
  • 2024 地图探险（BFS 探索可达格子）
  • 2023 旅游巴士（BFS + 二分最短路）
  • 2019 加工零件（BFS 分层最短路）

5.5 记忆化搜索（DP + DFS）

const int N = 1005;
int f[N][N];
int dp(int i, int j) {
    if (i == 0 && j == 0) return a[0][0];   // 边界
    if (f[i][j] != -1) return f[i][j];       // 已算过直接返回
    int res = ...;                            // 按转移方程计算
    return f[i][j] = res;
}
// 调用前：memset(f, -1, sizeof f);
对应真题
  • 2020 方格取数（记忆化搜索 / 坐标 DP）

六、动态规划（拉开分差的核心）

6.1 01 背包（每件最多选一次）

// dp[j] = 容量 j 时的最大价值；一维滚动，容量必须倒序
for (int i = 1; i <= n; i++)
    for (int j = m; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
对应真题
  • 2019 纪念品（多天背包）
  • 2005 采药 / 2001 装箱问题 / 2006 开心的金明（经典 01 背包）

6.2 完全背包（每件可选无限次）

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= m; j++)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

6.3 最长上升子序列 LIS（O(n log n)）

vector<int> t;
for (int x : a) {
    auto it = lower_bound(t.begin(), t.end(), x);
    if (it == t.end()) t.push_back(x);
    else *it = x;
}
int lis = t.size();   // 最长上升子序列长度
对应真题
  • 2022 上升点列（LIS 变形，配合坐标处理）

6.4 数字三角形 / 递推 DP

// 自底向上合并：a[i][j] += max(左下, 右下)
for (int i = n - 1; i >= 1; i--)
    for (int j = 1; j <= i; j++)
        a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
// 答案：a[1][1]
对应真题
  • 2002 过河卒（递推 / 组合）
  • 2001 数的计算（递推计数）

6.5 最长公共子序列 LCS

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = max(f[i - 1][j], f[i][j - 1]);

6.6 一维线性 DP 套路

// 通用框架：dp[i] 表示"以第 i 个位置结尾"的最优值
for (int i = 1; i <= n; i++) {
    dp[i] = 初值;
    for (int j = 1; j < i; j++)
        if (满足条件) dp[i] = 最优(dp[i], dp[j] + 增量);
}
怎么用
  • "求最长 / 最大 / 最小"类题，先想 dp[i] 表示什么，再找转移：从前面哪些 j 能转移过来。
  • 2024 接龙、2018 摆渡车本质都是线性 DP，认出"状态 + 转移"就能套。

七、图论（T4 常客）

7.1 邻接表存图

const int N = 100005;
vector<pair<int, int>> g[N];   // g[u] 存 {v, w}（终点, 边权）
void addEdge(int u, int v, int w) {
    g[u].push_back({v, w});
    // 无向图再加：g[v].push_back({u, w});
}

7.2 Dijkstra 最短路（朴素 O(n²)，小图适用）

const int N = 1005;
int g[N][N], dist[N], vis[N];
void dijkstra(int s, int n) {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, mn = INF;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dist[j] < mn) { mn = dist[j]; u = j; }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= n; v++)
            if (!vis[v]) dist[v] = min(dist[v], dist[u] + g[u][v]);
    }
}
// 注意：邻接矩阵 g 先全部置 INF，g[i][i] = 0
对应真题
  • 2023 旅游巴士（最短路 + 限制条件）
  • 2019 加工零件（奇偶层最短路）

7.3 Floyd 最短路（多源，O(n³)）

const int N = 205, INF = 0x3f3f3f3f;
int d[N][N];
// 初始化 d[i][j] = 边权，d[i][i] = 0，无直接边置 INF
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

7.4 Kruskal 最小生成树

struct Edge { int u, v, w; } e[N];
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }
int kruskal(int n, int m) {     // n 个点 m 条边
    sort(e + 1, e + m + 1, cmp);
    init(n);                    // 调用并查集初始化
    int sum = 0, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int u = e[i].u, v = e[i].v;
        if (!same(u, v)) {
            merge(u, v);
            sum += e[i].w;
            cnt++;
        }
        if (cnt == n - 1) break;  // 已选够 n-1 条边
    }
    return sum;   // 若 cnt < n-1 则图不连通
}

7.5 树的遍历（DFS）

vector<int> g[N];
void dfs(int u, int fa) {       // fa 是父节点，防止走回头
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}
对应真题
  • 2018 对称二叉树（递归比较左右子树）

八、高精度与组合数学

8.1 高精度加法（字符串）

string add(const string &a, const string &b) {
    string s;
    int i = a.size() - 1, j = b.size() - 1, c = 0;
    while (i >= 0 || j >= 0 || c) {
        int x = i >= 0 ? a[i--] - '0' : 0;
        int y = j >= 0 ? b[j--] - '0' : 0;
        s += char((x + y + c) % 10 + '0');
        c = (x + y + c) / 10;
    }
    reverse(s.begin(), s.end());
    return s;
}
对应真题
  • 2005 循环（大数幂次位数 / 高精度）
  • 2003 麦森数（高精度求末 500 位）

8.2 高精度减法（字符串，约定 a ≥ b）

string sub(const string &a, const string &b) {
    // 约定 a >= b；若 a < b 需先比较大小、交换并记负号
    string s;
    int i = (int)a.size() - 1, j = (int)b.size() - 1, c = 0;
    while (i >= 0 || j >= 0) {
        int x = i >= 0 ? a[i--] - '0' : 0;
        int y = j >= 0 ? b[j--] - '0' : 0;
        int d = x - y - c;
        if (d < 0) { d += 10; c = 1; }   // 借位
        else c = 0;
        s += char(d + '0');
    }
    reverse(s.begin(), s.end());
    int k = 0;
    while (k + 1 < s.size() && s[k] == '0') k++;   // 去前导 0，保留一位
    return s.substr(k);
}
怎么用
  • 减法要求被减数 ≥ 减数；若 a < b，先比较大小再交换，结果加负号。
  • 借位标记 c 参与下一位运算；最后去前导 0（结果本身是 0 时保留一个 '0'）。

8.3 高精度乘法（字符串）

string mul(const string &a, const string &b) {
    int n = a.size(), m = b.size();
    vector<int> c(n + m, 0);
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            c[i + j + 1] += (a[i] - '0') * (b[j] - '0');
    for (int i = n + m - 1; i > 0; i--) {
        c[i - 1] += c[i] / 10;
        c[i] %= 10;
    }
    int k = 0;
    while (k < n + m - 1 && c[k] == 0) k++;
    string s;
    for (int i = k; i < n + m; i++) s += char(c[i] + '0');
    return s;
}

8.4 高精度除法（高精 ÷ 低精整数）

// a 为高精度字符串，b 为 int 范围除数（b > 0），余数通过 rem 返回
string div(const string &a, int b, int &rem) {
    string s;
    ll cur = 0;
    for (char ch : a) {
        cur = cur * 10 + (ch - '0');
        s += char(cur / b + '0');
        cur %= b;
    }
    rem = (int)cur;                 // 最终余数
    int k = 0;
    while (k + 1 < s.size() && s[k] == '0') k++;   // 去前导 0
    return s.substr(k);
}
怎么用
  • 这是"高精 ÷ 低精"模板，覆盖 CSP-J 绝大多数场景（大数整除、进制转换、求商与余数）。
  • 用 long long 的 cur 暂存当前位，避免中间值溢出；rem 即最终余数。
  • "高精 ÷ 高精"本质是反复减法试商，考场极少见，不必背。

8.5 组合数 / 杨辉三角

const int N = 2005, MOD = 1e9 + 7;
ll C[N][N];
void comb(int n) {                 // 预处理 C[n][k]
    C[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
}

8.6 字符串哈希（滚动哈希）

const ll B = 131, MOD = 1e9 + 7, N = 100005;
ll h[N], p[N];
void build(const string &s) {
    p[0] = 1; h[0] = 0;
    for (int i = 0; i < s.size(); i++) {
        p[i + 1] = p[i] * B % MOD;
        h[i + 1] = (h[i] * B + s[i]) % MOD;
    }
}
ll sub(int l, int r) {             // 1-based 闭区间 [l, r] 的子串哈希
    return (h[r] - h[l - 1] * p[r - l + 1] % MOD + MOD) % MOD;
}
怎么用
  • 快速判断两段子串是否相等（哈希值相等即相等，冲突概率极低）。
  • 字符串去重、最长公共子串、Rabin-Karp 匹配都用它。

九、字符串处理速查

9.1 回文判断 / 双指针

bool isPal(const string &s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
    }
    return true;
}
对应真题
  • 2019 数字游戏（反转 + 判回文 / 哈希）
  • 2018 标题统计（字符统计 + 字符串遍历）

9.2 字符统计 / 子串

string s;
cin >> s;
// 字符频率
int cnt[256] = {0};
for (char c : s) cnt[(unsigned char)c]++;
// 查找子串
size_t pos = s.find("abc");
if (pos != string::npos) { /* 找到，pos 是下标 */ }
// 取子串 [l, r]（长度 = r - l + 1）
string sub = s.substr(l, r - l + 1);
易错点
  • cin >> s 遇空格就停；读整行用 getline(cin, s)，且 cin 后接 getline 要先 cin.ignore() 吃掉换行。
  • s.length() 是无符号，减法比较先强转 (int) 或存到 int n，否则空串会死循环。
  • string::find 找不到返回 string::npos，比较用 != string::npos，不是 -1。

十、背诵自检清单（考场前过一遍）

点开逐条自检，能默写即过关
  • 万能头 + 快读快写，能写出 read() / write()，记得 LLINF
  • gcd / lcm、qpow 带模，闭眼写
  • 质数判断、埃氏筛 / 欧拉筛
  • 进制互转 toBase / fromBase
  • sort 自定义 cmp（多关键字）
  • 整数二分两套模板（找 >=x 与 <=x）
  • 前缀和 / 差分、桶计数
  • 栈、队列、优先队列、并查集 find/merge
  • DFS 回溯 + next_permutation + 组合枚举
  • BFS 模板（带 vis 与距离）
  • 记忆化搜索（memset(f,-1) 前置）
  • 01 背包 / 完全背包（容量倒序 vs 正序）
  • LIS（二分）、数字三角形、LCS
  • 邻接表 + Dijkstra + Floyd
  • Kruskal（依赖并查集）
  • 高精度加 / 减 / 乘 / 除、组合数预处理、字符串哈希
  • 回文双指针、string::find / substr 易错点
教练提醒

模板背得再熟，考场第一件事永远是"读题 + 定数据范围 + 选算法"：

  1. n ≤ 10 直接暴力 / 全排列；n ≤ 10^5 想 O(n log n)（排序、二分、堆、并查集）；n ≤ 5000 想 O(n^2)（DP / Floyd）。
  2. 每个数组开够大小，乘积和路径和用 long long。
  3. 多测题目记得每轮清空（memset / clear()）。
  4. 先写能拿部分分的暴力，再优化——OI 赛制按测试点给分，别空着。

随堂检测

1. 背包容量循环方向

01 背包用一维数组优化时，容量 j 的循环必须（ ）。

  • A. 正序 1 → m
  • B. 逆序 m → w[i]
  • C. 随便都可以
  • D. 从 m/2 开始
查看答案

答案：B（逆序保证每件物品只被考虑一次；完全背包才用正序）

2. Dijkstra 适用条件

朴素 Dijkstra 算法要求图中（ ）。

  • A. 可以有负权边
  • B. 边权必须非负
  • C. 必须是无向图
  • D. 节点数不超过 100
查看答案

答案：B（边权非负；有负权用 SPFA / Bellman-Ford，CSP-J 一般不考）

3. 二分查找前提

对一个数组使用二分查找（找某个值）前，该数组必须（ ）。

  • A. 元素互不相同
  • B. 已经有序
  • C. 元素都为正数
  • D. 长度为 2 的幂
查看答案

答案：B（二分依赖有序性）

4. 并查集路径压缩

并查集 find 函数中 fa[x] = find(fa[x]) 的作用是（ ）。

  • A. 合并两个集合
  • B. 路径压缩，降低树高，加快后续查找
  • C. 判断是否为根
  • D. 删除节点
查看答案

答案：B（路径压缩）

5. 记忆化搜索前置

使用 f 数组做记忆化搜索前，通常需要（ ）。

  • A. 把 f 全部初始化为 0
  • B. 把 f 全部初始化为 -1（或其他不可能的值）以区分"未计算"
  • C. 不需要初始化
  • D. 把 f 设为 INF
查看答案

答案：B（用 -1 标记"还没算过"，算过就直接返回）

SShowball OI知识手册