参加过第11届蓝桥杯B组省赛的老选手应该都有同感这届比赛原本定在4月份因为疫情硬是拖到了7月原本的线下笔试改成线上双机位监考。很多人的复习节奏完全被打乱刷题计划和心态都受影响。但拿题目本身来说B组的C/C卷质量非常高填空的推理量适中大题的梯度拉得比较开——前几道送分送得明白后几道动态规划能区分出真实力。这篇题解围绕2020年第十一届蓝桥杯软件类B组C/C省赛的全部题目展开包含5道填空题和5道编程题的完整思路、代码实现、复杂度分析以及对命题趋势的个人判断。不管你是准备打下一届省赛的新人还是想复盘这套经典卷子的老手这篇文章都值得耐心读完。我会把每道题从拆题、推导到编码的完整过程写清楚也会把实际做题时容易踩的坑单独列一节这些是在OJ题解里通常看不到的。1. 比赛全貌与命题趋势1.1 一场特殊时间的省赛先说一个很多人忽略的背景2020年是蓝桥杯第一次大规模采用线上比赛的方式。C/C B组在7月那场省赛留下的经验对后来几届都有影响。线上赛和线下赛最大的差异在环境。线下赛你坐在机房编译器版本统一机器配置统一旁边没有干扰实时提交就能看到成绩。线上赛不一样每个人本地的GCC版本可能不同C标准可能不同最要命的是有些同学的电脑上居然没有合适的IDE或者本地跑得好好的代码提交上去就是编译错误。那天确实有考生因为环境问题折腾掉半个多小时。如果你后面也要参加线上赛务必提前做两个准备第一本地装好Code::Blocks或者Dev-C能编译能运行第二在比赛前把环境变量、编译器路径都配好不要现场折腾。蓝桥杯的评测机和大部分竞赛一样使用GCCC代码尽量写标准C11的语法避免用到较新的特性免得编译器不认。还有开发环境千万不要用VS Code裸写不编译直接交那和扔硬币没区别。1.2 题型结构与分值分布2020年B组省赛卷面结构是题号类型分值建议用时A结果填空510分钟B结果填空515分钟C结果填空1015分钟D结果填空1020分钟E结果填空1525分钟F编程大题1525分钟G编程大题2030分钟H编程大题2030分钟I编程大题2535分钟J编程大题2540分钟总分150时间4小时和历年一致。从分数分布能看出填空5题加起来45分大题合计105分。很多人容易犯的错误是光盯着大题死磕填空随便填——实际上填空每一道都值得拿稳因为大题最后一题全对的人极少填空多拿10分排名能提升非常多。1.3 B组定位与备考价值蓝桥杯B组叫“重点本科组”C/C组每年报名人数最多竞争也最激烈。B组的难度介于A组的“偏竞赛”和C组的“偏入门”之间大多数题目只要学过数据结构和基础算法就能下手但高分需要更强的代码稳定性和临场推理能力。2020年的B组题目有两个特点值得注意。第一硬核算法比重下降模拟、枚举、日期处理占了很大比例这种风格对刚接触竞赛的同学非常友好。第二动态规划没有考经典的背包或LIS模板而是考了状态定义比较灵活的“装饰珠”这说明出题人更看重你能根据数据范围设计状态而不是背模板。搞懂这届题目对准备省一省二的目标来说价值极高。2. 填空小题推理与模拟的角力场2.1 “门牌制作”——直接枚举还是数学公式门牌制作这题很多人以为要推公式实际直接数就行。题目是从1到2020所有数字一共用多少个字符“2”。我当时的做法是写个循环从1遍历到2020每次把数字转成字符串数2的个数。这题本质就是考察你会不会写最基础的枚举没有任何陷阱。一个容易翻车的地方是忘掉2020本身有“2”不过2020里面没有2。另一个隐蔽问题是有些选手会把0到2020都算进去但题目是从1开始。多算一个0不会影响结果因为0里面没有2所以这个错误不致命。一定要养成写枚举题目时先确认区间端点的习惯。比如这题如果用for(int i 1; i 2020; i)确定边界没有问题但如果你随手写成了i 2020最后就漏掉了2020这个数虽然2020没2不影响但下一次如果是含2的边界数丢分就冤枉了。2.2 “既约分数”——数学化简与枚举边界既约分数这题要求有多少个既约分数分子分母都在1到2020之间且分子可以等于分母。也就是说这题统计的是所有满足gcd(i, j) 1的(i, j)有序对数量其中1 i 2020, 1 j 2020。很多人看到“既约分数”就去推欧拉函数确实可以优化但这题的规模用双重循环加gcd足够。2020乘以2020是4080400个组合每对求一次gcd复杂度是O(n²logn)跑下来基本秒出。写代码时需要注意一点题目允许分子分母相等所以对角线上的元素也要统计当i和j相等时唯一满足条件的是1/1因为其它数除以自身都不是既约分数。实现的时候不要加if(i ! j)的限制。这题要能快速意识到gcd函数可以直接调用。比赛环境下的GCC自带algorithm库的__gcd也有C17的std::gcd直接用即可。但建议在本地写一个自己的gcd函数避免编译器标准不统一。如果每题都自己实现gcd还能顺手避免一些无谓的环境兼容问题。2.3 “蛇形填数”——矩阵规律还是模拟填表蛇形填数的题面通常描述一种蛇形排列方式问第20行第20列位置上的数是多少。这类题有两种做法一是模拟二是找规律。模拟的写法是维护一个方向变量碰到边界就转向交替改变行和列的变化方向。数组开一个足够大的二维矩阵初始化为0从左上角开始依次填入1、2、3……直到填满需要的大小然后直接输出a[20][20]。但这类题更推荐找规律至少要知道对角线上的数有规律可循。蛇形填数中第n行第n列的数通常是某一串平方数。不过这届这道题其实可以用简单归纳法手动沿两条对角线多算几个点找到主对角线上的递推关系。由于篇幅原因这里不展开所有中间数值但强烈建议考场上先用小规模模拟打印出前几项再归纳通项公式这样省时间且不容易错。我在考场上用的是模拟因为写的代码一次跑通不用花心思证明规律。模拟代码本身很简单只需要注意二维数组别开小了。开一个105乘以105的矩阵填到4000左右就能覆盖目标位置。填完以后检查输出是否正确如果发现数字不对优先检查转向条件。2.4 “跑步锻炼”——日期遍历的跨年陷阱跑步锻炼是这届填空里比较容易失分的一道。题目条件大致是某人在某年某月某日开始每天跑固定距离如果当天是月初或者周一额外多跑一段。问从开始日到某个截止日总共跑了多少。这种题的核心是写日期遍历。很多新手会手动列每个月多少天然后每个月从1号循环到月底。实际上最稳妥的写法是三个数组年天数、每月天数、以及一个判断闰年的函数。循环从起始年到截止年每个月的天数根据闰年动态更新。日期题有几处经典陷阱开始日期当天算不算题面没特别说明的话应该算如果有额外条件要看清楚。截止日期当天算不算同样要确认。跨年时判断闰年不要写错闰年是(year % 4 0 year % 100 ! 0) || year % 400 0不要用简化的year % 4 0了事。星期几的推进比较简单每天加1对7取模但起始日的星期几一定要算准。我一般会用已知的今天星期几往回推或者干脆用一个基准日期验证。考场上写日期处理题我的建议是不要图省事用ctime库函数。竞赛环境下的时间函数在不同操作系统上行为不完全一致而且调试输出很麻烦。老老实实写一个日期累加的循环几行代码的事换来的是一份确定无误的结果。2.5 “七段码”——组合枚举与连通性判断七段码是2020年B组填空里综合性最强的一道。说法是数码管有7个发光段编号a到g选出若干段要求选中的段连成一个整体问有多少种不同的选法。注意不需要所有7段全亮也没有要求必须贴着边。这题的思路是把7个段看成图的7个顶点按照相邻关系连边然后枚举所有非空子集判断每个子集诱导出的子图是否连通。实现上有几种途径。最简单的是二进制枚举用一个0到127的整数表示选了哪几段每一位对应一段。枚举到某个mask时取出所有选中段的编号通过并查集判断连通性或者用DFS从某个选中段出发看能否访问完所有选中段。我推荐DFS判断先根据mask建立邻接表只包含当前选中的点然后从第一个选中的点开始DFS记录访问个数如果访问个数等于选中个数说明连通答案加1。要注意第一段初始化为选中状态时计数要从1开始别从0。这题能拿分的关键是图建得对不对。七段码的相邻关系可以手画图来确认上面横的两段与左右竖的两段相连中间横的与四根竖的相连下面横的同理。画一个数码管的草图把每段的相邻段列出来再建边错误率可以降到零。3. 编程大题从算法模板到现场拆题3.1 回文日期日期模拟与回文判断的组合回文日期是编程大题的第一题难度不高但有坑。题面大概是给定一个8位数字日期找下一个回文日期以及下一个既是回文又是ABABBABA型的日期。这题放在F题的位置本意是送分可每年都有不少人因为日期合法性判断写崩。常规做法是先把给定的8位数字解析成年月日然后从下一天开始枚举日期。每一天把日期转成8位字符串判断是否回文判断是否满足ABABBABA。找到第一个回文就记录找到第一个ABABBABA就记录找到两个就退出。实现时最麻烦的是日期合法性。因为要按“日”递增每加一天都可能要进位到月再进位到年。比较稳健的写法是写一个函数bool isValid(int y, int m, int d)再用数组存平年每个月的天数闰年单独处理。每次d后如果超过当月天数则d 1, m如果m 12则m 1, y。判断回文和ABABBABA都可以用字符串处理但用整数更快把8位数拆成8个数字首尾比较一次完成回文判断ABABBABA的判断只需要看第1和第2位是否相同且第3和第4位是否相同且第1位和第3位不同但为了稳妥可以分别验证s[0]s[2] s[1]s[3] s[0]!s[1]这类关系。这题最容易丢分的地方是给定的起始日期本身可能就是一个回文日期这时候next不能从当天开始必须从下一天开始。题目通常说的是“下一个”如果从当天算某些用例就会错。我开始就因为没注意这个细节样例过了但提交时心里没底后来仔细读题发现确实要跳过当天。代码整体控制在100行以内复杂度是O(n)n是枚举的天数最多也没多少天因为回文日期在100年内的间隔不会太大这个做法是足够稳妥的。3.2 字串排序数据结构与排序的结合字串排序这道题给的是一个字符串要求将一个子串排序后的结果并且有多次查询每次给出l和r输出子串排序后的内容。题目描述可能有细节差异但核心思想一致因为字母只有26种所以可以用桶计数处理区间内每种字母的数量然后按字母顺序输出对应个数的字符。如果对每个查询都截取子串然后排序复杂度是O(n²logn)在字符串长度和查询次数都达到十万级别时必然超时。这时候要用前缀和优化开一个二维前缀数组cnt[26][n1]cnt[c][i]表示前i个字符中字母c出现的次数。查询一个区间[l, r]时cnt[c][r] - cnt[c][l-1]就是该区间内字母c的个数然后从a到z依次输出这若干种字母。这种“字符频次前缀和”的思路本质上就是把排序问题转化成了计数问题这也是很多字符串相关的区间查询题的标准做法。对这个题来说26个字母的常数特别小所以空间上26乘以1e5完全没问题。写代码时注意下标从0开始还是从1开始建议统一用1-based的下标存字符串这样前缀和写起来更直观。查询时要把输入的两个下标转换成1-based之后再相减。这题很简单但很容易因为下标混乱出现边界问题。如果题目改成要求输出排序后的字典序最小的排列这种桶计数的思路同样成立本质上我们都是要从左到右构造字符序列。在准备蓝桥杯的时候这种“以空间换时间”的做法值得熟练掌握。3.3 成绩统计浮点精度与边界处理成绩统计这题要求统计及格率和优秀率输入是n个成绩及格线为60分优秀线为85分输出两个百分比。百分比的精度要求一般保留一位小数并且要四舍五入。最简单的写法是统计及格人数和优秀人数分别乘以100除以总人数然后用printf(%.1f%%, x)输出。但这里面有一个非常经典的坑printf的%.1f用的是四舍五入而有些场景下标准要求的是“四舍五入保留一位小数”如果直接用整数除法再转浮点乘100可能会得到类似99.949999这样的值。更稳妥的写法有两种先算浮点数p cnt * 100.0 / n再用printf(%.1f%%, p 1e-9)修正浮点误差。或者把比例乘以10再加5除以10得到四舍五入后的整数手动拼出小数输出。实际考试中蓝桥杯的评测对浮点误差通常比较宽容printf直接输出一般能过。但既然是实战应该养成加一个微小修正量的习惯。用printf(%.1f%%, ans 1e-8)几乎不会出错。这类题少有人拿不到分但拿满分的关键在于输出格式。百分比符号要记得转义输出C语言里printf(%%)输出一个%很多人第一次写会漏掉这个符号。还有如果题目要求“四舍五入到整数百分比”那就不能用%.1f必须用printf(%.0f%%, ...)。考试时多看一眼题干的输出要求比多写十行代码都管用。3.4 平面切分几何计数与动态更新平面切分这题是比较有意思的一道几何题。题面大概是有n条直线每条直线可以用y kx b表示也可能出现k相同的情况。问这些直线依次加入平面后总共能切分出多少个区域。这题的突破点是一条新加入的直线能增加的区域数等于它与已有直线的不同交点个数加1。如果新直线与已有直线重合则不增加区域如果平行也不增加交点。因此核心计算变成对每条新直线遍历所有已有的直线计算它们的交点坐标用setpairlong double, long double去重然后答案累加s.size() 1。这题的k和b可能都是整数交点的分母可能会是0要提前判断平行和重合的情况。实际写代码的时候要注意几个问题。第一k相等且b相等时新直线和已有直线重合不增加新的区域并且后续也不应产生贡献。第二如果直接用double存交点坐标去重可能会因为浮点误差导致同一交点被误判为两个不同的点。比较稳的方案是用long double存或者用有理数的方式存把x表示为(b2-b1)/(k1-k2)但为了避免浮点误差可以用分数形式的pair存约分后的分子分母。但这会比较繁琐针对蓝桥杯的数据范围long double加上set足够通过。比赛时我还发现一个问题这题的n上限是1000O(n²)的复杂度完全可行每加入一条直线遍历之前的1000条最多100万次计算秒过。不需要任何高级几何库一个自定义的cmp结构体或者直接用pairlong long, long long就能处理。平面切分还有一个变种是圆或者线段核心思想都是“新增区域数等于新增交点数加1”掌握这个通用结论后遇到类似的几何题都能快速入手。3.5 装饰珠从数据范围反推动态规划装饰珠是整套卷子的压轴题之一也是区分度最高的一道。题面大概是你有很多个装饰珠每个珠子有等级和提供的价值你需要给装备的各个槽位放珠子但槽位有等级限制数量也有限制不同等级的珠槽可以放的珠子等级有规则求总价值的最大值。我印象里这题比较经典的描述是“有m个装备每个装备有若干个装饰孔每个孔有一个等级上限只能在满足等级条件的珠子里挑一个嵌入”最终求总价值最大。这题的关键是要抽象成“有多个盒子每个盒子有容量限制和等级限制有若干个物品每个物品占用1个容量且物品有自己的等级和价值求最大总价值”这一模型。由于每个孔只能放一颗珠子所以本质上是个分组选择和容量分配的组合问题。比较稳妥的做法是动态规划。可以把等级看成第一维价值看成第二维。由于珠子的数量不多——具体数量我记得是每个等级最多有若干种总数量级大概在三四百——所以可以开一个多维数组记录不同等级下可用的珠子数量然后对每个槽位做“选或不选”的背包DP。具体状态设计建议是dp[i][j]表示处理完前i个“槽组”后一共使用了j个珠子的最大价值。每个槽组内部有等级限制。更直接的做法是把所有背包容量看成“孔的数量”每个珠子最多被使用一次等级越高的珠子不一定越好需要权衡。不少人在考场上看到这题直接放弃。但实际上如果n比较小一个暴力搜索加剪枝也能拿到不少分。蓝桥杯的评测机制是部分得分哪怕只过了第一个测试点也能拿20%的分数。所以我的建议是压轴题能做正解当然好如果五分钟内没有思路先把前面几题的分拿稳最后30分钟再回来暴力。写DP时特别注意初始化和状态转移的方向外层循环应该是各等级珠子的处理顺序内层是可用孔数。如果状态转移用一维要从后往前刷否则会重复选择同一种珠子。这个错误我第做这类题时踩过一维背包重复选择的坑太典型了一定要养成先写二维、确认无误后再优化成一维的习惯。4. 做题顺序与时间分配实战建议4.1 按难度梯度推进的思路蓝桥杯省赛的题不完全是按难度从低到高排列的有时候第8题比第9题难第10题反而是模拟加搜索。所以不建议从头到尾闷头做完。我自己常用的策略是前5道填空题最多花70分钟。每道题控制在10到15分钟。如果一道填空超过15分钟还没有思路先跳过去把后面的编程题做完再回来。第6题、第7题和第8题如果难度正常每道花30分钟以内。这三题要尽量拿满分因为他们通常是送分或者难度较低的大题。第9题、第10题先读题5分钟判断是你能做的类型还是完全陌生的算法。如果有思路优先做第9题第10题如果是要写复杂的DP或搜索留到最后。这套策略的核心是不要因为某个难题卡住而影响简单题的得分。蓝桥杯省一通常不需要满分能把简单题全做对中等题做出一半排名已经非常靠前。我当时做完填空用了65分钟第6题用了20分钟第7题25分钟第8题35分钟留了80分钟给最后两题最后一题虽然没有全对但通过暴力拿到了部分分最终成绩相当理想。4.2 不容易得分的代码书写习惯有几种代码习惯在紧张的比赛环境下会害了你。第一变量名不要用太短的。比如int tmp用多了回头自己都分不清是哪个tmp。可以用cur、ans、cnt、tot等语义化一点的命名。代码不是写给评委看的是写给自己在30分钟后再看的。第二不要过度依赖调试输出。考试的时候可以在本地用printf加调试但提交前要记得注释掉或者删掉。很多人提交的代码里留着调试输出虽然通常不会影响结果但万一调试输出写到了标准输出流里面就会导致答案错误。第三养成读入后用scanf/cin关闭流同步的习惯。如果你用C的cin一定在main开头写ios::sync_with_stdio(false); cin.tie(0);。很多人的算法明明是对的就因为输入数据量大cin太慢导致超时这种丢分最不值得。第四数组开大一点。动态规划类的题目数组下标经常从1开始数组长度加上5或者10防止越界。C的越界不一定会RE有时候会静默改写出错。不要抱有侥幸心理每个数组都略微开大一点。4.3 对“部分得分”的理解蓝桥杯的题目不是只有AC和WA两种状态绝大部分测试点都是按点给分的。这和其他ACM类比赛不太一样既然按点给分就一定要争取部分分。比如第10题装饰珠如果时间紧张可以直接对第一组数据写暴力枚举或者写一个不剪枝的搜索至少拿10分到15分。第9题平面切分如果推导不出公式也可以直接模拟所有交点哪怕存浮点数有精度问题小数据也能对好几个点。部分得分思维的本质是在有限时间里把分数最大化。不要因为觉得“这题我写不完美”就彻底放弃。哪怕只是把题目读懂写一个能处理小数据的暴力也比交白卷好得多。5. 高频踩坑记录与自查清单5.1 日期题常见失误这一套题里日期相关的出现了两次跑步锻炼和回文日期“日期”几乎是每年蓝桥杯的常客。最常见的失误有四种忘记考虑闰年2月29日。很多人写每月天数数组时直接把2月天数为28闰年没加1。忘记考虑开始日期当天。题目如果问“从这天开始”多数情况要包含当天但有的题目会明确排除。要养成熟练使用isValid函数单独判断当天是否在范围内的习惯。星期几计算算错。用某个已知日期推导起始星期时需要非常小心最好写一个基准函数校验。日期格式化输出问题比如输出月份和日期时需要补前导零。回文日期这类题里全程用整数日期输出时才需要格式化提前做好除以10和取模的转换。自查方法也比较简单随便挑几个已知日期比如2020年1月1日是星期三之类的验证点跑一遍代码算出来对不对就能知道自己日期模板是否可靠。5.2 枚举题的越界与终止条件填空题中多道题都涉及枚举门牌制作、既约分数、蛇形填数。枚举时最常见的错误是终止条件偏移一位或者循环变量没有考虑等于边界的情况。比如既约分数那道题i和j都必须能取到2020。很多人写for(i 1; i 2020; i)就把边界漏了。这种错误的隐蔽之处在于如果答案只是少了边界上的几个分数样例可能依然正确只有对比标准答案时才会发现。另一个问题是求最大公约数时如果用while(b) { int t a % b; a b; b t; }要注意初始a、b的正负。蓝桥杯的数据一般保证正数但自己测试时可以多写几个边界值验证。5.3 动态规划的状态定义与初始化动态规划是难题里最容易暴露问题的地方有几个共通的坑。第一状态定义直接决定复杂度。定义得太粗会漏状态定义得太细会导致复杂度爆炸。比如装饰珠如果只按“使用珠子数量”定义状态不考虑等级限制转移就错了。建议先在草稿纸上写出状态转移方程再对照题目的数据范围算一遍复杂度确认可行后再写代码。第二初始化非常重要。很多DP的初始值应该是0或者负无穷写错一个数会跑遍所有结果都不对。背包类DP通常要求价值最大化初始化为0即可但如果要求刚好凑满某个容量初始就要用负无穷来区分“不可达状态”。第三循环顺序。二维的dp[i][j]依赖dp[i-1][j]和dp[i][j-cost]等状态的时候优化成一维要注意是从后往前还是从前往后。常见的错误是把自己写混乱导致同一个珠子被选两次。5.4 我认为最值得记住的经验整场比赛下来我特别有感触的一点是蓝桥杯检验的往往不是你会不会某个偏难怪算法而是你能不能把基础题稳定地写对。这套题里的日期模拟、桶计数前缀和、并查集连通判断、基于交点的几何计数全是普通的数据结构和基础算法但组合起来就能拉开很大的分差。最后再说一个考场上意外有用的细节如果题目给定了多组测试数据不要假设它们之间没有关联。有些题第一组样例和后面几组样例的约束条件可能不同。尽量把代码写通用不要针对某组数据特判。另外如果提前做完了不要闲着多准备几个边界数据自己测一测尤其是n1、n边界值、日期跨年这些情况。下次再遇到类似的比赛别慌按题目类型拆开打每道题该拿的分都拿了成绩自然不会差。