ACM竞赛题

🏆 ACM-ICPC简介

ACM国际大学生程序设计竞赛（ACM-ICPC）是世界上最具影响力的大学生计算机竞赛，被誉为计算机界的奥林匹克。

📋 竞赛特点

• 团队合作：3人一队，共用一台电脑
• 时间限制：5小时解决8-13道题目
• 实时排名：根据解题数量和用时排名
• 一次提交：每题只有一次AC机会，错误会有时间惩罚

🎯 知识点分布

基础算法 (40%)

• 排序算法
• 搜索算法（DFS、BFS）
• 贪心算法
• 分治算法

数据结构 (25%)

• 线性结构（栈、队列、链表）
• 树结构（二叉树、线段树、树状数组）
• 图结构（邻接表、邻接矩阵）
• 高级结构（并查集、堆）

数学算法 (20%)

• 数论（GCD、LCM、素数）
• 组合数学
• 概率统计
• 线性代数

动态规划 (15%)

• 基础DP
• 区间DP
• 树形DP
• 状态压缩DP

🔥 经典题目

1. 最大子序列和 🟡

题目描述： 给定一个整数序列，求其中连续子序列的最大和。

输入：

6 -2 11 -4 13 -5 -2

输出：

解法：动态规划（Kadane算法）

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

int maxSubArray(vector<int>& nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << maxSubArray(nums) << endl;
    
    return 0;
}

2. 最短路径问题 🔴

题目描述： 给定一个有向图，求从起点到终点的最短路径。

解法：Dijkstra算法

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii;

vector<int> dijkstra(int start, int n, vector<vector<pii>>& graph) {
    vector<int> dist(n + 1, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[start] = 0;
    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.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

int main() {
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    
    vector<vector<pii>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    
    vector<int> dist = dijkstra(start, n, graph);
    
    if (dist[end] == INT_MAX) {
        cout << -1 << endl;  // 无法到达
    } else {
        cout << dist[end] << endl;
    }
    
    return 0;
}

3. 背包问题 🟡

题目描述： 有N个物品和一个容量为V的背包，每个物品有重量w[i]和价值v[i]，求背包能装下的最大价值。

解法：动态规划

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

int knapsack(int n, int capacity, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][capacity];
}

int main() {
    int n, capacity;
    cin >> n >> capacity;
    
    vector<int> weights(n), values(n);
    
    for (int i = 0; i < n; i++) {
        cin >> weights[i] >> values[i];
    }
    
    cout << knapsack(n, capacity, weights, values) << endl;
    
    return 0;
}

4. 并查集应用 🟡

题目描述： 判断图中是否存在环。

解法：并查集

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

class UnionFind {
public:
    vector<int> parent, rank;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;  // 已经在同一集合，形成环
        
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    UnionFind uf(n);
    bool hasCycle = false;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (!uf.unite(u, v)) {
            hasCycle = true;
            break;
        }
    }
    
    cout << (hasCycle ? "YES" : "NO") << endl;
    
    return 0;
}

5. 字符串匹配 🔴

题目描述： 在文本串中查找模式串的所有出现位置。

解法：KMP算法

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

vector<int> computeLPS(string pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

vector<int> KMPSearch(string text, string pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> result;
    
    vector<int> lps = computeLPS(pattern);
    
    int i = 0;  // text的索引
    int j = 0;  // pattern的索引
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            result.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 result;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    
    vector<int> positions = KMPSearch(text, pattern);
    
    cout << positions.size() << endl;
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;
    
    return 0;
}

🎖️ 训练建议

基础阶段（1-3个月）

1. 掌握基本语法：C++/Java/Python
2. 基础算法：排序、搜索、递归
3. 基础数据结构：数组、链表、栈、队列
4. 练习平台：洛谷、HDU Online Judge

进阶阶段（3-6个月）

1. 高级数据结构：树、图、堆、并查集
2. 算法进阶：动态规划、贪心、分治
3. 数学基础：数论、组合数学
4. 练习平台：Codeforces、AtCoder

冲刺阶段（6个月以上）

1. 专项训练：网络流、字符串算法、计算几何
2. 模拟比赛：参加在线比赛
3. 团队配合：与队友协作训练
4. 练习平台：ICPC官方题库、各大学OJ

📚 推荐资源

书籍

• 《算法竞赛入门经典》- 刘汝佳
• 《算法竞赛进阶指南》- 李煜东
• 《挑战程序设计竞赛》- 秋叶拓哉

在线平台

• Codeforces (opens new window)
• AtCoder (opens new window)
• 洛谷 (opens new window)
• HDU Online Judge (opens new window)

学习网站

• OI Wiki (opens new window)
• 算法学习笔记 (opens new window)
• USACO Guide (opens new window)