蓝桥杯国赛C++ B组真题深度解析：递推、DP与贡献度思维实战

1. 项目背景与核心价值

最近在整理历年蓝桥杯国赛的真题时，我又翻出了2020年C++ B组的那套题。这套题在当年引起了不小的讨论，它不像一些年份的题目那样追求极致的算法复杂度，而是在基础算法和编程思维上设置了非常巧妙的“陷阱”和“弯道”。很多选手，包括一些平时刷题不少的同学，都在这里栽了跟头。我之所以想重新梳理这套题，是因为它非常典型地体现了蓝桥杯国赛从“考你会不会”到“考你熟不熟、细不细、活不活”的转变趋势。对于正在备赛的同学来说，吃透这套题的价值，远大于盲目刷十套新题。它更像是一面镜子，能照出你在编程基本功、逻辑严谨性、边界条件处理以及时间/空间复杂度权衡上的真实水平。今天，我就以一名多次参与竞赛辅导的“老司机”视角，带大家深度复盘2020年蓝桥杯国赛C++ B组的几道核心题目，不仅讲“怎么做”，更要讲清楚“为什么这么做”以及“当时容易怎么错”。

2. 试题一：平面分割（递推与空间思维）

这道题是当年国赛的第一道编程大题，题目描述大致是：有20条圆和20条直线，这些圆和直线两两相交，且没有三条线（或圆）交于同一点，问它们最多能把平面分割成多少部分。

很多同学一看到“最多”，再看到圆和直线混合，就有点发懵，容易陷入复杂的几何分类讨论。其实，这是一道经典的“递推”问题，考察的是将复杂问题分解为已知模型的能力。

2.1 问题拆解：从简单到复杂

我们不应该直接思考20圆+20线这个复杂场景。正确的思路是建立模型：

1. 只有直线：n条直线，两两相交且无三线共点，最多能将平面分割成多少部分？这是一个经典公式：L(n) = n*(n+1)/2 + 1。推导思路是：第k条直线，最多可以与前面的k-1条直线相交，产生k-1个新交点，这条直线被这些交点分割成k段，每一段都会将其穿过的原有区域一分为二，即新增k个区域。所以区域数递推公式为：f(k) = f(k-1) + k，初始f(0)=1，求和后即得上述公式。
2. 只有圆：m个圆，两两相交且无三圆共点，最多能将平面分割成多少部分？公式为：C(m) = m*(m-1) + 2。推导思路类似：第k个圆，最多可以与前面k-1个圆相交，每个圆产生两个交点，所以第k个圆上最多有2*(k-1)个交点，这些交点把这个圆分割成2*(k-1)段圆弧，每一段圆弧都会将其穿过的原有区域一分为二，即新增2*(k-1)个区域。递推公式：g(k) = g(k-1) + 2*(k-1)，初始g(0)=1，求和后即得公式。

注意：这里的关键是理解“新增区域”的来源。直线或圆上的每一段“新产生的”弧（或线段），如果它穿过了某个已有的区域，就会把这个区域分成两块。而“最多”的情况，就是确保每一段新弧都穿过一个独立的已有区域。

2.2 混合情况的分析与递推

现在考虑混合情况。我们不能简单地将L(20)和C(20)相加，因为直线和圆之间也会相交，产生新的分割。

我们需要思考增量。假设我们已经有了a条直线和b个圆，它们已经将平面分割成了F(a, b)个部分。现在，我们加入第a+1条直线。

这条新直线，会和已有的a条直线各交于1点，产生a个交点。 同时，它也会和已有的b个圆各交于2点，产生2b个交点。 所以，这条新直线上总共有a + 2b个交点。

这些交点把这条新直线分成了(a + 2b + 1)段（两端也算区间）。每一段，如果它穿过一个已有的区域，就会把这个区域一分为二，从而增加1个区域。在“最多”的假设下，这(a + 2b + 1)段中的每一段都穿过了不同的已有区域。

因此，新增一条直线，带来的区域增量是(a + 2b + 1)。

