第十六章竞赛技巧¶

算法和数据结构是核心实力，但竞赛技巧决定了你能否在有限时间内充分发挥实力。本章汇总了从读入优化到比赛策略的各类实战技巧，帮助你在赛场上做到"该拿的分一分不丢，能多拿的分尽量多拿"。

16.1 竞赛常用代码模板¶

在竞赛中，提前准备好常用的代码模板可以节省大量时间。以下是最常用的几类模板。

16.1.1 快读（快写）模板¶

标准的 scanf 或 cin 在面对 \(10^6\) 级别以上的整数输入时可能成为瓶颈。使用 getchar_unlocked 或 fread 可以将读入速度提升数倍。

为什么快读更快？

scanf / cin 在每次读入时都要进行格式化解析、类型检查等额外工作。
getchar_unlocked 是非线程安全版本的 getchar，省去了加锁开销，在竞赛单线程环境下完全可用。
fread 则是将大量数据一次性读入缓冲区，再逐字节解析，减少了系统调用次数。

基于 getchar_unlocked 的快读¶

#include <cstdio>
#include <cctype>

// 快读函数：读入一个非负整数
// 原理：逐字符读取，跳过非数字字符，累加计算数值
inline int read() {
    int x = 0;
    char ch = getchar_unlocked();
    // 跳过前导空白字符（空格、换行等）
    while (!isdigit(ch)) ch = getchar_unlocked();
    // 逐位累加数字
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar_unlocked();
    }
    return x;
}

// 支持负数的快读
inline int read_signed() {
    int x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch) && ch != '-') ch = getchar_unlocked();
    if (ch == '-') {
        f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar_unlocked();
    }
    return x * f;
}

// 快写函数：输出一个非负整数
inline void write(int x) {
    if (x < 0) {
        putchar_unlocked('-');
        x = -x;
    }
    if (x > 9) write(x / 10); // 递归输出高位
    putchar_unlocked(x % 10 + '0');
}

// 输出整数并换行
inline void writeln(int x) {
    write(x);
    putchar_unlocked('\n');
}

基于 fread 的更快读入¶

#include <cstdio>
#include <cctype>

// 使用 fread 一次性读入大量数据到缓冲区
// 适用于输入量特别大的场景（如 10^7 级别数据）
struct FastIO {
    static const int BUFSIZE = 1 << 20; // 1MB 缓冲区
    char buf[BUFSIZE], *p1, *p2;

    FastIO() : p1(buf), p2(buf) {}
    // 当缓冲区读完时，重新填充
    inline char gc() {
        if (p1 == p2) {
            p1 = buf;
            p2 = buf + fread(buf, 1, BUFSIZE, stdin);
            if (p1 == p2) return EOF;
        }
        return *p1++;
    }

    // 读入整数
    inline int read() {
        int x = 0;
        char ch = gc();
        while (!isdigit(ch)) ch = gc();
        while (isdigit(ch)) {
            x = x * 10 + (ch - '0');
            ch = gc();
        }
        return x;
    }

    // 读入 long long
    inline long long read_ll() {
        long long x = 0;
        char ch = gc();
        while (!isdigit(ch)) ch = gc();
        while (isdigit(ch)) {
            x = x * 10 + (ch - '0');
            ch = gc();
        }
        return x;
    }
} io;

int main() {
    int n = io.read(); // 使用示例：读入一个整数
    printf("%d\n", n);
    return 0;
}

快读使用的注意事项

getchar_unlocked 在 Windows 的 MinGW 环境下可能不可用，此时可用 getchar 替代（速度略慢但依然比 scanf 快）。
快读不能与 cin / scanf 混用，否则会因为缓冲区不同步而出错。
在某些 OJ 上（如洛谷），提交时需检查编译器是否支持对应函数。

16.1.2 常用宏定义¶

宏定义能大幅缩短代码量，减少模板代码的书写时间。以下是竞赛中最常用的宏定义集合：

// ==================== 基础类型与容器 ====================
#define pii pair<int, int>       // 常用于存坐标、区间等二元组
#define pll pair<long long, long long>  // long long 版本的二元组
#define pdd pair<double, double> // 浮点数二元组
#define vi vector<int>           // 整数向量
#define vl vector<long long>     // long long 向量
#define vvi vector<vector<int>>  // 二维整数向量（邻接矩阵等）

// ==================== 容器操作 ====================
#define pb push_back             // 在 vector 末尾添加元素
#define pf push_front            // 在 deque 队首添加元素
#define mp make_pair             // 构造 pair（C++11 后可用 {} 替代）
#define all(x) (x).begin(), (x).end()   // 表示整个容器的范围
#define rall(x) (x).rbegin(), (x).rend() // 逆序表示整个容器
#define sz(x) (int)(x).size()    // 容器大小

// ==================== 循环相关 ====================
#define rep(i, a, b) for (int i = (a); i < (b); i++)       // 左闭右开循环
#define repd(i, a, b) for (int i = (a); i >= (b); i--)     // 逆序循环
#define repi(i, a, b) for (int i = (a); i <= (b); i++)     // 左闭右闭循环

