Online Judge（OJ）是为程序设计竞赛而生的自动判题系统：提交源代码（C/C++/Java/Python 等）， 系统编译执行，用出题人预设的测试数据判断正确性，同时有严格的时间与内存限制。

一道 OJ 题目的结构

评测结果的 7 种情况（必背）

Codeforces（CF）生态速览

• Pretest → System Test：赛中只过部分测试点（Pretest Passed），赛后统一全量测评，没过就是 FST
• Hack 机制：Lock 自己的代码后可看同 Room 选手代码，构造数据卡掉对方：成功 +100，失败 −50
• GYM：还原真实 ACM-ICPC 规则的训练场，可组队虚拟参赛（Virtual Participation）
• Problemset：按标签（dp / graphs / dsu…）和难度筛选题目，适合专题训练

竞赛主流语言是 C++。先掌握语法与 STL，再建立「先估复杂度、再写代码」的习惯——这是所有算法的地基。

竞赛通用模板（背下来）

C++#include <bits/stdc++.h>     // 万能头（绝大多数 OJ 支持）
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // 关闭同步，cin/cout 提速
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    cout << *max_element(a.begin(), a.end()) << "\n";
    return 0;
}

STL 必会清单

时间复杂度速查（1 秒 ≈ 10⁸ 次运算）

部分排序算法复杂度（经典表）

亲手试一试 · 复杂度体检器

学习算法是一个循序渐进的过程。不要指望一口气啃完《算法导论》再做题——看书与刷题应当是螺旋式推进的。 下面是为零基础新手设计的四阶段路线，每阶段都有明确目标。

螺旋式学习法（看书 ↔ 刷题）

一周计划示例（参考小明的故事）

• 周一 ～ 周五：每天固定时间做 1 道题（工作日做题）
• 周六 ～ 周日：看《算法竞赛入门经典》等书，梳理本周知识点
• 组队后：每周一场组队训练（区域赛真题虚拟参赛）+ 赛后讲题补题
• 执行策略：队友之间互相监督打卡——「你今天做题了吗？没有？还不赶紧去做！」

模拟题是按照题目要求操作即可得到结果的一类题目，注重考查代码实现能力、细节和特殊情况处理。 区域赛第一题（签水题）几乎都是模拟。

实战示范：股票交易（入门经典题）

三种解法的演进（思考过程比答案更重要）

C++int main() {
    int n;
    while (~scanf("%d", &n)) {          /* 多组数据，EOF 结尾 */
        int res, ans = 0, x;
        scanf("%d", &x);  res = x;       /* res 记录前缀最小值 */
        for (int i = 2; i <= n; i++) {
            scanf("%d", &x);
            if (ans < x - res) ans = x - res;  /* 更新最大收益 */
            if (x < res) res = x;              /* 更新最小值   */
        }
        if (ans == 0) printf("No solution\n");
        else printf("%d\n", ans);
    }
    return 0;
}

经典陷阱：数据溢出（2017 沈阳站 I 题 Little Boxes）

C++/* a,b,c,d ≤ 2^62，四数之和最大可达 2^64，unsigned long long 也装不下 */
if (a == (1ULL << 62) && b == (1ULL << 62) &&
    c == (1ULL << 62) && d == (1ULL << 62))
    printf("18446744073709551616\n");   /* 特判输出 2^64 的真实值 */
else
    printf("%llu\n", a + b + c + d);

搜索用于枚举所有情况或遍历图中每个点，适用于数据范围较小的场景。核心两板斧： 深度优先搜索（DFS，递归实现）与广度优先搜索（BFS，借助队列，求最少步数）。

DFS / BFS 对比与模板

C++/* DFS：递归遍历 */
void dfs(int u) {
    vis[u] = true;
    for (int v : g[u]) if (!vis[v]) dfs(v);
}

/* BFS：队列 + 最少步数 */
queue<int> q;  q.push(s);  vis[s] = true;
while (!q.empty()) {
    int u = q.front();  q.pop();
    for (int v : g[u]) if (!vis[v]) {
        vis[v] = true;  step[v] = step[u] + 1;  q.push(v);
    }
}

剪枝：搜索不超时的关键

• 可行性剪枝：到达某状态时，无论后面怎么做都达不到题目条件，立即回溯
• 最优性剪枝：若当前可能的最高得分都达不到已有最优解，直接停止搜索
• 状态保存与恢复：回溯前先备份地图/状态，递归返回后恢复——小心全局变量被污染

