竞赛编程¶

一、算法分类详解¶

基础算法¶

算法	用途	时间复杂度	难度
排序（快排/归并）	数据整理	O(n log n)	⭐
二分查找	有序数组快速搜索	O(log n)	⭐
双指针	区间问题、滑动窗口	O(n)	⭐⭐
前缀和与差分	区间求和与更新	O(n) 预处理	⭐
贪心算法	局部最优→全局最优	视问题而定	⭐⭐

排序算法详解¶

// 快速排序（C++ 实现）
void quick_sort(int arr[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = arr[(l + r) >> 1];
    while (i < j) {
        do i++; while (arr[i] < x);
        do j--; while (arr[j] > x);
        if (i < j) swap(arr[i], arr[j]);
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

// 归并排序
void merge_sort(int arr[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i++, j++) arr[i] = tmp[j];
}

搜索算法¶

算法	用途	空间复杂度	难度
DFS（深度优先搜索）	所有可能路径、排列组合	O(h) 递归深度	⭐⭐
BFS（广度优先搜索）	最短路径、层序遍历	O(w) 最大宽度	⭐⭐
回溯	约束满足问题（N皇后、数独）	视剪枝情况	⭐⭐⭐

BFS 最短路径模板：

queue<int> q;
vector<int> dist(n + 1, -1);
dist[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : graph[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

动态规划（DP）¶

DP 是竞赛中最重要也是最难的算法之一，核心思想是将原问题拆分为子问题，记录子问题的解避免重复计算。

DP 解题步骤： 1. 确定状态定义（dp[i] 或 dp[i][j] 表示什么） 2. 确定状态转移方程 3. 确定初始条件和边界 4. 确定遍历顺序

经典 DP 问题： | 问题 | 状态定义 | 转移方程 | |------|---------|---------| | 斐波那契 | dp[i] = 第 i 项 | dp[i] = dp[i-1] + dp[i-2] | | 0-1 背包 | dp[i][j] = 前 i 个物品容量 j 的最大价值 | dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) | | 最长上升子序列（LIS） | dp[i] = 以 i 结尾的 LIS 长度 | dp[i] = max(dp[j] + 1) (j < i, a[j] < a[i]) | | 最长公共子序列（LCS） | dp[i][j] = s1[0..i] 和 s2[0..j] 的 LCS | dp[i][j] = dp[i-1][j-1] + 1 (s1[i]=s2[j]) |

0-1 背包模板：

// 一维优化
vector<int> dp(m + 1, 0);
for (int i = 0; i < n; i++) {
    for (int j = m; j >= w[i]; j--) {  // 倒序保证每个物品只用一次
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

图论算法¶

算法	用途	时间复杂度	难度
Dijkstra	单源最短路径（无负权）	O((n+m) log n)	⭐⭐⭐
Floyd-Warshall	多源最短路径	O(n³)	⭐⭐
Kruskal	最小生成树	O(m log m)	⭐⭐⭐
拓扑排序	有向无环图排序	O(n+m)	⭐⭐
并查集	连通性判断	O(α(n)) 近似常数	⭐⭐

Dijkstra 模板：

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

二、竞赛平台推荐¶

平台	特点	适合人群	网址
洛谷	中文界面，题目分级，题解丰富	入门到进阶	luogu.com.cn
Codeforces	国际平台，每周比赛，题目质量高	中级到高级	codeforces.com
AtCoder	日系平台，题目友好，难度适中	中级	atcoder.jp
蓝桥杯	国内竞赛，分省赛/国赛	入门到中级	dasai.lanqiao.cn
NowCoder（牛客）	国内平台，题型全面	入门到进阶	nowcoder.com
LeetCode	面试刷题为主，专题分类好	算法练习	leetcode.cn

三、系统学习路线¶

入门阶段（目标：省赛三等奖）¶

C/C++ 基础语法
    ↓（1~2 个月）
基础算法：枚举、模拟、排序、二分
    ↓（1~2 个月）
数据结构：数组、链表、栈、队列
    ↓（1 个月）
在洛谷刷入门题（难度：红题 → 橙题）

推荐题单：洛谷【入门 1】~【入门 4】

进阶阶段（目标：省赛一等奖）¶

搜索与图论：DFS、BFS、最短路径、并查集
    ↓（2~3 个月）
动态规划入门：背包、线性 DP、区间 DP
    ↓（2~3 个月）
数据结构进阶：线段树、树状数组、ST 表
    ↓（1~2 个月）
在 Codeforces 刷 1200~1600 分的题

高级阶段（目标：国奖/ACM 区域赛）¶

高级 DP：状压 DP、树形 DP、数位 DP
    ↓
字符串算法：KMP、AC 自动机、后缀数组
    ↓
高级图论：网络流、二分图匹配、强连通分量
    ↓
数论：快速幂、欧拉函数、组合数学
    ↓
参加 Codeforces 周赛、AtCoder ABC、区域赛

四、刷题策略¶

分类训练法¶

每周专注一种算法类型，精刷 10~15 道题：

周次	主题	目标
第 1 周	枚举与模拟	掌握暴力解法
第 2 周	排序与二分	掌握分治思想
第 3~4 周	搜索（DFS/BFS）	熟练掌握回溯
第 5~6 周	动态规划入门	掌握常见模型
第 7~8 周	图论基础	掌握最短路和 MST
第 9~10 周	数据结构	线段树/树状数组

刷题步骤¶

独立思考：至少 20 分钟尝试自己解决问题
查看题解：学习他人的思路，理解多种解法
自己实现：不看题解重新写一遍代码
总结归纳：记录本题用到的方法和技巧
举一反三：找同类型的题目巩固练习

五、比赛技巧¶

赛场策略¶

先易后难：先把所有题都看一遍，从最有把握的开始做
暴力保底：难题先写暴力解，至少拿到部分分数
时间分配：每道题如果 30 分钟没有思路，先跳过去做其他题
特判边界：注意 n=0、n=1、最大值、最小值等边界情况
对拍调试：写一个暴力程序 + 随机数据生成器，和正解对拍

常用技巧¶

读入优化：使用 ios::sync_with_stdio(false) 或 scanf/printf
数组开大：多开 5~10 个空间防止越界
数据类型：注意 int 溢出，使用 long long
常量定义：const int INF = 0x3f3f3f3f; 常用无穷大
输出格式：注意题目要求的输出格式，空格和换行

六、推荐学习资源¶

资源	类型	推荐理由
《算法竞赛入门经典》（刘汝佳）	书籍	竞赛入门必读，紫书
《算法导论》（CLRS）	书籍	理论严谨，全面深入
洛谷网校	在线课程	体系化视频课程
OI-Wiki	在线文档	全面系统的竞赛知识库
Codeforces Blog	社区	高质量算法教程

练习¶

动手实践

在洛谷上搜索"P1001"完成 A+B 问题
实现快速排序和归并排序
用 Dijkstra 算法求单源最短路径
完成一个 0-1 背包问题的完整代码