// ==================== 常用值 ====================
#define INF 0x3f3f3f3f            // int 型无穷大（约为 10^9）
#define LLINF 0x3f3f3f3f3f3f3f3fLL // long long 型无穷大
#define MOD 1000000007            // 常见取模值 10^9+7
#define MOD2 998244353            // 常见取模值 998244353
#define eps 1e-9                  // 浮点数比较精度
#define PI acos(-1.0)             // 圆周率

// ==================== 调试相关 ====================
// 注意：dbg 宏用到 cerr / endl，需要 #include <iostream> 与 using namespace std;
// （使用 #include <bits/stdc++.h> 的模板已自动包含，无需额外处理）
#define dbg(x) cerr << #x << " = " << (x) << endl
#define dbg2(x, y) cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

使用示例：

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

#define pii pair<int, int>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); i++)

int main() {
    // 使用 pii 存储坐标
    vector<pii> points;
    points.pb({1, 2});
    points.pb({3, 4});

    // 使用 rep 遍历
    rep(i, 0, sz(points)) {
        printf("点 %d: (%d, %d)\n", i, points[i].first, points[i].second);
    }

    // 使用 all 排序整个容器
    sort(all(points));

    return 0;
}

宏定义的陷阱

宏定义是简单的文本替换，不进行类型检查。sz(x) 展开后只出现一次 x，本身没有重复求值的问题。
真正有坑的是参数出现多次的宏：all(x) 展开为 (x).begin(), (x).end()，x 会被求值两次。传普通变量（如 all(v)）完全安全，但若传入带副作用的表达式，如 all(vs[i++])，i 会被自增两次，产生难以察觉的 bug。
建议在正式工程中使用函数或 constexpr，但在竞赛中宏定义的简洁性更重要。

16.1.3 对拍脚本¶

对拍（Stress Testing）是竞赛中调试的终极武器。核心思想：用暴力解法（保证正确但可能很慢）和你的解法对比大量随机数据，找到两者输出不同的数据作为反例。

对拍的完整工作流程

编写暴力解法 brute.cpp：用最朴素的方法求解，确保逻辑正确。
编写数据生成器 gen.cpp：生成随机的合法输入数据。
编写你的解法 solution.cpp：你认为正确的算法实现。
运行对拍脚本：不断生成数据，对比两个解法的输出，直到发现不一致。

数据生成器 gen.cpp¶

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>

// 生成 [l, r] 范围内的随机整数
int randInt(int l, int r) {
    return l + rand() % (r - l + 1);
}

int main(int argc, char* argv[]) {
    // 使用命令行参数作为随机种子，确保每次运行生成不同数据
    srand(atoi(argv[1]));

    int n = randInt(1, 100); // 随机生成 n 的大小
    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        printf("%d ", randInt(-1000, 1000)); // 随机生成数组元素
    }
    printf("\n");
    return 0;
}

对拍脚本 stress_test.sh¶

#!/bin/bash

# 对拍脚本：持续生成随机数据，比较两个解法的输出
# 用法：chmod +x stress_test.sh && ./stress_test.sh

echo "开始编译..."
g++ -O2 -o gen gen.cpp
g++ -O2 -o solution solution.cpp
g++ -O2 -o brute brute.cpp

if [ $? -ne 0 ]; then
    echo "编译失败！"
    exit 1
fi

echo "编译完成，开始对拍..."

for ((i = 1; i <= 10000; i++)); do
    # 用 i 作为随机种子生成测试数据
    ./gen $i > input.txt

    # 运行你的解法
    ./solution < input.txt > output_sol.txt

    # 运行暴力解法
    ./brute < input.txt > output_bf.txt

    # 比较输出
    if ! diff -q output_sol.txt output_bf.txt > /dev/null 2>&1; then
        echo "=== 第 $i 组数据发现差异！==="
        echo "--- 输入数据 ---"
        cat input.txt
        echo "--- 你的解法输出 ---"
        cat output_sol.txt
        echo "--- 暴力解法输出 ---"
        cat output_bf.txt
        echo "差异已保存在 input.txt 中，请手动调试。"
        exit 1
    fi

    # 每 100 组输出进度
    if ((i % 100 == 0)); then
        echo "已完成 $i 组测试，全部通过。"
    fi
done

echo "所有 10000 组测试数据全部通过！"

对拍的最佳实践

数据范围不要设太大，暴力解法要能在几秒内跑完。通常 \(n \le 100\) 或 \(n \le 50\) 即可。
对于浮点数题目，不能直接比较输出，需要判断差值是否在精度范围内。
可以在发现错误数据后手动缩小数据范围，便于调试。
建议对拍通过后再增大数据范围验证复杂度是否正确（即不会超时）。

16.1.4 调试技巧¶

竞赛中的调试效率直接影响解题速度。以下是几种高效的调试方法：

方法一：使用 cerr 输出调试信息¶

#include <cstdio>
#include <iostream>  // cerr 定义在 <iostream> 中，只 include <cstdio> 无法编译
using namespace std;

// cerr 不会被重定向到文件，非常适合调试
// 当你用 ./solution < input.txt > output.txt 时，
// printf 的内容写入 output.txt，但 cerr 的内容仍然显示在终端
void debug_array(int a[], int n) {
    cerr << "数组内容: [";
    for (int i = 0; i < n; i++) {
        if (i > 0) cerr << ", ";
        cerr << a[i];
    }
    cerr << "]" << endl;
}

方法二：条件编译¶

