19 常用竞赛技巧与时间复杂度分析

GESP 3 级起CSP-J / NOIP 必备CSP-S

级别标注：GESP 3 级起引入复杂度概念（考级要求）/ CSP-J、NOIP 必备（竞赛进阶：读入优化、常数优化、复杂度估算选算法）。

一、时间复杂度

时间复杂度 = 算法执行步数随数据规模 n 的增长趋势，用大 O 表示。它描述量级，不关心常数。

常见量级（从小到大）：

复杂度	含义	典型算法	可承受规模（约 1 秒）
O(1)	常数	数组访问	任意
O(log n)	对数	二分查找	巨大
O(n)	线性	一次遍历	10^7 ~ 10^8
O(n log n)	线性对数	sort、归并、Dijkstra 堆	10^6 ~ 10^7
O(n²)	平方	冒泡、01背包朴素、Floyd	10^3 ~ 10^4
O(n³)	立方	Floyd	500 左右
O(2^n)	指数	枚举子集	n ≤ 20
O(n!)	阶乘	全排列暴力	n ≤ 10

估算口诀：看到 n ≤ 10^5 想 O(n log n) 或 O(n)；n ≤ 5000 可容忍 O(n²)；n ≤ 20 才考虑指数枚举。

形象理解时间复杂度像给算法称体重：n 变成 2 倍，O(n) 算法时间变 2 倍，O(n²) 变 4 倍，O(2^n) 直接爆炸。它只看“量级”，2n 和 100n 都记作 O(n)。

考级视角GESP 笔试必考“读程序判断复杂度”：数循环嵌套层数是捷径——单层 O(n)、双层 O(n²)、三层 O(n³)；但要注意循环内每次 j *= 2 之类是 O(log n)。

二、空间复杂度

空间 = 变量 + 数组 + 递归栈。常用估算：1 int ≈ 4 字节，long long 8 字节；内存限制 256MB 时 long long 数组最多约 3×10^7 个。

例子：int a[100000][100000]（10^10 个 int ≈ 40GB）直接爆内存，必须换数据结构或降维。

三、读入优化（竞赛提速关键）

cin/cout 默认与 C 的标准 IO 同步，很慢。竞赛常用做法：

3.1 关闭同步 + 绑定

C++ 实例

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);   // 关闭 cin/cout 与 C stdio 的同步（提速关键）
    cin.tie(nullptr);              // 取消 cin 与 cout 的绑定（避免每次输出刷缓冲）
    int n; cin >> n;
    // 之后 cin/cout 会快很多（大输入时差距明显）
    return 0;
}

3.2 快读（手写 getchar 读整数）

C++ 实例

#include <cstdio>
// 快读模板：用 getchar 逐字符读入，比 cin 快（大输入量必备）
inline int read() {
    int x = 0, f = 1; char c = getchar();   // f 记录负号
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }  // 跳过非数字、识别负号
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }  // 逐位累加
    return x * f;
}

3.3 输出优化

C++ 实例

#include <iostream>
using namespace std;
// 用 printf 或 putchar 快写；最少要避免频繁 endl
int main() {
    // cout << x << '\n';  比 << endl 快（endl 会刷新缓冲区，频繁刷新拖慢速度）
    return 0;
}

形象理解cin 慢是因为默认和 C 的 stdio 同步排队（两边顺序要一致），关掉同步后它就不排队了，速度接近 scanf。手写快读则像自己手动捡货，比叫快递员（标准库）更快。

易错点快读必须处理负号和读到 EOF：while (c < '0' || c > '9') 里要 if (c == '-') f = -1;。另外 endl 会刷新缓冲区，循环输出里用

'
'

能快很多。

四、常数优化与代码习惯清单

循环展开 / 局部变量：把循环变量写成局部 int i, j，避免每次 int 声明。
提前 return：分支已定立即返回，减少无谓计算。
把多维数组压平为 1 维（a[x*n+y]）可省 cache 压力。
全局数组优于局部大数组：避免栈溢出（栈通常只有几 MB）。
少用递归改循环：递归调用有函数调用开销，大数据谨慎。
优先 '\n' 而非 endl。
能预分配就预分配：vector 用 reserve 减少扩容拷贝。
条件判断顺序：把低概率/代价高的判断放后面。

五、从复杂度倒推算法（读题方法论）

