ACM 竞赛编程指南

竞赛编程和面试编程是两种不同的技能。这里帮你把竞赛经验转化为面试优势。

输入输出模板

ACM 模式和 LeetCode 模式最大的区别：需要自己处理输入输出。

C++ 多测模板

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        // 处理单个测试用例
    }
    return 0;
}

关键点：

ios::sync_with_stdio(false) 关闭同步，提速 5-10 倍
cin.tie(nullptr) 解除 cin 和 cout 的绑定
多测时注意清空全局变量

Python 多测模板

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    # 处理单个测试用例

注意：Python 的 input() 太慢，必须用 sys.stdin.readline。

Java 多测模板

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            // 处理后用 sb.append() 收集输出
        }
        System.out.print(sb);
    }
}

关键：用 StringBuilder 收集输出，最后一次性打印。

高频坑点

数据范围与类型

数据范围	正确类型	常见错误
≤ 10^9	`int`	无
≤ 10^18	`long long`	用了 `int`
涉及乘法	检查中间结果	`int a * int b` 溢出

典型错误：

int a = 1e9, b = 1e9;
long long c = a * b;  // 错！a * b 已经溢出

long long c = 1LL * a * b;  // 对！先转 long long

图论算法选择

场景	正确算法	常见错误
非负权最短路	Dijkstra	无
有负权边	Bellman-Ford / SPFA	用了 Dijkstra
所有节点对	Floyd	单源算法跑 n 次
最小生成树	Kruskal / Prim	用了最短路算法

典型错误：在负权图上用 Dijkstra 会得到错误结果。

多测清空

每组测试前必须清空全局变量：

int cnt[100005];
vector<int> adj[100005];

void solve() {
    // 必须清空！
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= n; i++) adj[i].clear();
    
    // 然后处理当前测试用例
}

堆优化 Dijkstra 的坑

// 错误：没过滤过期状态
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    for (auto [v, w] : adj[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

// 正确：过滤过期状态
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;  // 过期了，跳过
    for (auto [v, w] : adj[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

竞赛常用技巧

快速读入（数据量 10^6+）

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

常用 STL

容器/函数	用途	复杂度
`priority_queue`	堆、Dijkstra	O(log n)
`set` / `map`	去重、查找	O(log n)
`unordered_set`	哈希去重	O(1) 平均
`lower_bound`	二分查找	O(log n)
`__builtin_popcount`	统计 1 的个数	O(1)

竞赛 → 面试转化

竞赛经验和面试要求不同：

方面	竞赛	面试
代码风格	越短越好	可读性优先
变量命名	单字母	有意义的名字
注释	几乎没有	关键步骤要注释
时间限制	1-2 秒	无严格限制
沟通	不需要	边写边说思路

面试代码风格示例

// 竞赛风格（面试不要这样）
int f(vector<int>& a) {
    int s = 0;
    for (int x : a) s += x;
    return s;
}

// 面试风格
int calculateSum(const vector<int>& numbers) {
    int sum = 0;
    for (int num : numbers) {
        sum += num;
    }
    return sum;
}

登录解锁更多

完整模板库（10+ 经典算法模板）
历年真题解析（Codeforces / AtCoder）
竞赛视频讲解
面试模拟训练

题型	核心算法	典型题目
背包问题	DP 状态设计	0/1 背包、完全背包
最短路	Dijkstra / SPFA	单源、多源
线段树	区间查询	区间和、区间最值
并查集	路径压缩	连通性、最小生成树
字符串	KMP / 哈希	模式匹配、回文