#include <cstdio>
#include <iostream>  // dbg 宏用到 cerr，必须包含 <iostream>
using namespace std;

// 只在本地调试时开启，提交时去掉 -DLOCAL 编译选项即可关闭
#ifdef LOCAL
    #define dbg(x) cerr << #x << " = " << (x) << endl
    #define dbgarr(a, n) do { \
        cerr << #a << " = ["; \
        for (int _i = 0; _i < n; _i++) { \
            if (_i) cerr << ", "; \
            cerr << a[_i]; \
        } \
        cerr << "]" << endl; \
    } while (0)
#else
    #define dbg(x)
    #define dbgarr(a, n)
#endif

int main() {
    int a[] = {3, 1, 4, 1, 5, 9};
    int n = 6;

    dbg(n);          // 只在定义了 LOCAL 时输出
    dbgarr(a, n);    // 只在定义了 LOCAL 时输出

    // 正式代码...
    int sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    dbg(sum);        // 输出: sum = 23

    return 0;
}

方法三：善用 assert¶

#include <cassert>
#include <cstdio>

int binarySearch(int a[], int n, int target) {
    int l = 0, r = n - 1;
    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;
    }
    // 在函数末尾添加 assert 检查返回值的合法性
    return -1; // 未找到
}

int main() {
    int a[] = {1, 3, 5, 7, 9};
    int n = 5;

    // 验证数组有序（二分的前提条件）
    for (int i = 1; i < n; i++) {
        assert(a[i] > a[i - 1]); // 如果数组无序，程序会立即终止并报错
    }

    int pos = binarySearch(a, n, 5);
    assert(pos >= 0 && pos < n); // 检查返回值在合法范围内
    assert(a[pos] == 5);         // 检查返回位置的值确实等于目标值
    printf("找到了，位置为 %d\n", pos);

    return 0;
}

assert 的使用注意

assert 在编译时加 -DNDEBUG 选项会被禁用，所以它只适合调试阶段。
不要在 assert 中写有副作用的表达式（如 assert(++x > 0)），否则禁用 assert 后行为会改变。
竞赛中建议始终保留 assert 检查输入数据的合法性，发现读入错误比调试算法错误容易得多。

方法四：打印中间状态的技巧¶

#include <cstdio>
#include <vector>
using namespace std;

// 打印 vector 的辅助函数
template<typename T>
void printVec(const char* name, const vector<T>& v) {
    fprintf(stderr, "%s[%zu] = {", name, v.size());
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) fprintf(stderr, ", ");
        fprintf(stderr, "%d", (int)v[i]);
    }
    fprintf(stderr, "}\n");
}

// 打印二维数组/矩阵的辅助函数
void printMatrix(const char* name, int a[][100], int n, int m) {
    fprintf(stderr, "%s (%dx%d):\n", name, n, m);
    for (int i = 0; i < n; i++) {
        fprintf(stderr, "  ");
        for (int j = 0; j < m; j++) {
            fprintf(stderr, "%4d", a[i][j]);
        }
        fprintf(stderr, "\n");
    }
}

16.2 时间复杂度分析与卡常技巧¶

16.2.1 各种操作的实际运行时间¶

下表基于常见的 1 秒时限，假设 CPU 约能执行 \(10^8\) 次基本操作（不同机器和编译器优化级别会有差异）：

操作类型	时间复杂度	\(n=10^5\) 时约耗时	\(n=10^6\) 时约耗时	备注
数组随机访问 `a[i]`	\(O(1)\)	极快	极快	缓存友好
哈希表 `unordered_map` 查找	\(O(1)\) 均摊	快	较快	最坏 \(O(n)\)
平衡树 `map` 查找	\(O(\log n)\)	较快	较慢	红黑树，常数较大
排序 `sort`	\(O(n \log n)\)	~0.015s	~0.15s	introsort（快排+堆排+插入排序混合）
遍历 `vector`	\(O(n)\)	~0.001s	~0.01s	缓存友好
`priority_queue` 单次操作	\(O(\log n)\)	较快	较快	二叉堆
并查集（路径压缩+按秩合并）	\(O(\alpha(n))\)	极快	极快	几乎 \(O(1)\)
DFS/BFS 遍历图	\(O(n + m)\)	取决于边数	取决于边数	邻接表
矩阵快速幂	\(O(k^3 \log n)\)	取决于 \(k\)	取决于 \(k\)	\(k\) 为矩阵维度

10^8 经验法则

在 1 秒时限内，一般可以执行约 \(10^8\) 次基本操作（整数加减乘、数组访问等）。除法、取模约为 2-3 倍时间。这个经验值在大多数 OJ 上是可靠的，但建议本地实测确认。

16.2.2 常见卡常方法¶

"卡常"是指通过优化常数因子，使程序在不改变时间复杂度的前提下运行更快。

方法一：位运算优化¶

// 取模优化：当 MOD 是 2 的幂时，可以用位运算替代取模
// 例如 MOD = 2^20 = 1048576
#define MOD_POW2 (1 << 20)
int fast_mod(int x) {
    return x & (MOD_POW2 - 1); // 等价于 x % MOD_POW2，但更快
}

// 乘以 2 的幂：用左移替代乘法
int a = 5;
int result = a << 3; // 等价于 a * 8

// 除以 2 的幂（向下取整）：用右移替代除法
int b = 17;
int quotient = b >> 2; // 等价于 b / 4 = 4