动态规划（DP）是一种决策过程：把多阶段问题拆成很多单阶段，利用阶段之间的关系逐个求解。 重点在于找到状态转移方程——可能从前向后、区间从小到大、沿轮廓线、或跟数位相关，变化多端。

经典模型清单（按序攻克）

区间 DP 示例：石子合并（朴素版）

C++/* dp[i][j] = 合并区间 [i, j] 的最小代价；大区间由小区间推出 */
for (int len = 2; len <= n; len++)
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;
        for (int k = i; k < j; k++)
            dp[i][j] = min(dp[i][j],
                dp[i][k] + dp[k + 1][j] + sum(i, j));
    }

真题状态设计对照

当暴力求解复杂度偏高时，可根据问题中的限定（如区间、前缀、最大异或）使用相应数据结构维护相应的值，达到优化时间复杂度的目的。

常用数据结构速查

树状数组模板（lowbit 是灵魂）

C++int lowbit(int x) { return x & (-x); }

void update(int x, int d) {
    while (x <= n) { BIT[x] += d;  x += lowbit(x); }
}
int query(int x) {
    int ret = 0;
    while (x) { ret += BIT[x];  x -= lowbit(x); }
    return ret;
}
/* 注意：树状数组下标从 1 开始，不能出现 0，否则 lowbit 会出问题 */

01 字典树求最大异或（经典应用）

C++/* 把每个数按二进制从高位到低位插入字典树；
   查询与 x 异或最大的值：每一位尽量走【相反】的子节点，
   两个数该位不同，异或结果才为 1 */
int query(int x) {
    int now = 0, t, ret = 0;
    for (int i = 30; i >= 0; i--) {
        t = (x >> i) & 1;
        if (nxt[now][t^1] && cnt[nxt[now][t^1]]) {
            ret |= (1 << i);          /* 这一位异或结果为 1 */
            now = nxt[now][t^1];
        }
        else now = nxt[now][t];
    }
    return ret;
}
/* 需要支持删除时：每个节点记录经过次数 cnt，
   插入 +1、删除 −1，cnt 为 0 的节点视作不存在 */

图论内容很多：最短路、生成树、匹配与网络流、拓扑结构、连通性、强连通分量，甚至还有给条件构造图的构造题。

最短路：堆优化 Dijkstra 模板

C++typedef pair<long long, int> pli;
priority_queue<pli, vector<pli>, greater<pli>> pq;   /* 小根堆 */

void dijkstra(int s) {
    fill(d + 1, d + n + 1, INF);
    d[s] = 0;  pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;  pq.pop();
        for (auto [v, w] : g[u])
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
    }
}
/* 无负权边用 Dijkstra；有负权用 SPFA；点少可用 Floyd */

建图技巧：有时候建出来就会做了

• 虚点建图（Meeting 类问题）：集合内两两连边边太多——把每个集合作一个新点，集合点向成员连权值 t 的有向边，成员向集合点连权值 0 的边，之后各跑一遍最短路即可
• 拆点（Kejin Game 类问题）：把每个点 i 拆成 i 和 i′ 建源汇，原图问题转化为最小割，直接用最大流求解
• 拓扑排序：Kahn 算法判环（出队数 < n 则有环），也可用于 DAG 上的 DP 与依赖调度
• 构造题（Graph Reconstruction 类问题）：由度数序列构图用 Havel–Hakimi 定理——所有点度数从大到小排序，每次考虑一个点向之后的点连边直至满足度数，再重新排序；度数连不完或出现负数则不可构图

运用数论知识和计算机快速计算的能力，可以解决许多问题。gcd / lcm、快速幂、筛法、容斥是四大件。

基础模板三连

C++/* 最大公约数（辗转相除） */
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
/* lcm(a,b) = a / gcd(a,b) * b —— 注意先除后乘防溢出 */