同理，如果我们加入第b+1个圆。 这个新圆，会和已有的a条直线各交于2点，产生2a个交点。 也会和已有的b个圆各交于2点，产生2b个交点。 所以，这个新圆上总共有2a + 2b个交点。

这些交点把这个新圆分成了(2a + 2b)段圆弧。同样，在“最多”的假设下，每一段弧都穿过一个不同的已有区域。

因此，新增一个圆，带来的区域增量是(2a + 2b)。

2.3 计算过程与代码实现

有了递推关系，我们就可以从零开始，模拟依次添加20条直线和20个圆的过程。初始平面为1部分。

我们可以选择任意添加顺序，因为最终结果与顺序无关（在“最多”的假设下）。一种简单的实现方式是先加完所有直线，再加所有圆，但需要注意在加圆时，直线数量a已经是20了。

更清晰的方法是使用双重循环或直接基于公式计算。这里给出模拟递推的C++代码：

#include <iostream> using namespace std; int main() { long long parts = 1; // 初始平面 int lines = 20, circles = 20; // 先添加20条直线 for (int a = 0; a < lines; ++a) { // 添加第a+1条直线时，已存在a条直线，0个圆 parts += (a + 2*0 + 1); // 增量 = a + 1 } // 此时已有20条直线，再添加20个圆 for (int b = 0; b < circles; ++b) { // 添加第b+1个圆时，已存在20条直线，b个圆 parts += (2*20 + 2*b); // 增量 = 40 + 2b } cout << parts << endl; return 0; }

计算一下： 添加直线：parts = 1 + (1+2+...+20) = 1 + 210 = 211添加圆：parts = 211 + (40+42+44+...+78) = 211 + (40+78)*20/2 = 211 + 1180 = 1391

所以，最终答案是1391。

2.4 易错点与心得

1. 混淆“最多”与“任意”：题目条件是“最多”，这意味着我们必须假设所有交点都产生，且交点不重合。计算增量时，必须用当前已有的直线和圆数量来计算最大可能交点数。如果当成任意情况计算，就会出错。
2. 增量公式记错：直线增量是(a + 2b + 1)，圆增量是(2a + 2b)。这里的系数（直线与圆相交产生2个点）和常数项（直线两端）非常关键。一个常见的错误是忘记+1，或者把圆的增量误写成2(a+b)+1。
3. 数据类型溢出：最终结果1391虽然不大，但在递推过程中，部分中间结果可能超过int范围（如果规模更大）。使用long long是更安全的竞赛习惯。
4. 实战心得：遇到这种“平面分割”问题，第一步永远是退回到最简单模型（只有直线、只有圆），推导或回忆其公式。第二步，思考新增元素带来的“切割段数”，这个段数就是区域增量。这比直接死记硬背混合公式要可靠得多。

3. 试题二：数字三角形（动态规划与路径回溯）

这道题是经典数字三角形的变种。题目通常给定一个数字三角形，从顶部走到底部，每次只能走到下一行相邻的两个位置，求经过数字之和的最大值。但国赛的题目往往会增加限制条件，比如“向左下走的次数和向右下走的次数相差不能超过1”。

3.1 经典DP解法回顾

如果没有额外限制，这就是一个最基础的动态规划问题。 设dp[i][j]表示从顶部走到第i行第j列（从0或1开始计数）所能获得的最大和。 状态转移方程为：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。 最终答案就是最后一行dp中的最大值。

3.2 限制条件的分析与转化

“向左下走的次数和向右下走的次数相差不能超过1”这个条件，限制了路径的终点。

想象一个高度为n的三角形。从顶点到底边，一共需要走n-1步。 设向左下走了L步，向右下走了R步，则有L + R = n - 1。 条件要求|L - R| <= 1。

解这个方程：

• 如果n-1是偶数，则L = R = (n-1)/2。这意味着路径终点一定是底行的最中间那个数（如果底行有奇数个数）？不对，需要更精确。
• 如果n-1是奇数，则L和R相差1。比如L = R+1或R = L+1。这意味着终点会偏向一边。

