博客详情 - turing-code

杜昊阳的博客
请输入文本
杜昊阳 LV 6 @ 2026-6-27 15:53:27

1-二分查找

类比：猜 1~100 之间的数，每次告诉你"大了"还是"小了"——你每次猜中间，最多 7 次必中。

适用范围：有序数组中查找某个值

标准模板（闭区间）

int binarySearch(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;         // [l, r] 闭区间
    while (l <= r) {
        int mid = l + (r - l) / 2;       // 防溢出
        if (a[mid] == target) return mid;
        if (a[mid] < target) l = mid + 1; // 目标在右边
        else r = mid - 1;                  // 目标在左边
    }
    return -1;  // 没找到
}

lower_bound 模板（找第一个 ≥ target 的位置）

while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= target) r = mid;
    else l = mid + 1;
}

upper_bound 模板（找第一个 > target 的位置）

while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] > target) r = mid;
    else l = mid + 1;
}

初赛常考

给定数组，手动模拟二分查找的比较次数
二分查找的前提条件：有序
mid 取整方向决定了会不会死循环（l=mid 时小心）

2-排序算法

类比：整理扑克牌——插入排序是你一张张把牌插到正确位置；选择排序是每轮找最小的牌放前面；冒泡排序是相邻两张比较，大的往后冒。

冒泡排序 O(n²)

for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);

每轮把最大的冒到最后。

选择排序 O(n²)

for (int i = 0; i < n - 1; i++) {
    int k = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[k]) k = j;
    swap(a[i], a[k]);
}

每轮找最小的放前面。

插入排序 O(n²)

for (int i = 1; i < n; i++) {
    int key = a[i], j = i - 1;
    while (j >= 0 && a[j] > key) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = key;
}

像打牌一样插牌。

快速排序 O(n log n) — CSP-S

void qsort(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, p = a[l + (r - l) / 2];
    while (i <= j) {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
        if (i <= j) { swap(a[i], a[j]); i++; j--; }
    }
    qsort(l, j); qsort(i, r);
}

初赛常考

每种排序的时间复杂度（最好/最坏/平均）
手动模拟某轮排序后的数组状态
稳定排序：冒泡、插入、归并是稳定的；选择、快排不稳定
计数排序 O(n + k)：当数据范围小时用（比如成绩排序）

3-贪心

类比：自助餐——每次都拿当前最大的那块披萨。但不一定全局最优，得证明"当前最优 = 全局最优"。

适用条件

局部最优能推出全局最优
典型的"不用后悔"的问题

经典题型

1. 活动安排：选最多的不相交区间

sort(a, a + n, [](Node x, Node y) { return x.r < y.r; });
int cnt = 1, last = a[0].r;
for (int i = 1; i < n; i++)
    if (a[i].l >= last) { cnt++; last = a[i].r; }

按结束时间排序，每次选结束最早的。

2. 找零问题：用最少硬币凑出金额

硬币面值成倍数关系时（1, 2, 5, 10）→ 贪心
不成倍数时（1, 3, 4）→ DP

3. 哈夫曼编码：每次合并最小的两个

初赛常考

判断贪心策略是否正确（给个反例）
活动安排/排队问题的手动模拟

4-D(B)FS

类比：

DFS = 走迷宫，一条路走到黑，走不通退回来换条路（一根筋）
BFS = 水波纹，一圈一圈往外扩散（地毯式）

DFS 框架

void dfs(当前状态) {
    if (到达终点) { 更新答案; return; }
    if (剪枝条件) return;          // 优化：提前排除不可能的分支
    for (所有可能的下一步) {
        if (没走过) {
            标记走过;
            dfs(新状态);
            取消标记;               // 回溯
        }
    }
}

BFS 框架（求最短步数）

