算法竞赛之路-从蓝桥杯到ACM的心路历程

前言

算法竞赛是我大学生活中最重要的经历之一。从蓝桥杯省赛到 ACM 区域赛，这段旅程不仅锻炼了我的编程能力，更培养了我解决问题的思维方式。今天想和大家分享我的竞赛之路。

初识算法竞赛

大一的迷茫

刚入学时，我对编程的了解仅限于课本上的基础知识。一次偶然的机会，我参加了学院的算法兴趣小组，第一次接触到了算法竞赛。

记得第一次做算法题时，一道简单的排序题让我折腾了整整一个下午。但当我终于 AC（Accepted）的那一刻，那种成就感让我迷上了算法。

基础学习路线

第1阶段：语言基础
  - C/C++ 语法
  - 基本输入输出
  - 数组、字符串操作

第2阶段：基础算法
  - 排序算法（快排、归并）
  - 二分查找
  - 简单贪心、模拟

第3阶段：数据结构
  - 栈、队列、链表
  - 二叉树、堆
  - 并查集

第4阶段：进阶算法
  - 动态规划
  - 图论算法
  - 数论、组合数学

蓝桥杯备赛经历

省赛准备（大二上学期）

蓝桥杯是我参加的第一个正式比赛。准备期间，我制定了详细的训练计划：

每日训练安排：

• 早上：2 道算法题（LeetCode/Codeforces）
• 下午：专题学习（DP/图论/数据结构）
• 晚上：复盘总结，整理模板

我的算法模板库

// 快速排序模板
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    int pivot = arr[(left + right) >> 1];
    int i = left - 1, j = right + 1;
    
    while (i < j) {
        do i++; while (arr[i] < pivot);
        do j--; while (arr[j] > pivot);
        if (i < j) swap(arr[i], arr[j]);
    }
    
    quickSort(arr, left, j);
    quickSort(arr, j + 1, right);
}

// 并查集模板
class UnionFind {
public:
    vector<int> parent, rank_;
    
    UnionFind(int n) {
        parent.resize(n);
        rank_.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank_[i] = 1;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        
        // 按秩合并
        if (rank_[fx] < rank_[fy]) swap(fx, fy);
        parent[fy] = fx;
        if (rank_[fx] == rank_[fy]) rank_[fx]++;
    }
};

// 线段树模板
class SegmentTree {
    vector<int> tree, lazy;
    int n;
    
public:
    SegmentTree(int size) {
        n = size;
        tree.resize(4 * n);
        lazy.resize(4 * n);
    }
    
    void pushUp(int node) {
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    
    void pushDown(int node, int left, int right) {
        if (lazy[node]) {
            int mid = (left + right) >> 1;
            tree[node * 2] += lazy[node] * (mid - left + 1);
            tree[node * 2 + 1] += lazy[node] * (right - mid);
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }
    
    void update(int node, int left, int right, int l, int r, int val) {
        if (l <= left && right <= r) {
            tree[node] += val * (right - left + 1);
            lazy[node] += val;
            return;
        }
        pushDown(node, left, right);
        int mid = (left + right) >> 1;
        if (l <= mid) update(node * 2, left, mid, l, r, val);
        if (r > mid) update(node * 2 + 1, mid + 1, right, l, r, val);
        pushUp(node);
    }
    
    int query(int node, int left, int right, int l, int r) {
        if (l <= left && right <= r) return tree[node];
        pushDown(node, left, right);
        int mid = (left + right) >> 1;
        int res = 0;
        if (l <= mid) res += query(node * 2, left, mid, l, r);
        if (r > mid) res += query(node * 2 + 1, mid + 1, right, l, r);
        return res;
    }
};

省赛比赛日

比赛当天，我遇到了一道让我印象深刻的题目：

题目大意： 给定一个 n×m 的网格，从左上角走到右下角，只能向右或向下走，求路径上数字和的最大值。

这是一道经典的动态规划题目。我的解法：

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

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];
    
    // dp[i][j] 表示到达 (i,j) 的最大路径和
    vector<vector<long long>> dp(n, vector<long long>(m));
    dp[0][0] = grid[0][0];
    
    // 初始化第一行和第一列
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < m; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];
    
    // 状态转移
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    cout << dp[n-1][m-1] << endl;
    return 0;
}

ACM 竞赛经历

组队与分工

ACM 是团队赛，我们三人小组的分工：

• 我：负责数据结构、图论、动态规划
• 队友A：负责数学、几何、字符串
• 队友B：负责贪心、模拟、代码实现

区域赛备战

备战 ACM 区域赛的日子是艰苦但充实的：

训练强度：

• 每周 3 场模拟赛（5 小时/场）
• 赛后补题、总结
• 定期专题训练

常用训练平台：

• Codeforces（ Div2/Div3 ）
• AtCoder（ ABC/ARC ）
• 洛谷（专题训练）
• Virtual Judge（模拟赛）

经典题型总结

1. 最短路问题

// Dijkstra 算法（堆优化）
typedef pair<int, int> PII;

vector<int> dijkstra(int start, vector<vector<PII>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[start] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

2. 树形 DP

// 树的最大独立集
void treeDP(int u, int parent) {
    dp[u][0] = 0; // 不选 u
    dp[u][1] = weight[u]; // 选 u
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        treeDP(v, u);
        
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0]; // 选 u 则不能选子节点
    }
}

竞赛收获

技术能力提升

1. 代码能力：能够快速写出正确、高效的代码
2. 算法思维：学会分析问题、设计算法
3. 调试能力：在压力下快速定位和修复 bug
4. 团队协作：与队友配合，分工合作

对工作的帮助

算法竞赛的经历对我的后端开发工作有很大帮助：

• 性能优化：能够分析算法复杂度，优化慢查询
• 系统设计：理解数据结构和算法在系统中的应用
• 问题解决：面对复杂问题时更有思路

给学弟学妹的建议

1. 坚持练习：算法是练出来的，每天至少一道题
2. 及时总结：建立个人模板库，整理常见套路
3. 参加模拟赛：适应比赛节奏，锻炼心态
4. 团队协作：ACM 是团队赛，学会分工配合
5. 享受过程：不要太在意结果，享受解题的乐趣

结语

算法竞赛教会我的不仅是算法知识，更是一种解决问题的思维方式。这种思维方式在工作中同样重要。

如果你也对算法竞赛感兴趣，欢迎一起交流！

---

本文记录我的算法竞赛经历，多次获得蓝桥杯/ACM省级奖项