其实，这描述的是在多层决策后，左右步数的平衡性。有一个更直观的几何理解：将向左下走视为坐标-1，向右下走视为坐标+1（假设水平方向）。从顶点(0,0)出发，走n-1步后，横坐标x的范围是[-(n-1), n-1]，且步数差L-R就是-x。条件|L-R|<=1即|x|<=1。

所以，合法的终点对应的列索引（假设顶点列索引为0）的绝对值不能超过1。对于底边有n个数的三角形，其列索引范围是[0, n-1]。我们需要将上述理论坐标映射到实际的数组索引上。

通常我们这样构建三角形：第i行有i+1个数，索引j从0到i。从(i, j)可以走到(i+1, j)（左下）和(i+1, j+1)（右下）。那么，从(0,0)出发，走到(i, j)的位置，向右下走的次数就是j，向左下走的次数就是i - j。（因为每向右下一次，列索引+1）。 所以，L = i - j,R = j。条件|L - R| <= 1即|i - 2*j| <= 1。

当走到最后一行i = n-1时，条件变为| (n-1) - 2*j | <= 1。 我们需要找出所有满足这个条件的列索引j，然后取dp[n-1][j]的最大值。

3.3 算法实现与细节

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<vector<int>> triangle(n, vector<int>(n, 0)); vector<vector<int>> dp(n, vector<int>(n, 0)); // 读入数据，只使用左下三角部分 for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { cin >> triangle[i][j]; } } // 初始化DP dp[0][0] = triangle[0][0]; // 状态转移 for (int i = 1; i < n; ++i) { for (int j = 0; j <= i; ++j) { dp[i][j] = triangle[i][j]; if (j == 0) { // 最左边，只能从上一行同列下来（即从右上角下来，但此处是左下走法） dp[i][j] += dp[i-1][j]; } else if (j == i) { // 最右边，只能从上一行前一列下来（即从左下下来） dp[i][j] += dp[i-1][j-1]; } else { dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]); } } } // 根据限制条件找出合法终点 int ans = 0; for (int j = 0; j < n; ++j) { if (abs((n-1) - 2*j) <= 1) { // 核心判断条件 ans = max(ans, dp[n-1][j]); } } cout << ans << endl; return 0; }

3.4 易错点与心得

1. 对限制条件的错误理解：最常见的错误是忽略了这个条件，或者错误地认为它限制了每一步的选择。实际上，它只约束了整条路径的宏观形态，最终体现在终点位置的选择上。DP过程本身不受影响。
2. 终点列索引的计算：推导|i - 2*j| <= 1这个条件是解题关键。直接去枚举L和R的组合也可以，但不如这个公式简洁高效。务必理解其推导过程。
3. 边界处理：在DP循环中，对每一行的第一个元素(j==0)和最后一个元素(j==i)要单独处理，因为它们只有一个来源。
4. 输入数据的存储：题目通常给的是三角形数据，用二维数组存储时，注意未使用的部分（右上三角）可以置0或不处理，但要确保DP时不会越界访问。
5. 实战心得：遇到带限制条件的DP，先思考这个条件影响了DP的哪个部分（状态定义、转移方程、初始条件、答案提取）。像本题，它只影响“答案提取”阶段，那么DP的核心部分就不用变。这是一种非常重要的解题技巧——分离关注点。

4. 试题三：子串分值（贡献度思维）

这道题是字符串处理中非常考验思维的一道题。题目定义了一个字符串S的“分值”为：其所有非空子串的“唯一字符个数”之和。对于一个子串，它的“唯一字符个数”是指在这个子串中只出现一次的字符的个数。要求计算给定字符串S的分值。

例如：字符串"aba"，其所有非空子串有："a"(1),"ab"(2),"aba"(1),"b"(1),"ba"(2),"a"(1)。分值为 1+2+1+1+2+1 = 8。

暴力枚举所有子串是 O(n²) 的复杂度，对于每个子串统计唯一字符又是 O(n)，总复杂度 O(n³)，对于 n 可能达到 10^5 的数据范围完全不可行。

