C++算法竞赛实战笔记：从基础到高级技巧

管老太

1. 为什么需要一份C++算法笔记

刚开始接触算法竞赛时，我经常遇到这样的困境：明明看过某个算法的讲解，真正做题时却总是卡在细节实现上。后来发现，系统化的笔记记录能够显著提升学习效率——特别是对C++这种需要精确控制底层细节的语言而言。

这份笔记最初只是我个人刷题时的代码片段集合，后来逐渐演变成包含算法思想、模板代码和易错点分析的综合手册。不同于教材上的理论说明，这里所有内容都经过LeetCode、Codeforces等平台真实题目的验证，每个代码片段都能直接用于解题。

2. 基础数据结构与算法实现

2.1 数组与链表的操作技巧

在算法题中，数组处理有个经典技巧：双指针法。以删除排序数组中的重复项为例：

cpp复制int removeDuplicates(vector<int>& nums) {
    if(nums.empty()) return 0;
    int slow = 0;
    for(int fast=1; fast<nums.size(); ++fast){
        if(nums[fast] != nums[slow]){
            nums[++slow] = nums[fast];
        }
    }
    return slow+1;
}

注意：slow指针始终指向已处理序列的末尾，这种写法比直接erase更高效，时间复杂度O(n)且不额外分配空间

链表操作中，虚拟头节点(dummy node)能大幅简化边界条件处理。比如在删除链表节点时：

cpp复制ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* cur = &dummy;
    while(cur->next){
        if(cur->next->val == val){
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp; // 避免内存泄漏
        }else{
            cur = cur->next;
        }
    }
    return dummy.next;
}

2.2 排序算法的工程实践

虽然STL提供了sort函数，但理解不同排序的适用场景很重要。快速排序的工业级实现需要考虑很多细节：

cpp复制void quickSort(vector<int>& arr, int l, int r) {
    if(l >= r) return;
    // 三数取中法选择pivot
    int mid = l + (r-l)/2;
    if(arr[l] > arr[r]) swap(arr[l], arr[r]);
    if(arr[mid] > arr[r]) swap(arr[mid], arr[r]);
    if(arr[mid] > arr[l]) swap(arr[mid], arr[l]);
    
    int pivot = arr[l];
    int i=l, j=r;
    while(i<j){
        while(i<j && arr[j]>=pivot) j--;
        arr[i] = arr[j];
        while(i<j && arr[i]<=pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, l, i-1);
    quickSort(arr, i+1, r);
}

实测发现：当数据量小于20时，插入排序反而更快。可以在递归到小数组时切换排序策略

3. 高级算法模板与应用

3.1 动态规划的四种经典模型

背包问题模板（01背包为例）：

cpp复制int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    vector<int> dp(capacity+1, 0);
    for(int i=0; i<weights.size(); ++i){
        for(int j=capacity; j>=weights[i]; --j){
            dp[j] = max(dp[j], dp[j-weights[i]]+values[i]);
        }
    }
    return dp[capacity];
}

最长公共子序列(LCS)模板：

cpp复制int longestCommonSubsequence(string text1, string text2) {
    vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));
    for(int i=1; i<=text1.size(); ++i){
        for(int j=1; j<=text2.size(); ++j){
            if(text1[i-1]==text2[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[text1.size()][text2.size()];
}

3.2 图论算法的实现细节

Dijkstra算法在实现时，优先队列的选择直接影响性能。使用STL的priority_queue需要正确处理比较函数：

cpp复制vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) {
    vector<int> dist(graph.size(), INT_MAX);
    dist[start] = 0;
    // 小顶堆，存储(距离, 节点)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.emplace(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[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

踩坑记录：默认的priority_queue是大顶堆，必须显式指定greater<>才能得到小顶堆。此外，不处理"旧数据"会导致性能下降2-3倍

4. 算法竞赛中的实用技巧

4.1 输入输出加速技巧

在数据量大的题目中，IO可能成为瓶颈。C++关闭同步流可以显著提升速度：

cpp复制ios::sync_with_stdio(false);
cin.tie(nullptr);

配合快速读写模板：

cpp复制inline int read() {
    int x=0; bool s=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')s=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return s?x:-x;
}

void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

4.2 调试与性能分析

使用条件编译实现调试输出，比赛时无需手动删除：

cpp复制#define DEBUG 1
#if DEBUG
#define debug(x) cerr << #x << "=" << x << endl
#else
#define debug(x) 
#endif

性能分析工具示例（测量函数耗时）：

cpp复制auto start = chrono::high_resolution_clock::now();
// 被测代码
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(end-start);
cout << "耗时：" << duration.count() << "微秒" << endl;

5. 常见错误与优化策略

5.1 内存访问越界防护

vector的at()方法比[]运算符更安全（会进行边界检查），但在竞赛中为了速度通常直接用[]。可以添加以下防御代码：

cpp复制#define _GLIBCXX_DEBUG  // 开启STL调试模式

常见越界场景：

忘记处理空输入（如nums.empty()）
循环条件写成i<=n而不是i<n
二维数组行列索引混淆

5.2 算法复杂度优化实例

以两数之和为例，对比不同实现的时间复杂度：

暴力解法 O(n²)：

cpp复制vector<int> twoSum(vector<int>& nums, int target) {
    for(int i=0; i<nums.size(); ++i){
        for(int j=i+1; j<nums.size(); ++j){
            if(nums[i]+nums[j]==target){
                return {i,j};
            }
        }
    }
    return {};
}

哈希表优化 O(n)：

cpp复制vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> seen;
    for(int i=0; i<nums.size(); ++i){
        int complement = target - nums[i];
        if(seen.count(complement)){
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

实际测试：当n=10⁶时，哈希表解法比暴力法快约1000倍。但需要注意哈希表的内存开销

6. C++特性在算法中的应用

6.1 Lambda表达式的妙用

自定义排序时，lambda比定义比较函数更简洁：

cpp复制sort(points.begin(), points.end(), [](const auto& a, const auto& b){
    return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
});

在DFS中捕获局部变量：

cpp复制void traverse(TreeNode* root) {
    vector<int> res;
    function<void(TreeNode*)> dfs = [&](TreeNode* node){
        if(!node) return;
        res.push_back(node->val);
        dfs(node->left);
        dfs(node->right);
    };
    dfs(root);
}

6.2 移动语义与算法优化

使用move语义避免不必要的拷贝：

cpp复制vector<string> processStrings(vector<string>& input) {
    vector<string> result;
    for(auto& s : input){
        if(s.size() > 5){
            result.push_back(move(s)); // 转移所有权
        }
    }
    return result;
}

在并查集(Union-Find)实现中，路径压缩的现代C++写法：

cpp复制class UnionFind {
    vector<int> parent;
public:
    UnionFind(int n) : parent(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }
    
    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};