// 判断奇偶：用位运算替代取模
bool isOdd = (a & 1); // 等价于 a % 2 != 0

// 交换两个数（无需临时变量，但在实际中未必比 std::swap 快）
a ^= b; b ^= a; a ^= b;

方法二：register 关键字¶

// register 提示编译器将变量放在寄存器中
// 注意：C++17 起 register 已弃用，但竞赛中仍可使用
// 实际效果取决于编译器是否采纳提示
void sum_array(int a[], int n) {
    register int sum = 0; // 建议编译器将 sum 放在寄存器
    for (register int i = 0; i < n; i++) {
        sum += a[i];
    }
    printf("%d\n", sum);
}

现代编译器的优化能力

现代编译器（g++ 带 -O2 或 -O3）已经足够智能，会自动将频繁使用的变量放入寄存器。register 关键字的实际效果在很多时候可以忽略，但在极端卡常的题目中仍值得一试。

方法三：inline 关键字¶

// inline 建议编译器将函数内联展开，消除函数调用开销
// 适用于频繁调用的短函数
inline int gcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 注意：现代编译器在 -O2 下会自动内联短函数
// inline 作为建议而非强制，编译器可以忽略

方法四：循环展开¶

// 循环展开：减少循环判断和跳转的次数
// 原始版本
void sum_original(int a[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    printf("%d\n", sum);
}

// 展开 4 次的版本（n 需要是 4 的倍数，或者在末尾处理余数）
void sum_unrolled(int a[], int n) {
    int sum = 0;
    int i = 0;
    // 主循环：每次处理 4 个元素
    for (; i + 3 < n; i += 4) {
        sum += a[i] + a[i+1] + a[i+2] + a[i+3];
    }
    // 处理剩余元素
    for (; i < n; i++) {
        sum += a[i];
    }
    printf("%d\n", sum);
}

方法五：减少函数调用¶

// 将频繁调用的小函数用宏或内联代码替代

// 不推荐：每次调用 max 都有函数调用开销
int max_val(int a, int b) { return a > b ? a : b; }

// 推荐：使用宏（在编译时展开，无函数调用开销）
#define MAX(a, b) ((a) > (b) ? (a) : (b))
// 或直接使用标准库 std::max（编译器会自动内联）

// 实际竞赛中的建议：
// 1. 短函数加 inline
// 2. 用 std::max / std::min 而非手写宏
// 3. 将循环中的不变量提到循环外面

方法六：使用数组代替 map¶

#include <cstdio>
#include <map>
#include <unordered_map>
#include <cstring>
using namespace std;

int main() {
    // 方案1：当值域较小时，用数组替代 map（快数倍到数十倍）
    int cnt_array[100005];
    memset(cnt_array, 0, sizeof(cnt_array));
    // cnt_array[x]++ 是 O(1) 且常数极小

    // 方案2：unordered_map（哈希表）比 map 快 3-5 倍
    unordered_map<int, int> cnt_hash;
    cnt_hash[42]++; // O(1) 均摊

    // 方案3：map（红黑树）最慢，但支持有序遍历
    map<int, int> cnt_tree;
    cnt_tree[42]++; // O(log n)

    // 经验：数组 >> unordered_map >> map
    // 能用数组就不用 unordered_map，能用 unordered_map 就不用 map
    return 0;
}

卡常不是万能的

卡常只能优化常数因子，不能改变时间复杂度。如果算法本身 \(O(n^2)\) 而数据范围 \(n = 10^5\)，再怎么卡常也过不了。
先确保算法正确且复杂度合理，再考虑卡常。
-O2 编译选项比手动卡常重要得多，务必确保开启。

16.2.3 什么时候用 scanf/printf 而不是 cin/cout¶

// 关键语句：关闭 cin/cout 与 C 风格 IO 的同步
// 加了这句之后，cin/cout 的速度会显著提升，接近 scanf/printf
ios_base::sync_with_stdio(false);
cin.tie(nullptr); // 解除 cin 和 cout 的绑定，进一步提速

// 以下代码展示了开启和不开启同步的性能差异
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;

int main() {
    // 取消注释下面两行以开启快速 IO
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);

    int n = 1000000;
    int x;

    clock_t start = clock();
    for (int i = 0; i < n; i++) {
        // cin >> x;       // 未关闭同步：很慢（约 2-3 秒）
        scanf("%d", &x);   // scanf 始终较快（约 0.5 秒）
    }
    clock_t end = clock();
    cerr << "读入耗时: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;

    return 0;
}

场景	推荐方案	原因
输入量 \(\le 10^5\)	`cin/cout` 或 `scanf/printf` 均可	速度差异不明显
输入量 \(10^5 \sim 10^6\)	`cin` + `sync_with_stdio(false)`	方便且够快
输入量 \(\ge 10^6\)	`scanf/printf` 或快读	速度有明显优势
需要输出浮点数精度控制	`printf`	格式化更方便（如 `printf("%.10f", x)`）
需要读入字符串（含空格）	`fgets(buf, sizeof buf, stdin)` 或 `getline(cin, s)`	`cin >> s` 遇空格会停止；`gets` 已从 C++14 起移除，不要再用

最佳实践

每个竞赛程序的 main 函数开头都加上：

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