4.1 贡献度思维：换个角度思考

我们不能着眼于“每个子串有多少个唯一字符”，而应该着眼于每个字符，在多少个子串中，能成为“唯一字符”。

对于字符串中的第i个字符S[i]（假设索引从0开始），我们考虑它在哪些子串里是唯一的。

假设在S[i]的左边，离它最近的与它相同的字符位置是left（如果没有，则left = -1）。 在S[i]的右边，离它最近的与它相同的字符位置是right（如果没有，则right = n，n为字符串长度）。

那么，对于S[i]而言，它要想在一个子串中是唯一的，这个子串必须包含S[i]，但不能包含S[left]和S[right]。

这意味着，这个子串的起始位置必须在(left, i]这个左开右闭区间内选择，结束位置必须在[i, right)这个左闭右开区间内选择。

• 起始位置有(i - left)种选择（从left+1到i）。
• 结束位置有(right - i)种选择（从i到right-1）。

根据乘法原理，S[i]能作为唯一字符出现的子串数量，就是(i - left) * (right - i)。

字符串 S 的分值，就是将所有字符的这个贡献值加起来：sum( (i - left[i]) * (right[i] - i) )，其中left[i]和right[i]分别表示字符S[i]左右两边最近相同字符的位置。

4.2 如何高效计算 left 和 right 数组

我们需要对字符串中每种字符，快速找到每个位置左右两边最近的出现位置。

一种高效的方法是预处理每个字符出现的位置列表。

对于字符ch，假设它出现的位置数组是pos[ch] = [p1, p2, p3, ..., pk]。 那么对于位置p2来说：

• 它左边的最近相同字符位置是p1。
• 它右边的最近相同字符位置是p3。 对于位置p1，左边没有相同字符，left = -1；右边最近是p2。 对于位置pk，左边最近是p_{k-1}；右边没有相同字符，right = n。

我们可以遍历字符串一次，记录每个字符上一次出现的位置，从而得到left数组。 然后，再逆序遍历字符串，记录每个字符下一次出现的位置，从而得到right数组。

4.3 算法实现

#include <iostream> #include <string> #include <vector> using namespace std; int main() { string s; cin >> s; int n = s.length(); vector<int> left(n, -1), right(n, n); vector<int> last_pos(26, -1); // 假设字符串只包含小写字母 // 计算 left 数组：记录每个字符上一次出现的位置 for (int i = 0; i < n; ++i) { int idx = s[i] - 'a'; if (last_pos[idx] != -1) { left[i] = last_pos[idx]; } last_pos[idx] = i; // 更新该字符最后出现的位置 } // 重置 last_pos，用于计算 right 数组 fill(last_pos.begin(), last_pos.end(), n); // 计算 right 数组：记录每个字符下一次出现的位置 for (int i = n - 1; i >= 0; --i) { int idx = s[i] - 'a'; if (last_pos[idx] != n) { right[i] = last_pos[idx]; } last_pos[idx] = i; // 更新该字符最后出现的位置（从右向左） } // 计算总贡献值 long long ans = 0; // 注意用 long long，结果可能很大 for (int i = 0; i < n; ++i) { ans += (long long)(i - left[i]) * (right[i] - i); } cout << ans << endl; return 0; }

4.4 易错点与心得

1. 思维定式：最容易犯的错误就是陷入“枚举子串”的暴力思维。竞赛中看到“所有子串的XX之和”，要立刻条件反射地想到“贡献度”思维——计算每个元素对总答案的贡献。
2. 边界处理：left数组的初始值应为-1，right数组的初始值应为n。这代表了“左边/右边没有相同字符”的边界情况。处理不当会导致贡献值计算错误。
3. 数据类型溢出：贡献值(i-left)*(right-i)可能很大，两个int相乘可能溢出，需要转换为long long再进行累加。这是竞赛中非常常见的坑。
4. 字符集范围：示例代码假设了字符串只有小写字母。如果字符集更大（如ASCII全部字符），last_pos数组的大小应调整为128或256。如果字符集未知或很大，可以使用unordered_map<char, int>来记录位置。
5. 实战心得：“贡献度”是处理子串、子数组类求和问题的利器。类似的题目还有“子串中不同字符个数之和”、“子数组最小值之和”等。核心思路都是：不从整体看部分，而从部分（每个元素）看它影响了哪些整体（子串/子数组）。

