不止是题解：用第十四届蓝桥杯C++ C组真题，带你吃透贪心、单调队列与Trie树

weixin_33725807

359人浏览 · 2026-06-01 12:59:58

weixin_33725807 · 2026-06-01 12:59:58 发布

蓝桥杯C++算法精讲：贪心、单调队列与Trie树的实战艺术

在算法竞赛的征途中，蓝桥杯始终是检验编程能力的重要试金石。当我们不再满足于简单的AC代码，而是渴望深入理解算法本质时，那些看似普通的竞赛题目便成为绝佳的学习素材。本文将以第十四届蓝桥杯省赛C++ C组的三道典型题目为切入点，带您领略贪心算法、单调队列和Trie树这三种重要数据结构的精妙之处。

1. 贪心算法的战略思维：《三国游戏》深度解析

贪心算法就像一位精明的军事统帅，在每个决策点都做出局部最优选择，最终汇聚成全局胜利。《三国游戏》这道题目正是这种思维的完美体现。

1.1 问题本质与建模技巧

题目要求我们在三个阵营之间分配武将，使得某个阵营的武将总战力超过另外两个阵营之和。这实际上是一个 资源分配最优化问题 ，关键在于发现隐藏在问题背后的数学规律：

设三个阵营的战力分别为A、B、C
我们需要满足A > B + C（或其他两种对称情况）
转化不等式可得：A - B - C > 0

这个简单的数学变形揭示了问题的核心——我们需要最大化某个线性组合的值。这种 问题转化能力 正是算法竞赛中的关键技能。

1.2 贪心策略的构建与证明

正确的贪心策略需要满足两个条件： 局部最优性 和 无后效性 。对于本题，我们可以：

对每个武将，计算其在不同阵营组合下的贡献值
按照贡献值从大到小排序
依次选择武将，直到满足胜利条件

struct Hero {
    int a, b, c;
    int diff() const { return a - b - c; }
};

bool cmp(const Hero& h1, const Hero& h2) {
    return h1.diff() > h2.diff();
}

int max_winning_heroes(vector<Hero>& heroes) {
    sort(heroes.begin(), heroes.end(), cmp);
    int A = 0, B = 0, C = 0;
    int res = 0;
    for (const auto& h : heroes) {
        int newA = A + h.a;
        int newB = B + h.b;
        int newC = C + h.c;
        if (newA > newB + newC || newB > newA + newC || newC > newA + newB) {
            A = newA;
            B = newB;
            C = newC;
            res++;
        } else {
            break;
        }
    }
    return res > 0 ? res : -1;
}

1.3 贪心算法的适用场景与局限

贪心算法并非万能钥匙，它适用于具有 最优子结构 和 贪心选择性质 的问题。在实际应用中，我们需要考虑：

何时使用贪心 ：活动选择、霍夫曼编码、最小生成树等问题
常见陷阱 ：局部最优不等于全局最优的情况
验证方法 ：尝试用反证法或数学归纳法证明贪心选择的正确性

提示：当问题涉及"最大/最小数量"、"最早/最晚时间"等优化目标时，可以优先考虑贪心算法。

2. 单调队列的滑动窗口艺术：《子矩阵》精讲

单调队列是一种神奇的数据结构，它能在O(n)时间内解决各种滑动窗口极值问题。《子矩阵》这道题目展示了如何将其扩展到二维空间。

2.1 从一维到二维的思维跃迁

题目要求我们找出所有k×l子矩阵中的最小值之和。直接暴力枚举的时间复杂度是O(nmkl)，显然无法接受。这时，我们需要分两步优化：

行方向优化 ：对每行使用单调队列预处理，得到行内滑动窗口最小值
列方向优化 ：在行处理结果的基础上，再次使用单调队列处理列方向

这种 降维打击 的思想是解决复杂问题的利器。

2.2 单调队列的实现细节

单调队列的核心在于维护一个 既单调又有效的 元素序列。以下是标准实现：

vector<int> sliding_window_min(const vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        while (!dq.empty() && nums[dq.back()] >= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() <= i - k) {
            dq.pop_front();
        }
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

2.3 二维扩展与性能分析

将一维算法扩展到二维时，需要注意：

先对每行处理，得到row_min[i][j]表示第i行中以j结尾的长度为l的窗口最小值
然后对每列处理，在row_min数组上做长度为k的窗口最小值

这样时间复杂度从O(nmkl)降到了O(nm)，实现了质的飞跃。

方法	时间复杂度	空间复杂度	适用场景
暴力枚举	O(nmkl)	O(1)	小数据量
单调队列	O(nm)	O(nm)	中大数据量
稀疏表	O(nm logk logl)	O(nm logk logl)	静态查询

3. Trie树与异或魔法：《异或和之差》揭秘

Trie树不仅是字符串处理的利器，在数值计算领域也有惊人表现。《异或和之差》展示了如何用Trie树高效解决异或极值问题。

3.1 异或运算的特殊性质

异或操作(XOR)有几个重要特性：

自反性：a ^ a = 0
交换律：a ^ b = b ^ a
结合律：a ^ (b ^ c) = (a ^ b) ^ c
与0的关系：a ^ 0 = a

这些性质使得我们可以用 前缀异或和 来表示任意区间的异或和： sum[l..r] = prefix[r] ^ prefix[l-1]

3.2 Trie树的构建与查询

为了快速找到与给定数异或结果最大/最小的数，我们需要将数字的二进制位存储在Trie树中：

class Trie {
private:
    struct Node {
        Node* children[2] = {nullptr, nullptr};
    };
    Node* root;
public:
    Trie() : root(new Node()) {}
    
    void insert(int num) {
        Node* curr = root;
        for (int i = 20; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (!curr->children[bit]) {
                curr->children[bit] = new Node();
            }
            curr = curr->children[bit];
        }
    }
    
    int findMaxXor(int num) {
        Node* curr = root;
        int res = 0;
        for (int i = 20; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (curr->children[1 - bit]) {
                res |= (1 << i);
                curr = curr->children[1 - bit];
            } else {
                curr = curr->children[bit];
            }
        }
        return res;
    }
};