洛谷题单：例题与作业

14.1 怎么用这份题单

14.2 分阶段作业计划

14.3 第 01~04 讲 · 线性结构题单

14.3.1 数组、模拟与栈

14.3.2 队列与单调结构

14.3.3 串与 KMP

14.3.4 例题精讲：KMP 模板题（P3375）

#include <bits/stdc++.h>
using namespace std;

/* 洛谷 P3375【模板】KMP
   输入：两行，第一行主串 S，第二行模式串 P
   输出：第一行所有匹配位置（1 基下标，空格分隔，行末也有空格）
         第二行模式串的 next 数组（教材 1 基约定：next[1]=0, next[i]=最长相等真前后缀长度+1） */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, p;
    cin >> s >> p;
    int n = s.size(), m = p.size();

    /* ---------- 1. 求 next 数组（1 基，教材约定） ----------
       nxt[i] 表示：p[1..i-1] 的最长相等真前后缀长度 + 1
       等价于 0 基前缀函数 pi 的 "pi[i-2] + 1" */
    vector<int> nxt(m + 1, 0);
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && p[i - 1] != p[j]) j = nxt[j];   // 注意：教材的写法是 j = nxt[j]
        if (p[i - 1] == p[j]) ++j;
        nxt[i] = j;
    }

    /* ---------- 2. KMP 匹配（1 基） ---------- */
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && s[i - 1] != p[j]) j = nxt[j];
        if (s[i - 1] == p[j]) ++j;
        if (j == m) {                       // 匹配成功，起点是 i - m + 1
            cout << i - m + 1 << ' ';
            j = nxt[j];                     // 继续找下一次出现（若只要第一次则 break）
        }
    }
    cout << '\n';

    /* ---------- 3. 输出 next[1..m] ---------- */
    for (int i = 1; i <= m; ++i) cout << nxt[i] << ' ';
    cout << '\n';
    return 0;
}

14.3.5 例题精讲：归并排序求逆序对（P1908）

逆序对是「排序 + 分治」的经典结合。归并排序在合并两个有序段时，如果右边段的元素 先被放进结果数组，就说明它比左边段剩下的所有元素都小——这一批「左边剩余元素」恰好构成 「以该元素为右端点的逆序对」。于是统计工作可以完全融进归并过程，不增加任何复杂度。

#include <bits/stdc++.h>
using namespace std;

/* 洛谷 P1908 逆序对
   思路：归并排序的同时统计逆序对，O(n log n)
   关键：合并时若右段元素先出，则它与"左段剩余的所有元素"都构成逆序对，
        一次累加 mid - i + 1 个（这里用 1 基的 [l, mid] 与 [mid+1, r]） */
long long ans = 0;                     // 逆序对数最多 n(n-1)/2，n = 5e5 时约 1.25e11，必须开 long long
vector<int> a, tmp;

void msort(int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;         // 防止 (l + r) 溢出
    msort(l, mid);
    msort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {            // 取等号放左边，保证稳定性
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            ans += mid - i + 1;        // 左段从 i 到 mid 的元素都比 a[j] 大
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int t = l; t <= r; ++t) a[t] = tmp[t];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    a.assign(n + 1, 0);
    tmp.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    msort(1, n);
    cout << ans << '\n';
    return 0;
}

/* 另一种同样常见的写法：树状数组 + 离散化
   思路：把元素按值离散化成 1..k，从后往前扫，
        每次查询"比当前元素小的已出现个数"即为其贡献的逆序对数。
   复杂度同样是 O(n log n)，但常数更小、代码更短（适合作为对拍的第二个实现）。 */

14.3.6 例题精讲：单调队列求滑动窗口最大值（P1886）

单调队列的思想是：如果一个元素比队尾元素更大、而且位置更靠后，那么队尾元素永远不可能再成为答案， 于是可以直接把它从队尾弹掉。每个元素最多入队一次、出队一次，所以整个算法是 O(n)。

#include <bits/stdc++.h>
using namespace std;

/* 洛谷 P1886 滑动窗口 /【模板】单调队列
   输入：n k，然后 n 个整数
   输出：第一行每个窗口的最小值，第二行每个窗口的最大值 */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    deque<int> dq;                       // 存"下标"，队列里的值保持单调

    /* ---------- 最小值：维护单调递增队列 ---------- */
    for (int i = 1; i <= n; ++i) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();  // 队尾更大且更靠前 → 永远用不上
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();                     // 队首滑出窗口
        if (i >= k) cout << a[dq.front()] << ' ';
    }
    cout << '\n';

    /* ---------- 最大值：维护单调递减队列（只需把比较方向反过来） ---------- */
    dq.clear();
    for (int i = 1; i <= n; ++i) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k) cout << a[dq.front()] << ' ';
    }
    cout << '\n';
    return 0;
}

14.4 第 05~07 讲 · 串、树与堆题单

14.5 第 08~09 讲 · 图论题单

14.5.1 图的遍历

14.5.2 最短路

14.5.3 生成树、拓扑与关键路径

