2023 年第十四届蓝桥杯 C／C++ B组省赛题解 - 知乎

　　这是一篇 2023 年第十四届蓝桥杯省赛 C/C++ B 组题解。本人蒟蒻 ACMer，最近发现时隔两周的蓝桥杯省赛还没有一篇题解，火速补了题来写份题解。最后再顺便写一下心得吧。

　　虽然蓝桥杯省赛结果差不多该出了，但这里给急急急的网友们挂个民间数据链接：2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题 - 题库 - C语言网 (dotcpp.com)

　　这题方法应该很多，没有和别人讨论想法。我的解法思路是：先 函数生成所有这一年的合法日期，然后枚举所有可以从数据中拿到的八位日期，检查它是否在合法日期的集合中。

　　这里枚举到四位，即年份的时候要判断一下，不然可能数据太多要跑很久。

　　注意要去重！不知道有多少冤大头痛失这 分。（原题里特意加粗了不重复）

　　题目提供了一个表达式： 其中， 表示一个 字符串， 表示符号 在字符串中的占比。那么简单化简一下这个式子，我们用 表示 中 的个数，用 表示 中 的个数， 表示 的长度，因为是 字符串，有 。 题目告诉你 以及 的值，求 和 。

　　首先你要知道计算机一秒大概可以完成 次简单运算（这个运算挺简单了吧），那么很简单我们枚举 去拟合 即可。

　　题意是有一种商品，花 元钱可以买 个该商品。给你多组这样的 和 ，请你确认这个商品的价格区间。

　　如果给你一对 和 ，那么它确定的价格区间就是 ，然后取所有区间的并即可。

　　注意不是 ，尽管我上面提供的民间数据可以过这个错误，这里提供错误数据 ，正确价格区间为 。我一个队友 S 这了，我赛时也考虑了这个问题。

　　这道题还可以二分去找合法的价格区间，我另一个队友是这么做的，虽然有点蠢，但至少避免了推错式子，不作扩展。为什么有人叫我前面将的这种做法为数论分块，我不是很理解，这更像一道 。

　　注意看数据范围是 ，自信贪心的可以好好反思一下自己了，如果真能写评论区留言。

　　最基本的爆搜，不需要剪枝，时间复杂度 ，看代码注释。

　　也可以使用 ，时间复杂度 。如果数据是 那这就是正解了。

　　这是一道普通的 ，时间复杂度可以是 或者 ，我这里写的是 的。

　　数字接龙的条件是前某个数字的最后一位与这个数字的第一位相同，那么我们使用 表示到第 位时，前 位中的接龙序列以数字 结尾的最大长度，设第 个数字的首位为 ，末位为 ，则状态转移方程为： 考虑到前 位的数据不会再次被使用，并且状态转移中有大量的拷贝，这里做了内存优化，同时时间也下降了十倍。（已经够过题了，这是次要的）

　　在和队友交流过程中，大概认为这道题是思维量最大的一道题了，因为你会发现再往后面的题都比较板子。

　　题目将地图分为 和 ，其中陆地又被区分为 和 ，题目对于 的定义是被任意的 所围成的环的内部，然后求 的数量。

　　但是如果你像题意那样理解 实现就比较复杂了，转换为 是其周围的 有任何一块是 的 ，所谓 是可以连通到地图外的 。如此理解。我们只要预处理出所有 ，再处理 即可。这里用广搜写的。

　　时间复杂度 ，如果写蠢了 也可以过，没有卡时间。

　　计数有多少个子串满足以 开头、 结尾、长度大于等于 。

　　双指针二分，一个指针遍历，一个指针二分。题目要求以 开头、以 结尾，那么就用两个数组分别记录 和 出现的位置，一个指针遍历 位置序列，一个指针在 位置序列二分大于等于当前长度加 后第一个 出现的位置，从这个位置往后都是有效贡献。时间复杂度 。

　　同样是双指针，类似的记录两个序列： 位置序列， 位置序列。慢指针遍历 位置序列，快指针在 与 的距离不足 时向后移动，指到足够或越界，记录每次贡献。时间复杂度 。

　　这道题虽然数据是 但是二分还是跑的过的，因为二分的常数非常的优秀，这里是我赛时首先想到的第一种解法。

　　使用优先队列维护找到最小删除数，并且使用类似链表的结构记录数的前驱与后继。

　　如果想到这些，那么问题就变成了一个流程的模拟了，我在代码里多打了一些注释。

　　我不知道命题组怎么想的 的数据给了 的时间，后面的 题 的数据给了 的时间。如果使用 优先队列，由于常数问题我测试了民间数据 了，听了别人的写法大多都是使用优先队列的。实测手写 或 不会 ，这样卡常？莫非是有更优秀的解法？评论区留言。（下面的代码使用手写堆的）

　　不管怎么看后面 题的常数不会与 题有这么大的差距。

　　板子题，作用是找到最近公共祖先。如果不会 ，建议去学，学完这道题自然就会了。

　　先求出不删除节点的总路程。要求去除一个节点后的最短距离只需要置换掉相邻两个最短路为一个新连接的最短路，左右边界特殊处理即可。

　　板子题，主要是一种思想，没学过赛时可能也能想到。大多数 的板子题都很有难度，因为单独的 很难做一件事情，这道题出出来很好，很适合作为板子题，难度较低。

　　也要 雾...

　　给定一棵树，给定 条最短路，现在让你砍断一条边从而砍断所有这 条最短路。

　　我们只需记录每条边经过了多少次，如果有一条边经过了 次，那么砍断它即可。否则输出 。

　　如何在允许的时间内计数所有边经过多少次我们只需要存储差分数，最后对全树求和即可。对于边 ， 。可以发现最后对全树求和就是我们要的边数。时间复杂度 。

　　OK！结束。

　　个人不是很喜欢这场蓝桥杯，最后两道题考得两个 ，在这里分配了 分的分值是否有失偏颇？最后两大题占据了 的分值却是两道板子题。近几年蓝桥杯的热度暴涨，出的题也是每年都不一样，从暴力杯到 杯一定程度考察考生的思维能力，有些题还是挺有思维量的，今年的 杯不作评价。

　　题还是比较传统的并且也没有什么问题， 题给的数据范围以及对应的时间有些问题，我当时赛时用的 写被卡掉可以理解，但是 的数据以及 的时间数据够强可以卡掉优先队列。相反 题 的数据给 的时间完全没有必要。

　　我是第一次打蓝桥杯，也是问题连连。 题没看到 ； 题那个自信贪心的就是我； 题 部分点被卡常（赛时疑似按了两下 编译错误）； 题 默好了默对了最后忘记调用了，神奇的过了样例； 题没写来不及。

　　文章心得拖延了两天，我写完这篇文章的时候刚好出结果了，勉强还是拿到了 。