常见解题模板

引言

在ACM竞赛中，掌握一些常用的解题模板可以大大提高编程效率和准确性。本文整理了竞赛中最常用的代码模板，涵盖了输入输出、基础算法、数据结构和特定问题类型等方面。这些模板可以作为你编写代码的起点，帮助你快速构建解决方案。

基础输入输出模板

标准输入输出加速

// 关闭同步流，加速cin/cout
ios::sync_with_stdio(false);
cin.tie(nullptr);

// 输入直到EOF
while (cin >> n) {
    // 处理输入
}

// 输入指定数量的测试用例
int T;
cin >> T;
while (T--) {
    // 处理每个测试用例
}

// 输入不定量的数据直到特定条件
while (cin >> n && n != 0) {
    // 处理输入
}

快速读写（处理大量数据）

// 快速读取整数
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;
}

// 快速输出整数
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

数据结构模板

并查集

// 并查集基本模板
const int MAXN = 1e5 + 5;
int parent[MAXN];
int rank_[MAXN];  // 秩优化

// 初始化
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank_[i] = 1;
    }
}

// 查找根节点（路径压缩）
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

// 合并集合（按秩合并）
void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank_[rootX] < rank_[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank_[rootX] == rank_[rootY]) {
                rank_[rootX]++;
            }
        }
    }
}

线段树（区间查询与修改）

// 线段树基本模板
const int MAXN = 1e5 + 5;
int arr[MAXN];  // 原始数组
int tree[MAXN * 4];  // 线段树数组，大小通常为原数组的4倍

// 构建线段树
void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    build(leftNode, start, mid);
    build(rightNode, mid + 1, end);

    tree[node] = tree[leftNode] + tree[rightNode];  // 根据需要修改操作（如求和、求最大等）
}

// 区间查询
int query(int node, int start, int end, int l, int r) {
    // 查询区间[l, r]
    if (r < start || l > end) {
        return 0;  // 查询区间与当前节点区间无交集
    }
    if (l <= start && end <= r) {
        return tree[node];  // 查询区间包含当前节点区间
    }

    int mid = (start + end) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    int leftSum = query(leftNode, start, mid, l, r);
    int rightSum = query(rightNode, mid + 1, end, l, r);

    return leftSum + rightSum;  // 根据需要修改操作
}

// 单点更新
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        arr[idx] = val;
        tree[node] = val;
        return;
    }

    int mid = (start + end) / 2;
    int leftNode = 2 * node;
    int rightNode = 2 * node + 1;

    if (idx <= mid) {
        update(leftNode, start, mid, idx, val);
    } else {
        update(rightNode, mid + 1, end, idx, val);
    }

    tree[node] = tree[leftNode] + tree[rightNode];  // 根据需要修改操作
}

树状数组（区间查询与单点修改）

// 树状数组基本模板
const int MAXN = 1e5 + 5;
int bit[MAXN];

// 获取最低位的1
int lowbit(int x) {
    return x & (-x);
}

// 单点更新
void update(int idx, int val, int n) {
    while (idx <= n) {
        bit[idx] += val;
        idx += lowbit(idx);
    }
}

// 前缀和查询
int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += bit[idx];
        idx -= lowbit(idx);
    }
    return sum;
}

// 区间查询[l,r]
int rangeQuery(int l, int r) {
    return query(r) - query(l - 1);
}

图论算法模板

深度优先搜索 (DFS)

// DFS模板
const int MAXN = 1e3 + 5;
vector<int> graph[MAXN];  // 邻接表表示图
bool visited[MAXN];  // 访问标记

void dfs(int u) {
    visited[u] = true;
    // 处理节点u

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }

    // 如果需要，在这里处理回溯操作
}

广度优先搜索 (BFS)

// BFS模板
const int MAXN = 1e3 + 5;
vector<int> graph[MAXN];  // 邻接表表示图
bool visited[MAXN];  // 访问标记
int dist[MAXN];  // 距离数组，用于最短路等问题

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 处理节点u

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;  // 更新距离
                q.push(v);
            }
        }
    }
}

Dijkstra算法（单源最短路）

// Dijkstra算法（堆优化）
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, cost;
    Edge(int t, int c) : to(t), cost(c) {}
};

