1. 项目概述一次对经典赛题的深度复盘最近整理硬盘翻到了几年前备赛蓝桥杯时留下的笔记和代码其中2017年B组C国赛的几道题让我印象尤为深刻。那年的题目在算法思维和工程实现上结合得相当巧妙既有对基础数据结构的扎实考察也不乏需要灵光一现的“脑筋急转弯”。虽然标题里写的是“部分题解”但我想挑出其中最具代表性的三道题不仅给出答案更重要的是拆解当时的解题心路历程、代码实现中的关键抉择以及那些赛后复盘才恍然大悟的优化点。无论你是正在备赛的选手还是想通过真题来锤炼自己C算法能力的开发者相信这次“穿越时空”的复盘都能带来一些实实在在的收获。我们不会停留在“AC”就万事大吉的层面而是会深入探讨为什么这道题用这个算法边界条件到底坑在哪里从暴力枚举到最优解思维是如何一步步跃迁的2. 核心赛题解析与解题思路拆解2.1 真题定位与整体难度评估2017年蓝桥杯软件类国赛C大学B组的题目延续了其一贯的风格前面几题侧重基础语法和简单逻辑用于“保分”中间部分考察经典算法如DFS、BFS、动态规划的应用能力最后压轴题则往往需要较强的数学建模或抽象思维能力。这次我们重点分析的“部分”题目正是选自中后段的精华它们能有效区分出“会写代码”和“善于用算法解决问题”的选手。从网络热词如“快速幂算法c”、“c八大排序算法”、“动态规划”可以看出大家关注的正是这些核心的算法考点。而“蓝桥杯真题”、“题解”等高频搜索词则反映了大量学习者渴望获得的不只是答案更是清晰的解题逻辑和可复现的思考过程。因此我们的解析将紧扣“思路产生-算法选择-代码实现-边界处理”这条主线。2.2 解题通用心法与赛场策略在深入具体题目之前有必要先统一一下“作战思想”。蓝桥杯的评测系统是OI赛制即提交后立即知道对错但看不到具体用例。这带来两个核心策略暴力法保底对于任何题目第一时间思考能否用简单的模拟或枚举拿到部分分数。即使时间复杂度很高也可能通过一些数据规模较小的测试点。这是非常重要的得分策略切忌在难题上钻牛角尖而浪费了简单题的分数。观察数据范围定算法题目给出的数据范围如N1000或N100000是选择算法的决定性依据。N20可能暗示状压DP或暴力DFSN1000 O(n²)的动态规划或朴素算法可能可行N100000则通常要求O(nlogn)或O(n)的算法。注意赛场上的第一要务是拿到尽可能多的分数而不是追求每道题的最优解。一个能通过60%测试点的暴力解远比一个思路完美但调试了1小时仍有bug的“最优解”有价值。3. 赛题一方格分割DFS与对称性剪枝3.1 问题重述与抽象建模这是当年一道非常经典的搜索问题。题目大意是一个6x6的方格矩阵沿着格线将其分割成完全相同的两部分。要求分割线必须从矩阵的中心点格点不是格子出发到达矩阵的边界并且分割线不能自交。问一共有多少种不同的分割方案。初看此题很容易被“分割成两部分”迷惑去思考如何切割格子。关键的抽象技巧在于转换视角不要盯着“剪开的格子”而是关注“走过的格点”。将6x6的方格扩展为7x7的格点阵因为格线交点才是格点。中心点是(3,3)。问题转化为从中心点(3,3)出发每次向上、下、左、右四个方向移动一格走到边界点即x或y坐标为0或6为止。要求走过的路径必须关于中心点(3,3)中心对称且路径不能重复访问同一个格点保证不自交。为什么是对称的因为剪开成相同的两部分意味着你在这部分边界上走出的路径在另一部分的边界上必然存在一条完全中心对称的路径。而这两条对称的路径合起来就是一条从中心到边界、再对称折返到中心的闭合路径不这里容易出错。更准确地说我们只需要搜索一条从中心到边界的路径其对称路径会自动生成。同时由于整个图形是中心对称的一条路径和它的对称路径会将所有格点分成两个集合。为了避免重复计算顺时针走和逆时针走被视为同一种分割我们需要在搜索时施加一个方向限制。3.2 DFS实现与关键剪枝策略基于以上分析我们可以采用深度优先搜索DFS来枚举所有从(3,3)到边界的路径并检查其对称性。但直接DFS的搜索树会非常庞大。核心剪枝对称性剪枝与方向限制由于最终分割方案是中心对称的那么如果我们搜索的路径触碰到了它的对称点就会导致路径自交因为对称点本应是另一部分的。因此在DFS过程中我们每走到一个新点(x, y)不仅要标记这个点已访问还必须立即标记其对称点(6-x, 6-y)也为已访问。这样就能天然保证搜索出的路径不会侵犯对称区域。方向限制以去重由于一种分割方案由一条中心对称的闭合边界构成从中心点出发第一步有四个方向。但是上下、左右是对称的。如果我们不加以限制会把本质上相同的方案旋转或对称后一致重复计算。一个简单有效的去重方法是规定第一步只能走一个方向比如向右或向下。因为任何合法方案都可以通过旋转使其第一步是向右的。这样最终结果需要乘以4吗不需要因为我们在标记对称点时已经将整个搜索空间约束在了第一象限相对概念最终结果就是唯一计数。#include iostream #include cstring using namespace std; int dirs[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; // 四个方向 bool visited[7][7]; // 标记7x7格点是否已访问 int ans 0; void dfs(int x, int y) { // 到达边界不能是中心点 if (x 0 || x 6 || y 0 || y 6) { ans; return; } for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; // 检查新坐标是否合法且未访问 if (nx 0 nx 6 ny 0 ny 6 !visited[nx][ny]) { // 标记当前点及其对称点 visited[nx][ny] true; visited[6-nx][6-ny] true; // 关键对称剪枝 dfs(nx, ny); // 回溯 visited[nx][ny] false; visited[6-nx][6-ny] false; } } } int main() { memset(visited, false, sizeof(visited)); // 标记中心点及其对称点自身 visited[3][3] true; // 从中心点开始搜索 dfs(3, 3); // 因为搜索树是对称的且我们每一步都标记了对称点 // 所以答案就是方案数。但注意从中心点向四个方向出发本质是旋转对称。 // 我们固定了搜索顺序但初始点(3,3)的对称点还是(3,3)所以不会重复。 // 最终需要将结果除以4吗不需要因为我们的visited标记和搜索规则已经保证了每种分割只被以一种“朝向”搜索一次。 // 更准确的做法是限制第一步的方向比如只向右走(3,3)-(4,3) ans 0; // 重置重新计算 memset(visited, false, sizeof(visited)); visited[3][3] true; visited[4][3] true; // 第一步向右 visited[2][3] true; // 标记对称点向左 dfs(4, 3); // 从(4,3)开始搜 cout ans * 4 endl; // 由于限制了第一步方向最终结果要乘以4 return 0; }实操心得这道题在赛场上的难点在于抽象建模。很多选手卡在如何表示“切割”上。一旦成功转化为“在格点图上搜索对称路径”的模型代码实现并不复杂。DFS函数本身很标准真正的灵魂在于visited[6-nx][6-ny] true;这一行对称标记。它同时完成了两项任务一是防止路径走到自身对称的位置导致自交二是保证了搜索出的路径其对称路径必然存在且不冲突。这比先搜索完整路径再检查对称性要高效无数倍。常见误区在6x6的“格子”上搜索而不是7x7的“格点”上搜索导致模型错误。忘记了去重将旋转或对称后相同的方案计为多种。对称标记时坐标计算错误(x,y)的对称点应是(6-x, 6-y)而不是(5-x, 5-y)那是针对6x6格子的索引。4. 赛题二磁砖样式状态压缩与哈希去重4.1 问题理解与搜索空间分析这道题可以看作是“铺瓷砖”问题的一个变种。题目描述了一个2行N列的网格现在有无限多的1x2占两格的磁砖可以横着铺覆盖同一行的两列也可以竖着铺覆盖两行同一列。要求铺满整个网格并且规定两种颜色假设为A和B的磁砖都不能有超过2x2的“同色四格”区域出现。即在任意一个2x2的子区域内不能所有格子都是同一种颜色。我们需要计算所有不同的铺满方案数。N的具体规模需要看题目印象中是10。即使N10搜索空间也巨大无比。因为每个格子最终的颜色由覆盖它的磁砖决定而磁砖的摆放方式很多。解题核心思路按列进行状态压缩DP或DFS回溯。由于瓷砖是1x2的它的摆放只影响当前列和下一列横铺或者当前列的两行竖铺。这提示我们可以一列一列地递推铺设。定义每一列的“状态”可以用一个数字表示该列两行格子的铺设情况和颜色。但这样状态会非常复杂因为要同时记录是否被覆盖以及颜色。一个更清晰的思路是DFS回溯 状态哈希去重。我们模拟整个铺设过程从左到右从上到下尝试放置瓷砖。放置时检查1. 是否超出边界2. 目标格子是否已被覆盖3. 放置后是否会产生非法的2x2同色区域。4.2 DFS回溯实现与关键优化我们用一个二维数组grid来表示网格初始为0表示未覆盖。用1表示颜色A2表示颜色B。DFS函数参数至少包含当前要放置的起点坐标(x, y)。放置策略每次找到第一个未覆盖的格子(x,y)尝试两种放置方式竖放如果x1 2且grid[x1][y]0则可以放置一块竖砖。随机或按顺序赋予它一个颜色1或2。横放如果y1 N且grid[x][y1]0则可以放置一块横砖。同样赋予颜色。合法性检查核心每次放置一块新砖后需要检查所有包含新砖格子的2x2区域。遍历所有以新砖格子为右下角、左上角、左下角、右上角的2x2区域确保区域在网格内检查该区域内四个格子是否都已覆盖且颜色相同。如果存在这样的区域则当前放置非法需要回溯。去重难点由于颜色只是抽象的“A”和“B”方案“AABB”和“BBAA”如果只是颜色互换在题目中可能被视为同一种如果题目说明颜色不同视为不同则不去重。通常这类题目中颜色是具体的如红蓝互换后视为不同方案。但2017年这道题需要仔细审题。一个更严峻的去重问题是网格是2行的旋转、对称后相同的方案如何避免重复计数题目通常要求计算“本质不同”的方案数。一个可靠的方法是当整个网格铺满后将其状态编码成一个唯一字符串或数字例如将每一行连起来存入一个unordered_set中进行去重。#include iostream #include cstring #include unordered_set using namespace std; int N; // 列数根据题目设定 int grid[2][12]; // 假设N最大为12 unordered_setstring schemes; // 用于去重 int ans 0; // 检查以(i,j)为左上角的2x2区域是否同色非法 bool check(int x, int y) { // 检查所有包含(x,y)的2x2区域 // 区域左上角可能为 (x-1, y-1), (x-1, y), (x, y-1), (x, y) // 但要确保区域在[0,1]行和[0, N-1]列内 for (int i max(0, x-1); i x i 1; i) { // i最多到0因为2行网格2x2区域的左上角行号只能是0 for (int j max(0, y-1); j y j N-1; j) { // j最多到N-2 // 现在(i,j)是可能的2x2区域左上角 if (grid[i][j] grid[i][j1] grid[i1][j] grid[i1][j1]) { if (grid[i][j] grid[i][j1] grid[i][j] grid[i1][j] grid[i][j] grid[i1][j1]) { return false; // 发现非法同色2x2 } } } } return true; } void dfs(int pos) { // 线性化位置pos x * N y if (pos 2 * N) { // 铺满了编码状态并去重 string key; for (int i 0; i 2; i) { for (int j 0; j N; j) { key char(0 grid[i][j]); } } if (schemes.find(key) schemes.end()) { schemes.insert(key); ans; } return; } int x pos / N; int y pos % N; // 如果当前格子已覆盖继续下一个 if (grid[x][y]) { dfs(pos 1); return; } // 尝试竖放 (颜色1) if (x 0 !grid[x1][y]) { // 竖放只能从第一行开始放 grid[x][y] grid[x1][y] 1; if (check(x, y) check(x1, y)) { dfs(pos 1); } grid[x][y] grid[x1][y] 0; // 回溯 } // 尝试竖放 (颜色2) if (x 0 !grid[x1][y]) { grid[x][y] grid[x1][y] 2; if (check(x, y) check(x1, y)) { dfs(pos 1); } grid[x][y] grid[x1][y] 0; } // 尝试横放 (颜色1) if (y N-1 !grid[x][y1]) { grid[x][y] grid[x][y1] 1; if (check(x, y) check(x, y1)) { dfs(pos 1); } grid[x][y] grid[x][y1] 0; } // 尝试横放 (颜色2) if (y N-1 !grid[x][y1]) { grid[x][y] grid[x][y1] 2; if (check(x, y) check(x, y1)) { dfs(pos 1); } grid[x][y] grid[x][y1] 0; } } int main() { cin N; // 实际比赛时N是给定的这里假设输入 memset(grid, 0, sizeof(grid)); dfs(0); cout ans endl; return 0; }踩坑记录这道题我初次实现时效率极低N10都跑不出来。主要瓶颈在于检查函数check调用过于频繁每次放置后都全盘扫描检查2x2区域是不现实的。优化后只检查与新放置格子相关的几个2x2区域最多4个。搜索顺序线性化位置(x,y)并按顺序找到第一个空位放置比双重循环更清晰也避免了重复搜索。去重编码最初我使用了将整个网格转为字符串的方法在N较大时字符串操作和哈希比较会成为瓶颈。对于状态压缩DP更好的方法是用一个长整型如long long的位运算来编码状态但本题由于有颜色1和2需要至少2比特表示一个格子状态编码会复杂一些。提示在竞赛中如果N不大比如8这种DFS哈希的方法在合理剪枝后是可行的。如果N更大比如15就必须用状态压缩DP了状态设计为dp[i][mask]其中mask编码了当前列两行的铺设情况和颜色然后递推下一列。但实现难度会高一个数量级。5. 赛题三对局匹配动态规划与分组思想5.1 问题转化与分组处理这道题是动态规划的经典应用也涉及了巧妙的数学思想。题目描述大致是有N个玩家每个玩家有一个实力积分值X。系统会将积分值相差恰好为K的玩家匹配到一起进行对局。现在的问题是如果一些玩家同时在线他们可能会被匹配到。我们希望从中挑选出一个最大的玩家子集使得这个子集中任意两名玩家的积分差都不等于K从而保证他们在线时永远不会被系统匹配到。输入玩家积分数组和差值K。输出最大子集的大小。暴力思路不可行N可以很大10^5级别枚举所有子集是2^N不可能。关键转化将玩家按积分对K取模的结果进行分组。 为什么因为如果两个玩家的积分差为K那么他们除以K的余数一定相同。例如K2积分3和5差2它们除以2的余数都是1。积分4和6差2余数都是0。也就是说差值为K的玩家必然存在于同一个“余数分组”内。不同余数分组之间的玩家积分差绝不可能是K因为积分差是K的倍数才会导致同余。因此问题从全局的一个大问题分解成了若干个独立的子问题在每个余数分组内选取一个最大的子集使得集合中任意两个数的差不为K。由于分组间独立最后将每个分组能选出的最大人数相加即可。5.2 分组内的动态规划模型现在问题简化为对于一个分组假设余数为r里面有一系列积分值r, rK, r2K, r3K, ...。我们要从中选出一个子集不能选择相邻的项因为选了rmK就不能选r(m1)K和r(m-1)K否则差为K。这变成了一个经典的打家劫舍或不相邻元素最大和问题的变种。只不过这里的“价值”不是积分值本身而是拥有该积分值的玩家数量。因为可能有多个玩家积分相同。假设我们将该分组内的积分值排序得到一个序列a[0], a[1], a[2], ...对应的玩家数量为cnt[0], cnt[1], cnt[2], ...。定义dp[i]为考虑前i个积分值时能选出的最大玩家数。 状态转移方程为如果不选第i个积分值dp[i] dp[i-1]如果选第i个积分值因为不能选第i-1个所以dp[i] dp[i-2] cnt[i](当i2时)对于i1的情况特殊处理dp[1] max(cnt[0], cnt[1])最终dp[last]就是这个分组内能选出的最大人数。特殊情况K0。当K0时分组条件积分差为0意味着所有积分相同的玩家都在一个组里并且他们之间都会发生匹配。那么在这个“组”里我们最多只能选择一种积分的玩家并且应该选择玩家数量最多的那种积分。因为如果选了两种不同积分此时差不为0因为K0时差为0才冲突他们之间不会冲突但题目要求是差为K的不能共存K0时就是积分相同的不能共存。所以对于K0问题简化为找出哪个积分值的人数最多答案就是这个人数。5.3 C代码实现与细节处理#include iostream #include vector #include map #include algorithm using namespace std; int main() { int N, K; cin N K; vectorint scores(N); mapint, int cnt_map; // 统计每个积分的人数 for (int i 0; i N; i) { cin scores[i]; cnt_map[scores[i]]; } if (K 0) { // 特殊情况K0只能选一种积分选人数最多的 int max_cnt 0; for (auto p : cnt_map) { max_cnt max(max_cnt, p.second); } cout max_cnt endl; return 0; } // 通用情况K 0 // 用于存储每个余数分组下的积分值 人数列表 mapint, vectorpairint, int groups; for (auto p : cnt_map) { int score p.first; int count p.second; int mod score % K; groups[mod].push_back({score, count}); } int total 0; // 处理每个余数分组 for (auto group : groups) { auto vec group.second; // vec里是(score, count) // 按积分值排序 sort(vec.begin(), vec.end()); int m vec.size(); if (m 0) continue; // 动态规划 vectorint dp(m, 0); dp[0] vec[0].second; // 只有第一个积分值可选 if (m 1) { // 对于前两个如果它们积分差为K则不能同时选 // 因为vec是按积分排序的且同余所以相邻项差一定是K的倍数。 // 由于同余且排序相邻的积分差就是K。 if (vec[1].first - vec[0].first K) { dp[1] max(vec[0].second, vec[1].second); } else { // 如果差不是K理论上在同余组内排序后相邻差就是K这里为了逻辑完整保留 dp[1] vec[0].second vec[1].second; } } for (int i 2; i m; i) { // 检查当前积分与上一个积分差是否为K if (vec[i].first - vec[i-1].first K) { // 不能同时选i和i-1 dp[i] max(dp[i-1], dp[i-2] vec[i].second); } else { // 可以同时选i和i-1 dp[i] dp[i-1] vec[i].second; } } total dp[m-1]; } cout total endl; return 0; }算法精讲这个解法的核心在于“分组”思想将原问题从O(N²)的关联中解脱出来变为多个O(M)的线性DP问题其中M是单个分组的长度。整体时间复杂度为O(N log N)主要用于排序和映射。一个极其重要的边界条件在上述DP实现中我们假设了同一个余数分组内积分值是等差数列公差为K。所以排序后相邻元素的积分差一定是K吗是的因为score % K r那么这些积分可以表示为r t*K(t为整数)。排序后相邻的t相差1所以积分差为K。因此if (vec[i].first - vec[i-1].first K)这个条件恒为真else分支永远不会执行。代码中可以简化直接使用“不能选相邻”的模型。我保留判断是为了让逻辑更清晰体现我们处理的是“差为K”这一条件。另一种更简洁的DP写法分组内// vec是已经按积分排序的积分人数列表相邻积分差恒为K int m vec.size(); if (m 0) continue; vectorint dp(m1, 0); dp[0] 0; // 前0个元素最大人数为0 dp[1] vec[0].second; // 前1个元素只能选第一个 for (int i 2; i m; i) { // 考虑前i个元素对应vec[0...i-1] // 不选第i个dp[i-1] // 选第i个dp[i-2] vec[i-1].second (因为不能选第i-1个) dp[i] max(dp[i-1], dp[i-2] vec[i-1].second); } total dp[m];这种写法下标处理更简单是处理“不相邻元素最大和”的标准DP写法。6. 常见陷阱与调试心得实录6.1 多组数据输入与初始化蓝桥杯的题目常常需要处理多组测试数据虽然国赛有时是单组。一个常见的坑是忘记在每组数据开始前清空全局变量和数据结构。例如在“磁砖样式”中grid数组、ans计数器、schemes集合必须在处理每个新的N前重置。在“对局匹配”中cnt_map和groups也需要清空。使用C时如果变量定义在main函数内则每次循环会自动重新创建如果是全局变量务必在循环体内手动clear()或memset。// 错误示范全局变量 unordered_setstring schemes; int ans; void solve() { // ... 使用 schemes 和 ans ... // 处理完一组数据后如果没有清空下一组数据会残留上一组的结果 } // 正确做法 void solve() { unordered_setstring schemes; // 定义在函数内自动管理 int ans 0; // ... 或者清空全局变量 ... // schemes.clear(); // ans 0; }6.2 整数溢出与数据类型选择这是算法竞赛中的经典陷阱。在“对局匹配”中虽然最后的人数不会超过N10^5但DP过程中dp[i]的值可能累加不过仍在int范围内。但在其他题目尤其是涉及排列组合、路径计数时结果可能非常大需要用到long long甚至高精度。例如有些题目结果需要对1e97取模这时不仅最终结果要用long long中间运算也可能需要先转为long long再取模防止乘法溢出。const int MOD 1e9 7; int a 1000000, b 1000000; // 错误乘法在int内溢出然后才转为long long取模 // int result (a * b) % MOD; // 正确先将乘数转为long long long long result (1LL * a * b) % MOD;6.3 搜索与DP中的状态设计误区以“方格分割”为例状态设计为visited[7][7]表示格点是否被访问。一个误区是只标记当前路径点而忘了同步标记对称点导致搜索出的路径不满足对称要求或者产生重复计数。在涉及对称性、旋转等去重问题时最好的办法是在生成状态的过程中就施加约束如第一步固定方向而不是生成所有状态后再进行复杂的去重判断。在“磁砖样式”的DFS中状态是当前的铺设网格。如果直接使用网格数组进行回溯每次递归调用都需要复制整个数组状态开销巨大。正确的做法是修改全局状态数组并在回溯时恢复。对于更复杂、网格更大的问题则需要用状态压缩一个整数表示一行或一列的状态来减少内存和时间消耗。6.4 调试技巧输出中间状态与小数据验证当你的程序结果不对或者运行超时时不要盲目盯着代码看。小数据验证自己设计几个小的、手算能知道答案的测试用例。比如“方格分割”可以试试2x2的网格答案应该是多少。用你的程序跑看结果是否匹配。输出中间状态在DFS或DP的关键步骤打印出当前的选择、状态值。例如在“磁砖样式”DFS中每放置一块砖可以打印出当前的grid看看铺设逻辑是否符合预期。使用断言assert在代码中你认为不变的条件处加入assert语句。例如在“对局匹配”分组时可以assert((vec[i].first - vec[i-1].first) % K 0)。这能帮你快速定位逻辑错误。对比暴力解对于小规模数据N8写一个最朴素的、正确性显而易见的暴力枚举程序可能很慢用它来验证你的优化算法DP/搜索的结果。这是验证算法正确性的黄金标准。6.5 赛场时间分配与代码策略回顾这三道题它们分别代表了三种不同的题型和难度。“方格分割”考的是建模和搜索剪枝“磁砖样式”是更复杂的搜索与去重“对局匹配”则是动态规划和问题转化。在真实的赛场上合理的策略是快速通读所有题目对每道题的难度、类型、可能耗时有个大致估计。先解决思路最清晰的。比如“对局匹配”一旦想到分组和不相邻DP代码实现相对直接调试也快。这种题目应该优先拿下。对于“方格分割”这类题如果短时间内无法抽象出正确的模型不要死磕。先写一个暴力搜索比如枚举所有分割线再检查获取部分分数N小的时候可能能过。标记一下等做完其他题再回来深入思考。“磁砖样式”属于代码实现细节多、容易出错的题。如果时间紧张优先保证正确性而不是追求最优解。先实现一个基础的DFS不带高效剪枝和去重确保逻辑正确能过小数据。如果还有时间再逐步加入哈希去重、更高效的检查等优化。最后保持好的编码习惯变量名清晰关键步骤写注释重复逻辑写成函数。这不仅能减少错误在调试时也能节省大量时间。毕竟在高度紧张的比赛环境中清晰可读的代码是你最可靠的盟友。