/* 快速幂：O(log b) */
long long qpow(long long a, long long b, long long mod) {
    long long ret = 1;  a %= mod;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

/* 埃氏筛打素数表 */
for (int i = 2; i <= 100000; i++) isprime[i] = true;
for (int i = 2; i <= 100000; i++)
    if (isprime[i])
        for (long long j = 2; i * j <= 100000; j++)
            isprime[i * j] = false;

容斥原理：正着不好求就求反面

求 1～n 中与 n 互质的数的四次方之和这类问题，正着求不好求，改为对 n 分解质因数后枚举质因数集合使用容斥：

C++/* 前提：fac[] 已存入 n 的所有不同质因子 */
for (long long s = 1; s < (1LL << cnt); s++) {
    long long now = 1;  int bits = 0;
    for (long long j = 0; j < cnt; j++)
        if (s >> j & 1) { bits++;  now *= fac[j]; }
    /* now 的倍数(≤n)有 n/now 个，四次方和代入公式 */
    /* 四次方和公式：Σk⁴ = n(n+1)(2n+1)(3n²+3n−1)/30 */
    /* 奇数个质因子做加，偶数个做减；除以 30 用费马小定理求逆元 */
    temp = qpow(now, 4) * (n / now) % mod * (n / now + 1) % mod
         * (2 * n / now + 1) % mod * ((3 * n / now * n / now
         + 3 * n / now + mod - 1) % mod) % mod
         * qpow(30, mod - 2) % mod;     /* qpow(30, mod-2) 即 30 的逆元 */
    if (bits & 1) ans = (ans + temp) % mod;
    else          ans = (ans + mod - temp) % mod;
}
/* 最后：用总和减去不互质的部分，得到互质部分的四次方和 */

数学推导示例：A Simple Math Problem（2016 大连站 D）

源自北航 ACM 集训队学长的实战经验：入门、刷题、团队三个维度的方法论。

入门：刷题 vs 看书

「只看书」容易望而生畏——《算法导论》全书 745 页，想读完整本再去「捕鱼」，无异于读完字典再去看书； 「只刷题」又会留下知识漏洞。正确姿势是螺旋式：看书时配合刷题巩固知识点， 刷题时遇到没学过的算法主动去学，慢慢积累，会有十分可观的收获。

刷题：数量 vs 质量

训练：团队 vs 个人

• 团队的好处：互相监督、互相鼓励、分工学习不同专题，减轻学习负担
• 但团队配合建立在个人实力之上——努力提高个人实力才是硬道理
• 三人一台电脑的基本分工：①各自为政式（谁擅长谁上）；②指手画脚式（一人敲码、两人观察提议）——最好的策略是两者结合
• 经典协作流程：A 想思路 → 三人讨论细节 → B 操刀写码、C 在旁 debug，A 去看下一题
• 注意避免「两个人同时做了同一道题」的低效情况——开赛前明确分工！

赛场心态（来自学长们的血泪）

工欲善其事，必先利其器。训练平台与经典书籍是 ACMer 的两件核心装备——其中下面三个网站，建议立刻收藏，几乎覆盖从入门到区域赛的全部资源。

三大必收藏学习网站（新手首选）

其他优质资源（进阶补充）

• AtCoder（atcoder.jp）——日本平台，ABC 每周一场，题目梯度极适合新手
• 牛客（nowcoder.com）——国内比赛 + 企业笔试题库，求职向友好
• Virtual Judge（vjudge.net）——聚合全球各 OJ 题目，方便组队刷题榜
• LeetCode——自带详细官方题解，按 Easy/Medium/Hard 标注，找工作向

三本经典书（怎么读最有效）

广义 ACM：值得一并参加的比赛

• CCPC 中国大学生程序设计竞赛——国内另一大赛事体系，赛程与 ICPC 互补
• 蓝桥杯（C/C++、Java 组）——个人赛，入门友好，省赛国赛两级
• 百度之星、编程之美、Topcoder——大厂 / 平台举办，练手 + 简历加分

了解竞赛之后，你还需要权衡参与它能带来什么、会让你失去什么，再根据自己的目标做出选择。

利 vs 弊（正反方观点提炼）

五类人群，五条建议

Q & A 精选

收录 2016–2019 年亚洲区域赛真题（公开题解整理）、2020–2024 年考生回忆版改编题、 2025 年官方样题风格题，以及依据近年赛制编写的 2026 年模拟预测题。 回忆版与改编题可能与原题表述略有出入。选择题点击选项立即判分；思路题点击「查看解析」展开——建议先自己想 10 分钟再看答案。

C++for (int s = mask; s; s = (s - 1) & mask) {
    /* s 依次取 mask 的每个非空子集，从大到小 */
}
/* 若还需包含空集，循环结束后单独处理 s = 0 */