这样使用 cin/cout 也不会太慢。如果你习惯 scanf/printf，则不需要这行。

16.3 常见竞赛题型分类与解题思路¶

16.3.1 如何判断一道题用什么算法¶

面对一道新题，可以通过以下决策流程逐步缩小算法范围：

flowchart TD
    A[读题] --> B{问题要求什么?}
    B -->|求最值/最优解| C{能否用贪心?}
    B -->|求方案数/计数| D{数据范围?}
    B -->|判断是否存在/可行性| E{图论相关?}
    B -->|维护数据/查询| F{操作类型?}

    C -->|局部最优=全局最优| C1[贪心]
    C -->|需要记录子问题| C2[动态规划]
    C -->|搜索空间较小| C3[BFS/DFS/回溯]

    D -->|n ≤ 20| D1[状压DP / 搜索]
    D -->|n ≤ 1000| D2[O(n^2) DP]
    D -->|n ≤ 10^5| D3[组合数学 / O(n log n)]
    D -->|n ≤ 10^9| D4[数学公式 / 快速幂]

    E -->|求最短路| E1{边权?}
    E -->|求连通性| E2[并查集 / DFS]
    E -->|求拓扑序| E3[拓扑排序]
    E -->|求最小生成树| E4[Kruskal / Prim]

    E1 -->|边权相等| E1a[BFS]
    E1 -->|非负权| E1b[Dijkstra]
    E1 -->|有负权| E1c{是否有负环?}
    E1c -->|无负环| E1d[Bellman-Ford / SPFA]
    E1c -->|有负环| E1e[Floyd 判负环]

    F -->|单点修改+区间查询| F1[树状数组 / 线段树]
    F -->|区间修改+单点查询| F2[差分数组]
    F -->|区间修改+区间查询| F3[线段树 lazy标记]
    F -->|可持久化/历史版本| F4[主席树 / 可持久化线段树]
    F -->|字符串匹配| F5[KMP / Trie / AC自动机]

16.3.2 题型到算法的映射表¶

题型特征	可能的算法	数据范围暗示	典型题目关键词
最优化问题（最大/最小值）	DP、贪心、二分答案	\(n \le 1000\) 级别多为 DP	最大值、最小代价、最少操作
方案计数	DP、组合数学、容斥原理	看是否需要取模	方案数、排列、组合
连通性问题	并查集、DFS/BFS	\(n \le 10^5\)	连通、合并、关系
区间操作（修改+查询）	线段树、树状数组、分块	\(n \le 10^5\)，操作 \(m \le 10^5\)	区间和、区间最值、单点修改
区间覆盖/最值	ST 表、线段树	静态查询用 ST 表	区间最大/最小值
最短路	Dijkstra、BFS、Floyd、SPFA	稠密图用 Floyd，稀疏图用 Dijkstra	最短距离、最少花费
最小生成树	Kruskal、Prim	\(n \le 10^5\) 用 Kruskal	最小代价连通、铺设道路
拓扑排序	Kahn 算法、DFS	DAG 图	先后关系、依赖关系
字符串匹配	KMP、哈希、Trie、AC 自动机	串长 \(\le 10^6\)	匹配、出现次数
可行性/判定问题	二分搜索、搜索	答案具有单调性	是否可能、最大/最小的可行值
背包问题	01 背包、完全背包、多重背包	容量 \(W \le 10^4 \sim 10^5\)	选或不选、容量限制
序列相关（LCS/LIS）	DP、贪心+二分	\(n \le 10^5\) 用 \(O(n\log n)\)	子序列、最长、递增
数论（GCD/质数）	欧几里得、筛法、快速幂	\(n \le 10^7\) 用线性筛	整除、质因数、取模
博弈论	SG 函数、找规律	状态可分解	先手必胜、Nim 游戏
计算几何	叉积、凸包、扫描线	\(n \le 10^5\)	面积、距离、交点
图上路径问题（多源）	Floyd 算法	\(n \le 500\)	所有点对最短路

关于数据范围的经验判断

\(n \le 10\)：指数级算法可行（\(2^n\)、\(n!\)）
\(n \le 20 \sim 25\)：状压 DP、\(O(2^n \cdot n)\)
\(n \le 100\)：\(O(n^3)\)（Floyd 等）
\(n \le 500\)：\(O(n^3)\) 的 DP、\(O(n^2 \log n)\)
\(n \le 5000\)：\(O(n^2)\)
\(n \le 10^5\)：\(O(n \log n)\)
\(n \le 10^6\)：\(O(n)\) 或 \(O(n \log n)\)（较紧）
\(n \le 10^9\)：\(O(\sqrt{n})\) 或 \(O(\log n)\)
\(n \le 10^{18}\)：\(O(\log n)\)（快速幂、矩阵快速幂）

16.3.3 从读题到 AC 的完整流程¶

下面以一个具体例子说明完整的解题流程：

题目大意： 给定 \(n\) 个物品，每个物品有重量 \(w_i\) 和价值 \(v_i\)。有一个容量为 \(W\) 的背包，求能装的最大总价值。\((1 \le n \le 100, 1 \le W \le 10^5)\)

步骤一：读题与提取关键信息

关键信息：
- n 个物品，每个有重量和价值 → 经典背包问题
- 容量为 W 的背包 → 容量限制
- 求最大总价值 → 最优化问题
- 数据范围：n ≤ 100, W ≤ 10^5