14.5.4 例题精讲：堆优化 Dijkstra 完整模板（P4779 风格）

最短路题的难点往往不在算法本身，而在「建图 + 松弛 + 路径还原 + 边界」四件事都要写对。 下面这份模板把这些全都包含进去了，可以直接当比赛模板用。

#include <bits/stdc++.h>
using namespace std;

/* 洛谷 P4779【模板】单源最短路径（标准版）
   要求：n, m 到 1e5 级别，边权非负，输出源点到每个点的最短路长度（不可达输出 2^31-1）
   这份模板同时演示：链式前向星建图、堆优化 Dijkstra、路径还原、long long 防溢出 */
const int MAXN = 100005;
const long long LINF = (1LL << 62);

int head[MAXN], nxt[MAXN * 2], to[MAXN * 2], wt[MAXN * 2], ecnt = 0;
/* 注意：无向图每条边要加两次，所以数组要开 2*m；有向图开 m 即可 */

void addEdge(int u, int v, int w) {
    to[ecnt] = v; wt[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt++;
}

int n, m, s;
vector<long long> dist;
vector<int> pre;                      // 路径还原：pre[v] = 最短路树上 v 的父结点

void dijkstra(int src) {
    dist.assign(n + 1, LINF);
    pre.assign(n + 1, 0);
    /* 小根堆：pair 的 first 是距离，默认按 first 比较；greater<> 让它变成小根堆 */
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;      // 关键！堆里可能有过期状态，必须跳过
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (d + wt[e] < dist[v]) {  // 松弛
                dist[v] = d + wt[e];
                pre[v] = u;             // 记录是从 u 走过来的
                pq.push({dist[v], v});
            }
        }
    }
}

/* 还原 src → t 的路径（不含 src 时把 src 排除即可） */
vector<int> getPath(int src, int t) {
    vector<int> path;
    if (dist[t] == LINF) return path;   // 不可达
    for (int cur = t; cur != 0; cur = pre[cur]) {
        path.push_back(cur);
        if (cur == src) break;
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s;
    memset(head, -1, sizeof(int) * (n + 1));   // 只清零前 n+1 个，避免 O(MAXN) 的常数
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);                      // 有向图加一次；无向图这里要再加一条 addEdge(v, u, w)
    }
    dijkstra(s);
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == LINF) cout << (1LL << 31) - 1 << ' ';   // 按题目要求输出不可达的表示
        else cout << dist[i] << ' ';
    }
    cout << '\n';

    /* 示例：输出 s → n 的路径（很多最短路题的第二问都是这个） */
    vector<int> path = getPath(s, n);
    for (size_t i = 0; i < path.size(); ++i) {
        cout << path[i];
        if (i + 1 < path.size()) cout << " -> ";
    }
    if (!path.empty()) cout << '\n';
    return 0;
}

14.6 第 10~12 讲 · 查找、排序与 DP 题单

14.7 进阶挑战（学有余力）

14.8 调试与对拍：自己造数据验证程序

做题最容易卡在「样例过了但提交 WA」。这时候不要干瞪眼，用对拍： 写一个慢但一定正确的暴力程序，再写一个随机数据生成器，循环比较两者输出。

/* ============ 对拍三件套之 ①：暴力程序 brute.cpp ============
   以「求数组区间和」为例，暴力就是每次都老老实实累加 */
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    while (q--) {
        int l, r;
        cin >> l >> r;
        long long s = 0;
        for (int i = l; i <= r; ++i) s += a[i];   // O(n) 暴力
        cout << s << '\n';
    }
    return 0;
}

/* ============ 对拍三件套之 ②：数据生成器 gen.cpp ============
   生成 n ≤ 10 的小数据，便于暴露边界问题 */
#include <bits/stdc++.h>
using namespace std;
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n = rng() % 10 + 1;            // 1 ~ 10
    int q = rng() % 10 + 1;            // 1 ~ 10
    cout << n << ' ' << q << '\n';
    for (int i = 1; i <= n; ++i) cout << (int)(rng() % 21 - 10) << " \n"[i == n];
    for (int i = 0; i < q; ++i) {
        int l = rng() % n + 1, r = rng() % n + 1;
        if (l > r) swap(l, r);
        cout << l << ' ' << r << '\n';
    }
    return 0;
}

:: ============ 对拍三件套之 ③：批处理脚本（Windows） ============
:: 把三个文件编译后放在同一目录，双击运行即可
@echo off
g++ brute.cpp -O2 -o brute.exe
g++ mine.cpp  -O2 -o mine.exe
g++ gen.cpp   -O2 -o gen.exe
for /l %%i in (1,1,1000) do (
    gen.exe > in.txt
    brute.exe < in.txt > brute.out
    mine.exe  < in.txt > mine.out
    fc brute.out mine.out > nul
    if errorlevel 1 (
        echo **************** 第 %%i 组数据 WA 了！****************
        type in.txt
        echo ---------- 暴力输出 ----------
        type brute.out
        echo ---------- 你的输出 ----------
        type mine.out
        pause
        exit /b
    )
)
echo 全部通过！
pause

14.9 本章小结