vector<Edge> graph[MAXN];  // 邻接表
int dist[MAXN];  // 距离数组

void dijkstra(int start) {
    fill(dist, dist + MAXN, INF);
    dist[start] = 0;

    // 使用优先队列优化，pair<距离, 节点编号>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;  // 已有更短的路径

        for (auto& edge : graph[u]) {
            int v = edge.to;
            int cost = edge.cost;

            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                pq.push({dist[v], v});
            }
        }
    }
}

Bellman-Ford算法（处理负权）

// Bellman-Ford算法
const int MAXN = 1e3 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, cost;
};

vector<Edge> edges;  // 边集合
int dist[MAXN];  // 距离数组

bool bellmanFord(int n, int start) {
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;

    // 进行n-1轮松弛操作
    for (int i = 1; i < n; i++) {
        bool updated = false;
        for (auto& edge : edges) {
            if (dist[edge.from] != INF && dist[edge.from] + edge.cost < dist[edge.to]) {
                dist[edge.to] = dist[edge.from] + edge.cost;
                updated = true;
            }
        }
        if (!updated) break;  // 如果本轮没有更新，提前退出
    }

    // 检测负权回路
    for (auto& edge : edges) {
        if (dist[edge.from] != INF && dist[edge.from] + edge.cost < dist[edge.to]) {
            return false;  // 存在负权回路
        }
    }

    return true;  // 不存在负权回路
}

Floyd-Warshall算法（多源最短路）

// Floyd-Warshall算法
const int MAXN = 500 + 5;  // 节点数量限制更小
const int INF = 0x3f3f3f3f;

int dist[MAXN][MAXN];  // 距离矩阵

void floyd(int n) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else if (dist[i][j] == 0) dist[i][j] = INF;  // 如果没有直接边，设为无穷
        }
    }

    // Floyd算法主体
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Kruskal算法（最小生成树）

// Kruskal算法（结合并查集）
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;

struct Edge {
    int u, v, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

Edge edges[MAXM];  // 边集合
int parent[MAXN];  // 并查集

// 并查集查找
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

// 最小生成树 - Kruskal算法
int kruskal(int n, int m) {
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 按边权排序
    sort(edges, edges + m);

    int totalCost = 0;  // 最小生成树的总权值
    int edgeCount = 0;  // 已选边数

    for (int i = 0; i < m; i++) {
        int rootU = find(edges[i].u);
        int rootV = find(edges[i].v);

        if (rootU != rootV) {  // 不会形成环
            parent[rootU] = rootV;  // 合并集合
            totalCost += edges[i].cost;
            edgeCount++;

            if (edgeCount == n - 1) break;  // 已找到最小生成树
        }
    }

    return edgeCount == n - 1 ? totalCost : -1;  // 如果不能形成生成树，返回-1
}

动态规划模板

背包问题模板

// 01背包问题
void knapsack01() {
    int n, W;  // n: 物品数量, W: 背包容量
    vector<int> weights(n);  // 物品重量
    vector<int> values(n);   // 物品价值

    // dp[i]: 容量为i的背包能装的最大价值
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // 逆序遍历确保物品只被选择一次
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
}

// 完全背包问题
void unboundedKnapsack() {
    int n, W;  // n: 物品数量, W: 背包容量
    vector<int> weights(n);  // 物品重量
    vector<int> values(n);   // 物品价值

    // dp[i]: 容量为i的背包能装的最大价值
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // 正序遍历允许物品被重复选择
        for (int j = weights[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
}

最长公共子序列 (LCS)

// 最长公共子序列问题
int lcs(string s1, string s2) {
    int n = s1.length();
    int m = s2.length();

    // dp[i][j]: s1[0...i-1]和s2[0...j-1]的最长公共子序列长度
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[n][m];
}

最长递增子序列 (LIS)

// 最长递增子序列问题 - O(n²)解法
int lis_n2(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    // dp[i]: 以nums[i]结尾的最长递增子序列长度
    vector<int> dp(n, 1);
    int result = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        result = max(result, dp[i]);
    }

    return result;
}

// 最长递增子序列问题 - O(nlogn)解法
int lis_nlogn(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    // tails[i]: 长度为i+1的LIS的末尾元素的最小值
    vector<int> tails;

    for (int x : nums) {
        // 二分查找x应该插入的位置
        auto it = lower_bound(tails.begin(), tails.end(), x);

        if (it == tails.end()) {
            tails.push_back(x);  // x比所有尾部元素都大，新增一个长度
        } else {
            *it = x;  // 更新长度为it-tails.begin()+1的LIS的末尾元素
        }
    }

    return tails.size();
}

字符串算法模板

KMP算法

// KMP算法
vector<int> computeLPS(string pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);  // Longest Proper Prefix which is also Suffix

    for (int i = 1, len = 0; i < m; ) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }

