算法竞赛 · 从零到精通 · 13 讲

第 1 讲 · 开始之前：环境、平台与心态

1. 选一门语言

• 正式比赛主流是 C++（速度快、模板多），推荐直接用 C++ 备战。
• 只想先体验、或以后搞数据方向：用 Python（本站有独立的 Python 入门课）。

2. 装环境（10 分钟）

• 下载任一编译器：Windows 推荐 Dev-C++ 或 VS Code + MinGW；或者直接用在线环境（洛谷 IDE、Codeforces 自带）。
• 基本框架（往后的代码都在这个框架里写）：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;      // 读入两个数
    cout << a + b << endl; // 输出它们的和
    return 0;
}

3. 注册一个平台并提交第一题

• 推荐先在 Codeforces 注册：打开题目列表 → 按难度排序 → 选最简单的一道 → 写代码 → Submit。
• 提交后看到绿色的 Accepted（AC）就成功了；红色的 Wrong Answer（WA）会告诉你哪组数据没过。

第 2 讲 · 复杂度：让你的程序"跑得动"

竞技编程的第一思维不是"对不对"，而是"快不快"。评测机大约每秒能执行 1 亿次左右的基本操作。

记一张速查表（1 秒时限内）

• n ≤ 10⁶：只能 O(n) 或 O(n log n)
• n ≤ 5000：O(n²) 可以
• n ≤ 300：O(n³) 可以
• n ≤ 20：状态压缩 / 枚举子集（2ⁿ）
• n ≤ 10：全排列枚举（10! = 362 万）

例子

// 求 1+2+...+n
// 慢：循环 O(n)
long long s = 0;
for (int i = 1; i <= n; i++) s += i;
// 快：公式 O(1)
long long s2 = 1LL * n * (n + 1) / 2;

第 3 讲 · 数组、字符串与"模拟"

要点

• 数组：int a[100005]; 开在外层（全局）会自动清零且不会爆栈。
• 字符串：string s; 支持 s.size()、s[i]、s.substr(l, len)。
• 模拟题三件套：读清规则 → 用循环一步步做 → 注意边界（第 1 个、最后一个、等于号）。

例题（洛谷风格）：统计一句话里的大写字母数量

string s; getline(cin, s);
int cnt = 0;
for (char c : s)
    if (c >= 'A' && c <= 'Z') cnt++;
cout << cnt << endl;

第 4 讲 · 排序与二分

排序：一行解决

int a[1005], n;
sort(a, a + n);              // 升序
sort(a, a + n, greater<int>()); // 降序
// 结构体排序
struct P { int x, y; };
bool cmp(const P& a, const P& b){ return a.x < b.x; }
sort(p, p + m, cmp);

二分：在"单调世界"里找答案

两种用法：一、 在有序数组里找某个值；二、 答案具有单调性时二分答案（"最大的最小值""能不能做到"类问题）。

// 在升序数组 a 里找 x 是否存在
int l = 0, r = n - 1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] == x) { /* 找到 */ break; }
    if (a[mid] < x) l = mid + 1; else r = mid - 1;
}

第 5 讲 · 前缀和与差分

前缀和（快速求区间和）

long long pre[100005];
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];
// 区间 [l, r] 的和：
long long ans = pre[r] - pre[l-1];

差分（快速区间加）

// 让 [l, r] 全部 +v：
diff[l] += v; diff[r+1] -= v;
// 结束后求前缀和还原：
for (int i = 1; i <= n; i++) a[i] = a[i-1] + diff[i];

第 6 讲 · 栈、队列与链表

• 栈 stack：后进先出。典型场景：括号匹配、撤销、单调栈找"下一个更大元素"。
• 队列 queue：先进先出。典型场景：排队模拟、BFS（下一讲）。
• 链表：节点 + 指针/数组模拟（nxt[i]），用于频繁插入删除。

// 括号匹配
stack<char> st; bool ok = true;
for (char c : s) {
    if (c == '(') st.push(c);
    else if (c == ')') {
        if (st.empty()) { ok = false; break; }
        st.pop();
    }
}
if (!st.empty()) ok = false;
cout << (ok ? "YES" : "NO") << endl;

第 7 讲 · 递归与深度优先搜索（DFS）

递归三要素

• 终止条件（到了最底层做什么）
• 缩小问题（自己调用自己，但规模更小）
• 回溯（走不通时退回上一步，恢复现场）

// 求 n 的阶乘（最简单的递归）
long long fac(int n) {
    if (n <= 1) return 1;      // 终止
    return n * fac(n - 1);      // 缩小规模
}
// DFS 框架（网格）
int n, m; bool vis[1005][1005];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
void dfs(int x, int y) {
    vis[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny])
            dfs(nx, ny);
    }
}