步骤二：分析算法选择

- 最优化问题 → DP 或 贪心
- 每个物品只能选一次（隐含条件需确认）→ 01 背包
- n ≤ 100, W ≤ 10^5 → O(nW) = 10^7，可接受
- 结论：使用 01 背包 DP

步骤三：设计状态与转移方程

状态定义：dp[j] = 容量为 j 时的最大价值
转移方程：dp[j] = max(dp[j], dp[j - w[i]] + v[i])
遍历顺序：物品从前往后，容量从后往前（避免重复选同一个物品）

步骤四：编写代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 105;
const int MAXW = 100005;

int w[MAXN], v[MAXN];
int dp[MAXW]; // 滚动数组优化空间

int main() {
    int n, W;
    scanf("%d%d", &n, &W);

    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    // 01 背包核心代码
    for (int i = 0; i < n; i++) {
        // 从后往前遍历，确保每个物品只用一次
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    printf("%d\n", dp[W]);
    return 0;
}

步骤五：调试与验证

检查清单：
- [ ] 样例是否通过？
- [ ] 边界情况处理了吗？（n=1, W=0, 所有物品都装不下等）
- [ ] 数组大小够不够？（会不会越界？）
- [ ] 初始化正确吗？（dp 数组是否需要初始化为 0 或 -INF？）
- [ ] 数据类型是否足够？（结果会不会溢出 int？）
- [ ] 输出格式正确吗？（末尾换行、精度等）

调试检查清单（通用）

每次提交前都过一遍以下清单：

数组大小是否为题目最大范围 + 适当余量？
是否有多组测试数据需要处理（别忘了初始化）？
变量名是否写错（如 i 写成 j）？
循环边界是 < 还是 <=？
是否有未处理的特殊情况？
是否有整数溢出风险？

16.4 比赛策略¶

16.4.1 时间分配¶

Codeforces 赛制（2小时，通常 6-8 题）¶

阶段	时间	策略
通读题目	前 5-10 分钟	快速浏览所有题目，大致判断难度
签到题（A/B）	10-20 分钟	快速完成，确保不丢分
中等题（C/D）	30-60 分钟	主攻区域，仔细分析再下手
较难题（E/F）	剩余时间	尽力而为，不要在一棵树上吊死

Codeforces 的分数机制

Codeforces 的题目分值随时间递减（每分钟减少一定分数），因此： - 签到题要快速通过，抢时间分。 - 难题如果长时间没思路，不如先跳去做后面的题。 - WA (Wrong Answer) 也会扣分，提交前务必检查。

ICPC 赛制（5小时，通常 10-13 题，可带纸质资料）¶

阶段	时间	策略
通读题目	前 15-20 分钟	每道题都读一遍，标记难度和类型
签到题	30-60 分钟	2-3 人分工快速完成所有签到题
中等题	2-3 小时	主力解题，注意分工合作
冲刺阶段	最后 1 小时	查看罚时和排名，决定策略

ICPC 团队赛的关键

分工明确：一人读题、一人写代码、一人检查/调试，轮流切换。
使用气球颜色：观察哪些气球（AC 标志）出现得最多，说明哪些题比较容易。
罚时管理：罚时 = 所有 AC 题目的提交时间之和 + 每次错误提交罚 20 分钟。尽量一次 AC。

什么时候该放弃一道题¶

判断是否放弃的依据：
1. 已经想了 30 分钟以上还没有任何思路 → 先跳过，做其他题
2. 已经 WA 了 3 次以上且找不到 Bug → 换人检查或先搁置
3. 赛程过半时，果断评估：这道题还要花多久？值不值得？
4. 如果有两道题都没做出来，优先选更有把握的那道

16.4.2 先做哪道题¶

读题策略

先通读所有题：花 5-15 分钟快速浏览所有题目，标记：
明显的签到题（几乎能秒杀的）
自己擅长的题型（如你擅长 DP 就优先找 DP 题）
看不懂的题（暂时搁置）
从签到题开始：先稳住基本分数和心态。
根据自己的强项选题：同样是中等难度的题，选自己更熟悉的题型。

不同难度的题目识别¶

/*
 * 签到题的特征：
 * - 题目描述简短
 * - 数据范围很小（如 n ≤ 100）
 * - 没有复杂的约束条件
 * - 通常是模拟、简单数学、简单贪心
 *
 * 中等题的特征：
 * - 题目有一定思考量
 * - 可能需要某个经典算法
 * - 数据范围暗示了时间复杂度
 *
 * 难题的特征：
 * - 题目描述较长，条件多
 * - 需要组合多个知识点
 * - 或需要特殊的技巧/结论
 */

16.4.3 如何处理不会的题（部分分策略）¶

在 ICPC/OI 赛制中，通常有部分分（Partial Score）。即使不能完全解决一道题，拿到部分分也很有价值。

暴力拿部分分¶

/*
 * 部分分策略示例：
 * 题目要求：求 n 个数中所有子序列的最大权值和
 * 完整解法：O(n) 的 DP 解法
 * 部分分解法：O(2^n) 的枚举
 *
 * 当 n ≤ 20 时，暴力枚举所有子序列可以拿到小数据的分数
 */
#include <cstdio>
#include <algorithm>
using namespace std;

int a[25];
int n;

// 暴力枚举所有子序列
int brute_force() {
    int ans = -1e9;
    // 枚举 2^n 个子集
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                sum += a[i];
            }
        }
        ans = max(ans, sum);
    }
    return ans;
}