queue<int> q;
vis[start] = true;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (所有邻居 v) {
        if (!vis[v]) {
            vis[v] = true;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

BFS 第一次到达终点时就是最短路径。

初赛常考

手动模拟 DFS/BFS 的遍历顺序
判断哪个是 DFS 序 / BFS 序
回溯时为什么要取消标记？
DFS 栈实现 vs 递归实现

5-动态规划

类比：你从 1 楼爬到 10 楼，每层能爬 1 步或 2 步。到第 10 楼的方法数 = 到第 8 楼 + 到第 9 楼。把大问题拆成小问题，记住小问题的答案。

DP 五步法

状态定义：dp[i] 表示什么
初始条件：dp[0]、dp[1] 等
转移方程：dp[i] 怎么从之前的算出来
计算顺序：从小到大还是从大到小
答案：最终要输出哪个 dp

线性 DP — 最长上升子序列 LIS

// O(n²) 写法
vector<int> dp(n, 1);  // dp[i]: 以 a[i] 结尾的 LIS 长度
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        if (a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + 1);

// O(n log n) 写法（二分优化）
vector<int> lis;
for (int x : a) {
    auto it = lower_bound(lis.begin(), lis.end(), x);
    if (it == lis.end()) lis.push_back(x);
    else *it = x;
}

线性 DP — 最大子段和

int cur = 0, ans = INT_MIN;
for (int i = 0; i < n; i++) {
    cur = max(a[i], cur + a[i]);   // 继续加 or 重新开始
    ans = max(ans, cur);
}

背包 DP — 01 背包

// dp[v]: 容量 v 能装的最大价值
for (int i = 1; i <= n; i++)           // 遍历物品
    for (int v = V; v >= w[i]; v--)    // 倒序遍历容量！
        dp[v] = max(dp[v], dp[v - w[i]] + c[i]);

为什么倒序：保证每个物品只用一次（正序就变成完全背包了）。

背包 DP — 完全背包

for (int i = 1; i <= n; i++)
    for (int v = w[i]; v <= V; v++)    // 正序！
        dp[v] = max(dp[v], dp[v - w[i]] + c[i]);

初赛常考

填 DP 表（给转移方程，手动算几个格子）
判断哪个是正确的状态转移方程
背包容量遍历顺序（01 倒序，完全正序）

6-栈与队列

类比：

栈 = 一摞盘子，后进先出（LIFO）
队列 = 排队买奶茶，先进先出（FIFO）

栈的应用

括号匹配

stack<char> st;
for (char c : s) {
    if (c == '(' || c == '[' || c == '{') st.push(c);
    else if (st.empty() || !match(st.top(), c)) return false;
    else st.pop();
}
return st.empty();

表达式求值：中缀转后缀（逆波兰表达式）

队列的应用

单调队列 — 滑动窗口最大值

deque<int> q;  // 存下标，值单调递减
for (int i = 0; i < n; i++) {
    while (!q.empty() && q.front() < i - k + 1) q.pop_front(); // 出窗口
    while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();    // 维护单调性
    q.push_back(i);
    if (i >= k - 1) cout << a[q.front()] << ' ';
}

priority_queue — 优先队列（堆）

priority_queue<int> maxHeap;                              // 大根堆
priority_queue<int, vector<int>, greater<int>> minHeap;   // 小根堆

初赛常考

给一系列操作，模拟栈/队列里元素的变化
判断出入栈序列是否合法
后缀表达式的计算

7-前缀和差分

类比：你要知道一周内哪天的累计花费——每天记一下花了多少，到第 i 天的总花费 = 前 i 天的和。这就是前缀和。

一维前缀和

vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; i++)
    pre[i] = pre[i - 1] + a[i];   // pre[i]: 前 i 个元素的和

// 查询 [l, r] 的和 = pre[r] - pre[l - 1]

二维前缀和

vector<vector<int>> pre(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];

// 查询 (x1,y1) 到 (x2,y2) 的和
int sum = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];

差分 — 前缀和的逆运算

// 给 [l, r] 每个数都 + c
diff[l] += c;
diff[r + 1] -= c;

// 最后对 diff 求前缀和得到原数组

初赛常考

前缀和能 O(1) 求区间和，替代 O(n) 的暴力
二维前缀和容斥原理的公式
差分能 O(1) 完成区间修改

8-双指针

类比：两个人并排走，一个快一个慢，或者一个在前一个在后。典型应用：滑动窗口、有序数组合并。

两数之和（有序数组）

int i = 0, j = n - 1;
while (i < j) {
    if (a[i] + a[j] == target) { 找到; break; }
    else if (a[i] + a[j] < target) i++;
    else j--;
}

滑动窗口

int l = 0, r = 0;
while (r < n) {
    加入 a[r];            // 扩大窗口
    while (窗口不满足条件) {
        移除 a[l]; l++;    // 缩小窗口
    }
    更新答案;
    r++;
}

初赛常考

双指针相比双重循环的复杂度优势（O(n) vs O(n²)）
什么时候用双指针：有序、区间、子数组问题

9-并查集