5. 试题四：荒岛探测（计算几何与积分思想）

这道题是当年国赛的压轴题之一，综合性很强。题目描述了一个椭圆（探测器信号范围）和一个三角形（荒岛区域），要求计算椭圆与三角形重合部分的面积。这本质是一个计算几何问题，但直接求任意多边形与椭圆的交集面积非常复杂。

5.1 问题转化：暴力法的局限与优化方向

最直接的想法是蒙特卡洛方法：在三角形和椭圆的外接矩形内随机撒大量点，统计落在交集内的点的比例，乘以矩形面积得到近似面积。但这种方法精度低、速度慢，且竞赛中通常要求精确解或高精度解。

另一种思路是多边形裁剪：用椭圆曲线去裁剪三角形多边形。但椭圆是二次曲线，裁剪算法（如Sutherland-Hodgman）通常针对直线裁剪，处理曲线边界非常麻烦。

本题的突破口在于题目可能给出的特殊条件（回忆真题）：椭圆的焦点在x轴上，且三角形的一条边与x轴平行。这个条件极大地简化了问题。

5.2 基于定积分的面积计算

如果椭圆是标准的x^2/a^2 + y^2/b^2 = 1，且三角形底边在x轴上（假设为从x1到x2的一条线段），那么椭圆与三角形重叠的部分，可以看作是一个曲边梯形的面积减去（或加上）几个三角形面积。

具体步骤：

1. 坐标变换：将椭圆平移旋转，使其标准方程成立，同时相应变换三角形的顶点坐标。如果椭圆焦点在x轴，且长轴与x轴平行，那么可能只需要平移。
2. 确定积分区间：找出三角形与椭圆在x轴方向上的重叠区间[L, R]。这可以通过求解三角形三条边与椭圆的交点x坐标得到。
3. 计算曲边梯形面积：在重叠区间[L, R]内，椭圆的上半部分曲线方程为y = b * sqrt(1 - x^2/a^2)。我们需要计算的是，在这个区间内，椭圆曲线、x轴、以及三角形的斜边所围成的区域面积。这需要根据三角形斜边在椭圆上方还是下方，对面积进行加减。
   • 如果三角形的斜边（在区间内）在椭圆上方，那么重叠部分面积 =∫(椭圆上曲线) dx - ∫(三角形斜边) dx（在公共区间内）。
   • 如果三角形的斜边在椭圆下方，那么重叠部分就是椭圆曲线到x轴的面积，但还需要考虑三角形是否完全在椭圆内，情况更复杂。实际上，更通用的方法是：计算在x处，椭圆曲线y值y_ellipse(x)与三角形在该x处对应的y值y_triangle(x)的最小值（因为底部是x轴，取两者中靠下的那条线作为上边界？不对）。我们需要的是椭圆与三角形公共部分的面积。可以转化为：在x处，从x轴到min(y_ellipse(x), y_triangle(x))的积分，但前提是y_triangle(x)在这个x处有定义（即x在三角形投影内）。
4. 分段积分：由于三角形的边是直线，其表达式在x的某些区间内会发生变化（例如，穿过三角形顶点）。因此，需要根据三角形与椭圆在x方向上的交点，将积分区间[L, R]进一步细分为若干个子区间，在每个子区间内，y_triangle(x)由一条固定的直线方程描述。
5. 数值积分：最终的积分表达式∫ sqrt(1 - x^2/a^2) dx或∫ min( sqrt(1 - x^2/a^2), kx+b) dx可能没有初等函数形式的原函数。在竞赛中，通常允许使用自适应辛普森积分等数值方法来计算定积分，达到要求的精度即可。