// 完整解法：最大子段和（Kadane 算法）
int full_solution() {
    int max_ending_here = a[0];
    int max_so_far = a[0];
    for (int i = 1; i < n; i++) {
        max_ending_here = max(a[i], max_ending_here + a[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // 小数据用暴力，大数据用正解
    if (n <= 20) {
        printf("%d\n", brute_force());
    } else {
        printf("%d\n", full_solution());
    }
    return 0;
}

特殊情况的处理¶

/*
 * 很多题目的特殊情况有简单的解法：
 *
 * 1. n = 1 时：直接输出答案，无需任何算法
 * 2. 所有元素相同时：答案往往很简单
 * 3. 树退化为链时：就是序列上的问题
 * 4. 图是一棵树时：不需要考虑环
 *
 * 即使拿不到满分，处理好特殊情况也能拿到 10-30 分
 */

输出格式分¶

别小看格式分

在 OI 赛制中，输出格式错误也会判为 WA。但有些比赛（如部分 IOI 风格赛制）会给"格式分"。 - 确保输出的空格、换行、精度完全符合要求。 - 不确定时，看样例输出的格式严格模仿。 - 末尾是否有多余空格或换行，往往会导致 WA。

16.5 交互题简介¶

16.5.1 什么是交互题¶

交互题（Interactive Problem）是一类特殊的题目：你的程序需要与评测系统（评测器/Judge）进行实时通信。不是一次性读入所有输入然后输出答案，而是通过"提问-回答"的交互过程来获取信息并得出结论。

交互题的核心区别

普通题：读入数据 → 计算 → 输出答案（一次性完成）
交互题：反复进行 "输出问题 → 刷新缓冲区 → 读入回答" 的过程，直到得出答案

16.5.2 交互题的输入输出方式¶

交互题与普通题的最大区别在于输出后需要 刷新缓冲区，否则评测器收不到你的输出。

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

// 方式一：使用 endl（自动刷新缓冲区，但稍慢）
void method1() {
    cout << "这是我的问题" << endl;  // endl = '\n' + flush
    int response;
    cin >> response;
}

// 方式二：手动 flush（推荐，更快）
void method2() {
    cout << "这是我的问题\n" << flush;  // 手动刷新
    int response;
    cin >> response;
}

// 方式三：使用 fflush(stdout)（C 风格）
void method3() {
    printf("这是我的问题\n");
    fflush(stdout);  // C 风格的刷新
    int response;
    scanf("%d", &response);
}

缓冲区刷新是必须的！

如果不刷新缓冲区，你的输出会留在内存中，评测器收不到，就会导致程序"挂起"（TLE 或 IDLE）。这是交互题最常见的错误。

16.5.3 常见交互题类型¶

类型一：二分交互¶

给你一个范围 \([1, n]\)，其中有一个隐藏的答案。你可以提问"是否 \(\le x\)？"，要求用尽量少的提问次数找到答案。

思路： 标准二分搜索，每次将范围缩小一半，\(O(\log n)\) 次提问即可。

类型二：猜数游戏¶

评测器心中想了一个数（或一个排列），你通过有限次数的提问来猜出它。常见的提问方式有： - 比较两个位置的大小关系 - 询问某个区间的性质（如中位数） - 询问某个子集的异或和

类型三：交互式构造¶

要求你构造某个满足条件的对象（如图、序列），评测器会告诉你当前构造是否满足约束。

类型四：树上交互¶

给定一棵树（但边被隐藏），通过查询节点间的关系（如两点距离、LCA）来推断树的结构。

16.5.4 完整示例：交互式二分查找¶

以下是一个完整的交互题示例，模拟了典型的二分交互题。

题目描述（模拟）： 评测器想了一个 \([1, 1000000]\) 之间的整数 \(x\)。你可以询问"是否 \(\le k\)？"，评测器会回答 YES 或 NO。请在不超过 20 次提问后找到 \(x\)。

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

/*
 * 交互式二分查找
 *
 * 交互协议：
 * - 我们输出一个整数 k，表示询问"答案是否 <= k？"
 * - 评测器回答 "YES" 或 "NO"
 * - 最后输出 "! x" 表示答案为 x
 *
 * 注意：这是模拟版本。在真实交互题中，评测器是外部程序。
 * 本地测试时，可以手动输入回答或写一个模拟的 judge。
 */

// 向评测器提问：答案是否 <= k？
bool ask(int k) {
    cout << k << endl; // 输出问题并刷新缓冲区
    // 在本地测试时，以下代码模拟评测器的回答
    // 在实际比赛中，评测器会自动回答
    string response;
    cin >> response;
    return response == "YES";
}

// 输出最终答案
void answer(int x) {
    cout << "! " << x << endl; // 输出答案并刷新缓冲区
}

int main() {
    int lo = 1, hi = 1000000;

    // 二分查找：每次将范围缩小一半
    // 最多需要 ceil(log2(1000000)) ≈ 20 次提问
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2; // 防止溢出
        if (ask(mid)) {
            // 答案 <= mid，缩小右边界
            hi = mid;
        } else {
            // 答案 > mid，缩小左边界
            lo = mid + 1;
        }
    }

    // lo == hi，找到了答案
    answer(lo);

    return 0;
}

16.5.5 更复杂的交互题示例：交互式排序¶

题目描述（模拟）： 评测器有一个隐藏的长度为 \(n\) 的排列 \(p\)。你可以比较任意两个位置的大小关系（输出 ? i j，评测器回答 < 或 >），要求用不超过 \(n \times \lceil \log_2 n \rceil\) 次比较将排列排序。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int pos[MAXN]; // pos[i] = 值 i 当前的位置

// 向评测器提问：位置 i 的值 是否 < 位置 j 的值？
bool isLess(int i, int j) {
    cout << "? " << i << " " << j << endl;
    char response;
    cin >> response;
    return response == '<';
}

int main() {
    int n;
    cin >> n;

    // 初始化：假设排列是 1 到 n，pos[i] = i
    for (int i = 1; i <= n; i++) {
        pos[i] = i;
    }

    // 使用插入排序（比较次数约为 n^2，不满足要求但易于理解）
    // 实际比赛中应该用 merge sort 将比较次数控制在 n*log(n)
    int arr[MAXN];
    for (int i = 1; i <= n; i++) arr[i] = i;

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

    // 输出答案
    cout << "!";
    for (int i = 1; i <= n; i++) {
        cout << " " << arr[i];
    }
    cout << endl;

    return 0;
}

16.5.6 交互题的本地测试技巧¶

在本地调试交互题比普通题困难，因为需要模拟评测器的行为。以下是常用方法：

/*
 * 方法一：使用条件编译切换交互模式
 */
#ifdef LOCAL
    // 本地调试：手动输入或模拟 judge
    int hidden_answer = 42; // 预设答案
    bool ask(int k) {
        cerr << "询问: <= " << k << " ? ";
        bool result = (hidden_answer <= k);
        cerr << (result ? "YES" : "NO") << endl;
        return result;
    }
#else
    // 正式提交：与评测器交互
    bool ask(int k) {
        cout << k << endl;
        cout.flush();
        string s;
        cin >> s;
        return s == "YES";
    }
#endif

/*
 * 方法二：编写交互脚本（推荐用于复杂交互题）
 *
 * 创建两个文件：
 * - solution.cpp: 你的解法（从 stdin 读、向 stdout 写）
 * - judge.cpp: 模拟评测器（从 solution 的 stdout 读、向 solution 的 stdin 写）
 *
 * 使用管道连接两个程序：
 * mkfifo pipe1 pipe2
 * ./solution < pipe1 > pipe2 &
 * ./judge < pipe2 > pipe1
 *
 * 或者使用 Python 脚本做中间人（更灵活）
 */

16.5.7 交互题注意事项¶

交互题的常见坑

忘记刷新缓冲区：这是最常见的错误。用 endl 或 cout.flush() 或 fflush(stdout)。
提问次数限制：注意题目给出的提问次数上限，超出会直接判 WA/TLE。
不要在 cerr 中输出调试信息：在交互题中，cerr 的输出会被评测器读到（如果你用管道测试的话），正式提交时也可能有影响。本地调试用条件编译包裹。
注意读入格式：交互题的回答格式因题而异，可能是字符串（YES/NO）、整数、或单个字符（</>）。务必仔细读题。
endl vs "\n"：endl 会自动刷新缓冲区但效率稍低；"\n" + flush 效率更高。如果题目对时间要求严格，优先用后者。

// 推荐的交互输出方式（效率与安全兼顾）
// 方法 A：endl（最安全，容易记住）
cout << "你的输出" << endl;

// 方法 B：手动 flush（稍快）
cout << "你的输出\n" << flush;

// 方法 C：C 风格（最快）
printf("你的输出\n");
fflush(stdout);

// 千万不要这样写（会挂起！）：
cout << "你的输出\n"; // 没有 flush，评测器收不到

交互题的解题思路

明确交互协议：清楚你输出什么、评测器回答什么、格式是什么。
计算提问次数：题目限制多少次提问？你的算法需要多少次？是否足够？
信息论角度思考：每次提问获得 1 bit 信息（是/否），\(k\) 次提问最多区分 \(2^k\) 种情况。
先想暴力再优化：如果暴力枚举会超出提问限制，考虑二分、分治等减少提问次数的方法。

本章小结¶

主题	核心要点
代码模板	准备好快读、常用宏、对拍脚本，节省比赛时间
时间复杂度与卡常	\(10^8\) 法则，先保证算法正确再卡常，善用 `-O2` 编译
题型分类	通过数据范围和问题类型快速定位算法，建立自己的算法库
比赛策略	先通读、先签到、合理分工、果断放弃、部分分要拿满
交互题	记得 flush！注意提问次数限制，从信息论角度设计策略

给新手的建议

竞赛技巧需要在实践中不断积累。建议每次比赛后回顾： 1. 哪些题本该做出来但没做出来？是算法没学好还是代码实现有问题？ 2. 时间分配是否合理？有没有在某道题上浪费太多时间？ 3. 有没有因为低级错误（数组越界、变量名写错、忘记取模等）而 WA？ 4. 把每次比赛当作学习机会，持续完善自己的模板库和解题套路。

第十六章 竞赛技巧¶