    return lps;
}

vector<int> kmpSearch(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> lps = computeLPS(pattern);
    vector<int> matches;  // 存储匹配位置

    for (int i = 0, j = 0; i < n; ) {
        if (pattern[j] == text[i]) {
            i++; j++;
        }

        if (j == m) {  // 找到一个匹配
            matches.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    return matches;
}

Trie树（字典树）

// 字典树（Trie）
struct TrieNode {
    TrieNode* children[26];  // 假设只包含小写字母
    bool isEndOfWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入单词
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
    }

    // 查找单词
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
    }

    // 查找是否有以prefix为前缀的单词
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!node->children[index]) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
};

数学模板

最大公约数与最小公倍数

// 最大公约数（辗转相除法）
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

// 最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 避免a*b可能的溢出
}

快速幂

// 快速幂（非递归实现）
// 计算 (base^exponent) % mod
long long quickPow(long long base, long long exponent, long long mod) {
    long long result = 1;
    base %= mod;

    while (exponent > 0) {
        if (exponent & 1) {
            result = (result * base) % mod;
        }
        exponent >>= 1;
        base = (base * base) % mod;
    }

    return result;
}

素数筛法

// 埃氏筛法
vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

// 线性筛法（欧拉筛）
vector<int> linearSieve(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }

        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;  // 核心优化
        }
    }

    return primes;
}

组合数计算

// 组合数 C(n,k) % mod，使用逆元优化
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

long long fact[MAXN];  // 阶乘
long long invFact[MAXN];  // 阶乘的逆元

// 快速幂计算逆元
long long quickPow(long long x, int n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        n >>= 1;
    }
    return res;
}

// 预处理阶乘及其逆元
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }

    // 计算阶乘的逆元，invFact[n] = fact[n]^(MOD-2) % MOD
    invFact[MAXN-1] = quickPow(fact[MAXN-1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = (invFact[i+1] * (i+1)) % MOD;
    }
}

// 计算组合数 C(n,k) % MOD
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (((fact[n] * invFact[k]) % MOD) * invFact[n-k]) % MOD;
}

完整程序模板

基本框架

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

// 常用类型别名
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;

// 常用常量
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);

// 常用宏定义
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

void solve() {
    // 在这里实现具体的解题逻辑
}

int main() {
    // 关闭同步流，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;  // 如果有多个测试用例
    while (t--) {
        solve();
    }

    return 0;
}

注意事项与使用建议

1. 模板适配：所提供的模板是通用的，在使用时需根据具体问题调整参数、条件和函数实现。

2. 变量命名：在实际比赛中，可以使用更简短的变量名以提高编码速度，但确保命名方式一致且清晰。

3. 边界检查：务必注意数组越界、整数溢出等问题，根据题目数据范围适当选择数据类型。

4. 调试技巧：在模板中添加自己的调试功能，如打印中间结果、检查特定条件等。

5. 个性化定制：随着编程经验的积累，不断调整和完善自己的模板库，使其更符合个人习惯。

6. 复制粘贴注意：使用模板时，小心调整索引起始（0-based vs 1-based）、符号和特殊条件。

总结

本文提供了ACM竞赛中最常用的代码模板，覆盖了基础输入输出、数据结构、图论、动态规划、字符串处理和数学算法等多个方面。这些模板不仅可以提高你的编码效率，还能减少出错的可能性。建议你根据自己的需要和习惯，将这些模板整理成个人的代码库，以便在比赛中快速调用。

记住，模板只是工具，真正的解题能力来自于对算法思想的深刻理解和灵活运用。在比赛中，要根据具体问题选择合适的算法，并将模板与实际情况结合起来。