解题第一步看数据范围，倒推算法：

示例

n ≤ 10^5, 排序类 => 想到 sort / 归并 / 优先队列
n ≤ 10^5, 最短路 => Dijkstra 堆优化
n ≤ 10^3 ~ 10^4 => O(n²) DP / Floyd 也勉强
n ≤ 20 ~ 25   => 状态压缩 / 暴力枚举
n ≤ 10       => 全排列暴力

考级视角这是竞赛最实用的一步：先看 n 的范围再决定算法。n ≤ 10^5 想 O(n log n)；n ≤ 5000 可 O(n²)；n ≤ 20 才上状压/枚举。选错复杂度 = 提交必 TLE。

易错点别只看最大 n，还要看总输入规模（如多组数据 T×n）和常数因子（如大常数 STL 嵌套）。估算 1 秒 ≈ 10^8 次简单运算，留 3~5 倍余量更稳。

六、常见竞赛技巧汇总

读题三遍：确认输入输出格式、数据范围、取模要求。
样例一对一：先通过样例再提交。
对拍：写暴力程序与优化程序随机数据对比（新手校验）。
打表找规律：小数据暴力输出观察模式。
二分答案是万能钥匙：很多"最大化最小值/最小化最大值"题可以二分判定。
可行性→最优性：先判断"有没有解"，再求最优。
离线处理：排序询问、莫队等（NOIP 进阶）。
双指针 / 前缀和 / 差分：预处理加速区间问题（CSP-J 常考）：

C++ 实例

// 前缀和：O(1) 求子数组和
// pre[i] = pre[i-1] + a[i]; 区间 [l,r] 和 = pre[r] - pre[l-1]

// 差分：O(1) 区间加，最后前缀和还原
// d[l] += v; d[r+1] -= v;
#include <iostream>
using namespace std;
const int N = 100005;
int diff[N];                    // 差分数组
int main() {
    int n, m; cin >> n >> m;      // n 个位置，m 次区间加
    while (m--) {
        int l, r, v; cin >> l >> r >> v;
        diff[l] += v;             // 区间起点 +v
        diff[r + 1] -= v;         // 区间终点后一位 -v（抵消）
    }
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i - 1];   // 前缀和还原出每个位置的真实值
        cout << diff[i] << " ";
    }
    cout << endl;
    return 0;
}

形象理解前缀和像超市购物小票累计金额：pre[i] 是前 i 项总和，问区间 [l,r] 的和直接 pre[r] - pre[l-1]，一次算好、随时取用。差分像给区间统一盖章：只在两端做记号，最后统一还原。

易错点差分最容易错：区间 [l,r] 加 v 要写 d[l] += v; d[r+1] -= v;，下标从 1 开始的话数组要开 n+2，且最后用前缀和还原时才看到效果。

七、易错点 / 常见坑点

⚠️ 忘记关同步导致大数据 TLE（cin 默认慢）。
⚠️ endl 频繁使用拖慢输出。
⚠️ 快读实现边界不严谨（读到 EOF、负号处理）。
⚠️ 递归爆栈：预计递归很深时改循环/显式栈或加大栈空间。
⚠️ 复杂度估算错误导致提交 TLE；先看 n 再选算法。
⚠️ 数组大小开错（下标从 1 开始要多开一个）。
⚠️ 全局数组未初始化读入脏数据（int a[N] 全局自动为 0，但部分情况要主动 memset(a, 0, sizeof a)）。

八、考级要求 vs 竞赛进阶

考级要求（GESP 4 级起）：理解大 O 概念、能判断简单循环的复杂度（如 O(n²)）、能根据数据范围选择合适做法；笔试常考"该程序时间复杂度是？"。
竞赛进阶（CSP-J/NOIP）：读入优化是默认要求；掌握 O(n log n) 常规上限、常数级优化、从数据范围反推算法；进阶还有均摊分析、离线、分块等。

九、课内练习建议

计算多个例子的复杂度（嵌套循环、递归、二分）。
给定数据范围（n=10^5 + O(n²)），实测会 TLE，理解"先看 n 再写代码"。
对一个大输入规模的题，分别用"关同步 cin"和"快读"测时间差异。
前缀和 + 差分做 2 个题目练熟。
写一个对拍脚本（暴力 vs 优化）。