类比：朋友圈——A 和 B 是朋友，B 和 C 是朋友，那 A、B、C 就在同一个圈子里。并查集就是管理这种"谁和谁是一伙的"的数据结构。

核心操作

int fa[N];

// 初始化：每个人是自己的老大
for (int i = 1; i <= n; i++) fa[i] = i;

// 找根（路径压缩）
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);  // 路径压缩
    return fa[x];
}

// 合并两个集合
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}

带权并查集（扩展）

int w[N];
// find 时同时维护到根的距离/权值

初赛常考

给一系列合并操作，问最终有几个集合
路径压缩的作用（把树压平，下次 find 更快）
判断是否是二分图 → 双栈排序

10-图论基础

类比：地图——城市是顶点，路是边。最短路就是找从 A 到 B 最近的路。

存图方式

邻接矩阵：g[i][j] 表示 i 到 j 有边

vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));

邻接表（常用）：

vector<pair<int, int>> g[n + 1];  // g[u] = {(v, w), ...}
g[u].push_back({v, w});

Dijkstra（单源最短路，无负权边）O(m log n)

vector<int> dist(n + 1, INF);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;           // 已过时
    for (auto [v, w] : g[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

核心思想：每次选当前距离最小的顶点。

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

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];

最小生成树 — Kruskal O(m log m)

// 1. 按边权排序
sort(edges, edges + m, [](Edge a, Edge b) { return a.w < b.w; });
// 2. 从小到大选边，用并查集判断是否会成环
int cnt = 0, ans = 0;
for (int i = 0; i < m; i++) {
    if (find(edges[i].u) != find(edges[i].v)) {
        merge(edges[i].u, edges[i].v);
        ans += edges[i].w;
        if (++cnt == n - 1) break;
    }
}

拓扑排序（有向无环图）

vector<int> inDeg(n + 1);
// 计算入度，入度为 0 的入队
queue<int> q;
for (int i = 1; i <= n; i++)
    if (inDeg[i] == 0) q.push(i);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u])
        if (--inDeg[v] == 0) q.push(v);
}

初赛常考

Dijkstra 手动模拟过程
Floyd 三重循环的 k 为什么在最外层
拓扑排序的序列是否唯一
什么图有拓扑序（DAG）

11-数论基础

GCD / LCM

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }  // 先除再乘防溢出

质数判定

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

质数筛 — 埃氏筛 O(n log log n)

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++)
    if (isPrime[i])
        for (int j = i * i; j <= n; j += i)
            isPrime[j] = false;

质数筛 — 线性筛 O(n)

vector<int> primes;
vector<bool> isPrime(n + 1, true);
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push_back(i);
    for (int p : primes) {
        if (i * p > n) break;
        isPrime[i * p] = false;
        if (i % p == 0) break;  // 关键：保证每个合数只被最小质因子筛掉
    }
}

快速幂

int qpow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

初赛常考

进制转换（二进制、八进制、十六进制互转）
位运算（& | ^ ~ << >>）
质数判定和筛法的时间复杂度比较
模运算的基本性质

请输入文本

目录

1-二分查找

标准模板（闭区间）

lower_bound 模板（找第一个 ≥ target 的位置）

upper_bound 模板（找第一个 > target 的位置）

初赛常考

2-排序算法

冒泡排序 O(n²)

选择排序 O(n²)

插入排序 O(n²)

快速排序 O(n log n) — CSP-S

初赛常考

3-贪心

适用条件

经典题型

初赛常考

4-D(B)FS

DFS 框架

BFS 框架（求最短步数）

初赛常考

5-动态规划

DP 五步法

线性 DP — 最长上升子序列 LIS

线性 DP — 最大子段和

背包 DP — 01 背包

背包 DP — 完全背包

初赛常考

6-栈与队列

栈的应用

队列的应用

priority_queue — 优先队列（堆）

初赛常考

7-前缀和差分

一维前缀和

二维前缀和

差分 — 前缀和的逆运算

初赛常考

8-双指针

两数之和（有序数组）

滑动窗口

初赛常考

9-并查集

核心操作

带权并查集（扩展）

初赛常考

10-图论基础

存图方式

Dijkstra（单源最短路，无负权边）O(m log n)

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

最小生成树 — Kruskal O(m log m)

拓扑排序（有向无环图）

初赛常考

11-数论基础

GCD / LCM

质数判定

质数筛 — 埃氏筛 O(n log log n)

质数筛 — 线性筛 O(n)

快速幂

初赛常考

状态

开发

支持

关于

登录