5.3 自适应辛普森积分法

自适应辛普森积分是计算给定区间[l, r]上函数f(x)的定积分的有效数值方法。

#include <iostream> #include <cmath> #include <iomanip> using namespace std; double a, b; // 椭圆参数 // 假设三角形由三条直线描述，这里简化：我们只关心在某个x处，三角形的高度y_tri(x) // 实际代码中，需要根据三角形顶点坐标，求出每条边的直线方程，并实现一个函数，给定x，返回三角形在该x处的y值（可能有多值，取与椭圆比较的相关值） double f(double x) { // 这是被积函数。例如，如果我们求的是椭圆上半部分与x轴之间的面积，那么： if (x < -a || x > a) return 0; // x超出椭圆范围 double y_ellipse = b * sqrt(1 - x*x/(a*a)); double y_triangle = ...; // 根据三角形方程计算，这里需要具体实现 // 假设我们要求椭圆与三角形重叠部分，在x处的“高度”是两者中较小的一个（因为从x轴向上看） // 但更准确地说，是求 min(y_ellipse, y_triangle) 从 x轴 到 该值的积分，如果该值>0。 // 实际上，重叠部分在x处的垂直截线长度是 min(y_ellipse, max(y_triangle, 0))？情况复杂。 // 这里仅以椭圆面积为例： return y_ellipse; } // 辛普森公式 double simpson(double l, double r) { double mid = (l + r) / 2; return (r - l) * (f(l) + 4*f(mid) + f(r)) / 6; } // 自适应辛普森递归计算 double asr(double l, double r, double eps, double whole_area) { double mid = (l + r) / 2; double left_area = simpson(l, mid); double right_area = simpson(mid, r); if (fabs(left_area + right_area - whole_area) < 15 * eps) { return left_area + right_area + (left_area + right_area - whole_area) / 15; } return asr(l, mid, eps/2, left_area) + asr(mid, r, eps/2, right_area); } // 主函数调用 double calculate_area(double l, double r, double eps) { return asr(l, r, eps, simpson(l, r)); }

5.4 易错点与心得

1. 几何情况分析不全：这是本题最大的难点。椭圆和三角形的位置关系有多种：包含、相交、相离。相交又分为三角形顶点在椭圆内、边穿过椭圆等多种情况。必须对所有情况进行分类讨论，或者设计一个能处理所有情况的通用积分函数（如计算在x处，椭圆与三角形区域的垂直重叠长度）。
2. 积分函数定义错误：被积函数f(x)不是简单的椭圆y值。它表示在横坐标x处，椭圆与三角形公共部分的垂直高度。如果三角形在该x处不存在（x不在三角形水平投影内），则高度为0；如果存在，则高度为min(y_ellipse(x), y_triangle_upper(x)) - max(0, y_triangle_lower(x))，其中y_triangle_upper和y_triangle_lower是三角形在x处的上下边界（对于与x轴平行的底边，下边界可能是0）。这需要根据三角形具体形状仔细推导。
3. 数值积分精度：自适应辛普森积分的精度参数eps需要设置合理，太小会超时，太大会精度不足。通常对于输出浮点数的题目，eps设为1e-6或1e-7是安全的。
4. 坐标变换：如果椭圆不是标准位置，必须先通过平移和旋转将椭圆变换到标准方程x^2/a^2 + y^2/b^2 = 1，同时对三角形的所有顶点进行相同的变换。这是计算几何中的常规操作，但涉及矩阵运算，容易出错。
5. 实战心得：国赛出现这种题，往往不期望选手写出完美解决所有情况的代码。更常见的考察点是：1) 能否将问题转化为积分模型；2) 能否正确实现数值积分；3) 能否处理一种或几种特定的、简化后的情况（如三角形底边在x轴）。在考场上，如果时间有限，应优先保证核心算法（如自适应辛普森积分）的正确实现，并对简单情况（如三角形完全在椭圆内，或底边在x轴上的直角三角形）进行准确计算，拿到部分分数。