蓝桥杯 2026 省赛 B 组复盘:考前状态、考场决策与赛后重做
前言
省赛落幕,我拿到了省一的成绩,校内第 2,北京市第 25。
从结果上看,这似乎是一个“好成绩”。但结合我的个人体验,我仍然觉得自己本可以做得更好,或者说,我并没有发挥出自己的正常水平。
因此,这篇文章并不是一篇获奖感言,而是围绕考前状态、考场决策、赛后重做,以及这次比赛所暴露出的问题,做一次完整的复盘。
考前状态与准备
考前状态
这次省赛前,我的状态并不好。
一方面是长期的焦虑和睡眠问题。赛前很长一段时间里,我对自己的水平、学校平台、未来发展以及比赛结果都有强烈的焦虑感。临近比赛时,这种焦虑并没有明显缓解,反而让我在复习和休息之间很难找到稳定节奏。
另一方面,我的身体状态也很不理想。考前一晚我依然没有休息好,彻夜失眠,整个人并不是在一个精力充足、心态平稳的状态下走进考场的。
这也是我赛后最难受的地方之一:我并不是完全不会这些题,而是在考场上没有进入正常的思考状态。有些题我能摸到方向,但没有足够稳定的心态和足够冷静的头脑支撑我推演下去;有些题我选择了止损,写了骗分的做法;还有些题则是在赛后重做时才发现,自己其实并不是没有能力理解,只是考场上没有完成最后一步转化。
因此,这次复盘并不只是为了重新写一遍题解,也是为了更清楚地看见:哪些问题来自知识短板,哪些问题来自临场建模,哪些问题又来自考场状态和稳定性。
赛前准备
赛前一周,我才开始进行系统备赛。我主要围绕两条线做准备:一是完整真题模拟,二是专题复习。
真题模拟方面,我完整做了三套省赛真题,同时穿插补了一些零散真题,用来熟悉蓝桥杯的题型分布、填空题节奏和后半部分大题的难度梯度。
专题复习方面,我重点过了一些自己认为省赛中可能会用到的内容,包括搜索(BFS / DFS)、字符串哈希、快速幂、进制转换、gcd / lcm、STL、Dijkstra、LCA、拓扑排序、基础数学函数,以及 DP 中的背包、树形 DP 和自定义状态设计等内容。
从赛后结果来看,这些内容绝大多数都没有命中考题。但这些复习并不是完全没有意义,它们至少让我在基础代码、常见模型和比赛节奏上更稳定了一些。
真正暴露出来的问题,更多集中在数学推导以及考场压力下的细节处理上。这些问题也能体现在后文的逐题复盘中。
逐题复盘
下面对比赛中的 8 道题进行逐题复盘。
T1:青春常数
点击展开/折叠 T1题面
题意简述
本题给定整数:
要求统计有多少种拆分方式,使得:
并且满足:
本质上,这是一道整数拆分计数题。题面中的年份拼接容易带来一定干扰,但最终并不涉及字符串拆分或特殊构造。
考场思路
考场上我一开始被题面叙述干扰了一下,以为“拆分”可能和字符串结构有关。但重新读题后,我意识到它应该只是把这个整数拆成两个非负整数之和,并要求前一个数严格小于后一个数。
因此只需要统计满足条件的 的取值个数。由于 ,条件 等价于:
也就是:
因为 是奇数,所以合法的 为:
一共有:
种。
正解思路
根据:
令 ,可得:
进一步转化为:
所以合法的 个数为:
代入:
得到答案:
即:
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题本身并不难,真正值得记录的是考场上的第一反应。作为第一道填空题,我原本预期它应该是比较直接的送分题,但题面刚读完时,我却被“拆分”和年份拼接这些表述卡了一下,一度以为它可能和字符串结构有关。
这种开局被第一题轻微卡住的感觉,其实会对心态造成影响。尤其是在考前状态本来就不稳定的情况下,第一题如果不能立刻确认思路,很容易产生一种“是不是今天又不在状态”的自我怀疑。
好在我后面及时把题面抽象成了最朴素的数学条件:,且 。转化之后,这题就只是统计满足 的非负整数 的个数。
第一道题,稳住心态最重要。
T2:双碳战略
点击展开/折叠 T2题面
题意简述
有 盏路灯,初始全部为亮。每一盏路灯只有亮和灭两种状态,可以用 和 表示。
第奇数次操作时,可以选择一盏路灯,并翻转它及其右侧所有路灯,也就是翻转一个后缀。
第偶数次操作时,可以选择一盏路灯,并翻转它及其左侧所有路灯,也就是翻转一个前缀。
对每一种可能的最终状态,定义从初始全亮状态变成该状态所需的最少操作次数。题目要求统计所有 种状态的最少操作次数之和,并对 取模。
考场思路
这题我在考场上大概看了十分钟,但始终没有找到有效的切入点。
题面里的操作规则并不难理解,但难点在于它要求统计所有状态的最少操作次数之和。状态数量是 ,显然不可能逐个考虑,同时我也没想出来暴力解法。
在没有形成有效模型的情况下,我选择直接跳过,并且后续没有再回看。
正解思路
这题的关键是不要直接看每一盏灯本身,而是看相邻两盏灯之间的关系,也就是“插板”。
对于一个最终状态:
其中 。
我们先只考虑相邻两盏灯之间是否不同。对于每一对相邻位置:
如果它们相同,说明这里没有分界;如果它们不同,说明这里有一个分界。可以把这种分界理解成一个“插板”。
因此,长度为 的灯序列,一共有 个内部插板位。
一次翻转后缀时,后缀内部的相邻关系不会改变,因为这一整段都同时取反。真正改变的只有后缀起点左侧的那个边界。
同理,一次翻转前缀时,前缀内部的相邻关系也不会改变,真正改变的只有前缀终点右侧的那个边界。
所以,除了整体翻转之外,每一次操作本质上都可以看成是在改变一个内部插板位。
接下来先只看这 个内部插板位。
对于所有 种最终状态,任意一个固定的内部插板位,有一半状态中它为 ,另一半状态中它为 。也就是说,每个插板位在所有状态中会贡献:
次操作。
内部插板位一共有 个,所以这部分总贡献为:
但是,只看内部插板还不够。
因为相同的内部插板结构,对应两种互为整体取反的原序列。
例如 时,如果内部插板为:
那么对应的原序列可以是:
也可以是:
这两个序列的相邻变化完全相同,但整体亮暗方向相反。
对于每一种固定的内部插板结构,按这些插板去操作,只能到达两种互补状态中的一种;另一种还需要额外进行一次整体翻转。
因此,对于每一种固定的内部插板结构,都会额外贡献 次操作。
内部插板结构一共有:
种,所以整体翻转带来的额外贡献为:
于是总答案为:
合并得:
本题中:
所以答案为:
用快速幂计算即可。
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题最值得记录的不是我为什么没做出来,而是我在考场上没有继续和它死磕。
作为一道填空题,它的分值有限;而从题目结构和赛后难度来看,它明显不是简单枚举或几步模拟能够解决的问题。我后来在洛谷上看到这题的难度标记是蓝题,这也说明它本身就不是一道适合在考场上长时间硬啃的低成本题。
考场上我看了约十分钟,仍然没有建立出有效模型。在这种情况下,继续投入时间大概率只会拖累后面的题目。直接跳过,并且不再回看,是当时更接近局部最优的选择。
赛后补题时再去理解它的内部插板统计和整体翻转补偿,是复盘应该做的事;但在考场上,比赛目标不是证明自己每道题都能想出来,而是在有限时间内尽可能多地拿分。
这题给我的经验不是某个具体算法模板,而是考场决策本身:有些题难、分值少、入口不明显,就应该果断止损。
T3:循环右移
点击展开/折叠 T3题面
题意简述
给定 ,要求统计满足条件的数组数量。
数组 的长度为 ,并且每个元素都需要满足:
题目要求这个数组对任意一个连续子数组进行一次循环右移后,整个数组仍然保持不变。
需要求满足条件的数组数量。
考场思路
这题我在考场上其实没有做严格证明。
当时主要是通过样例和直觉判断:如果一个数组满足题目要求,那么它大概率只能是所有元素都相等的数组。因为只要数组里存在不同的元素,某次对连续子数组的循环右移就很可能改变原数组。
基于这个判断,我直接认为合法数组只能形如:
其中:
所以答案就是可以选择的 的数量:
如果 ,则没有合法取值,答案为 。
因此最终写成:
正解思路
这题的严格证明其实很短,只需要考虑长度为 的连续子数组。
对于任意相邻两个元素:
它们本身就是一个长度为 的连续子数组。
如果对这个子数组进行一次循环右移,那么:
会变成:
题目要求操作之后整个数组仍然保持不变,所以这两个位置上的元素不能发生变化。因此必须有:
这个结论对所有相邻位置都成立,所以:
也就是说,满足条件的数组只能是全体元素都相等的数组。
于是数组只能写成:
其中:
所以合法数组数量为:
如果 ,则答案为:
统一写成:
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题考场上我是靠样例和直觉得出了正确结论并写出了正解,但严格来说,当时并没有完成证明。赛后回头看,真正的证明非常短:题目虽然要求任意连续子数组都满足条件,但只需要考虑长度为 的连续子数组,就能推出所有相邻元素必须相等。
这题给我的经验是,直觉可以帮助快速找到方向,但如果时间允许,还是应该尽量把关键结论补成一个可验证的证明。尤其是这种“任意子数组 / 任意区间”类条件,往往不一定要从一般情况入手,最小的关键结构可能已经足够强。
考场上这题能做对,说明我的直觉方向是有效的;但从复盘角度看,它也提醒我,填空题和结论题不能只停留在“感觉应该是这样”,最好能快速找到一个能够支撑结论的最小反证或证明点。
T4:蓝桥竞技
点击展开/折叠 T4题面
题意简述
有 种位置,第 种位置有 名选手。
现在需要把所有选手分成若干支战队,每支战队必须满足:
- 恰好有 名选手;
- 这 名选手来自 个不同的位置。
也就是说,同一支战队中不能出现两个相同位置的选手。
对于每组数据,判断是否可以把所有选手全部分完。如果可以,输出 T,否则输出 F。
考场思路
这题我在考场上第一时间没有想出简洁做法,大概卡了小十分钟后选择先跳过。
后面把剩下能写的题处理完之后,我又回头来看这题。当时心态已经有点崩,没有再冷静地从必要条件和充分性角度分析,而是把它当成了一个实际分组问题,写了一个比较复杂的递归 / 构造逻辑。
正解思路
设总人数为:
如果所有选手可以被分成若干支合法战队,那么每支战队恰好 人,所以首先必须满足:
如果这个条件不满足,显然无法分完。
设最终一共有:
支战队。
由于每支战队中同一种位置最多只能出现 名选手,因此对于任意一种位置 ,这 名选手最多只能分散到 支战队中。
所以还必须满足:
也就是:
这两个条件是必要的。
接下来需要说明它们也是充分的。
可以把 支战队看成 个盒子。对于第 种位置,因为:
所以它的 名选手总能分别放进不同的战队中,不会出现同一支战队里有两个相同位置选手的情况。
更直观地说,可以每次从当前剩余人数最多的 个不同位置中各取 人组成一队。只要总人数仍然是 的倍数,并且没有任何一种位置的人数超过剩余队伍数,就不会出现某一种位置被迫在同一队中重复出现的情况。
因此,判断条件就是:
且:
两者同时成立时输出 T,否则输出 F。
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题的考场代码我并不确定是完全正确的。现在回头看,当时的写法明显过于复杂,也没有抓到这题真正的判定核心。
我没能在考场上及时识别出它是一个充分必要条件判定题。其实是可以秒的,但是没看出来这个充要条件,浪费了很多时间不说,极大程度地影响了心态和答题节奏。这很伤。
题目表面上是在说“分组”,很容易让人下意识地去想怎么实际构造每一支队伍。但它只要求判断是否存在方案,并不要求输出具体分组方式。也正是因为我被“分组过程”带偏了,才会在考场上写出一个复杂且不确定正确性的递归。
赛后重做时,这题其实可以压缩成两个条件:总人数能否被 整除,以及人数最多的位置是否超过队伍数。真正难的不是写代码,而是敢于相信这两个条件不仅必要,而且充分。
这题给我的经验是,遇到“能否分组”“能否安排”“是否存在方案”这类问题时,不要第一时间进入搜索或递归。应该先看总量约束,再看单类上界约束,最后判断这些必要条件是否已经足够。如果能在考场上先完成这一层抽象,很多看似需要构造的问题其实会变成非常简洁的判定题。
T5:LQ 聚合
点击展开/折叠 T5题面
题意简述
给定一个长度为 的字符串,字符串中只包含三种字符:
LQ?
其中,? 可以被替换成 L 或 Q。
定义一个字符串中的 LQ 聚合数量为满足以下条件的二元组数量:
并且:
也就是说,需要统计有多少对 L 在前、Q 在后的组合。
题目要求将所有 ? 替换成 L 或 Q,使得最终字符串中的 LQ 聚合数量最大,并输出这个最大值。
考场思路
这题我在考场上没有真正推出来正解。
当时我大致猜到,? 的替换可能应该倾向于前面放 L、后面放 Q,也就是类似:
1 | LLLLQQQQ |
这样的形态。但这个结论在考场上并没有被我证明出来,我也没有把它稳定地转化成枚举分界点的做法。
最后我写了一个基于这个猜测的贪心做法,但这个做法并不严谨,大概只能拿到很少的小样例的部分分。
正解思路
首先考虑一个关键结论:
在最优方案中,所有
?的替换结果一定可以看成:前面一段替换成L,后面一段替换成Q。
也就是说,如果按 ? 在原字符串中出现的顺序来看,最优形态一定可以写成:
1 | LLLL...LLQQQ...QQ |
不会出现某个较早的 ? 被替换成 Q,而某个较晚的 ? 被替换成 L 的情况。
证明这个结论可以用交换法。
假设存在两个 ?,位置分别为 ,且:
但当前替换为:
也就是出现了 Q ... L 的倒置。
如果把它们交换成:
那么这两个位置本身就会新增一对 LQ。同时,对于它们中间的字符:
- 中间的
Q可以和新的左侧L形成贡献; - 中间的
L可以和新的右侧Q形成贡献。
因此,把较早的 Q 和较晚的 L 交换成 L ... Q,答案不会变差。
所以最优方案一定存在一个分界点:分界点之前的 ? 全部替换成 L,分界点之后的 ? 全部替换成 Q。
接下来问题就变成了:
枚举这个分界点,并快速维护当前字符串中的 LQ 数量。
一种做法是,初始时先把所有 ? 都当作 Q。
此时我们可以计算出当前字符串中的 LQ 数量,记为 cur。
然后按照 ? 出现的位置从左到右枚举,每次把当前这个 ? 从 Q 改成 L,相当于枚举新的分界点。
假设当前处理的是第 个 ?,它在原字符串中的位置为 。
当它从 Q 改成 L 时,答案会发生两部分变化。
首先,它原来作为 Q,会和它左边的所有 L 形成 LQ 对。现在它不再是 Q,这些贡献要删掉。
它左边的 L 包括两部分:
- 原字符串中固定的
L; - 前面已经由
?改成L的字符。
如果前面已经处理了 个 ?,那么这一部分数量就是 。
因此损失为:
其次,它现在作为 L,会和它右边的所有 Q 形成新的 LQ 对。
由于初始时把所有 ? 都看作 Q,而我们是从左到右依次把 ? 改成 L,所以当前位置右侧仍然为 Q 的数量可以用前缀统计快速得到。
记这部分新增贡献为:
于是每次转移就是:
在枚举所有分界点的过程中取最大值即可。
由于每个位置只会被处理常数次,所以总复杂度为:
需要注意的是,LQ 对数最多可以达到 ,因此答案和当前贡献都需要使用 long long。
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题我在考场上真正卡住的点,其实不是后面的维护,而是没有把 ? 的最优替换形态严格推出来。
我当时隐约猜到了答案可能应该长成“前面一段 L,后面一段 Q”的形式,但因为没有证明这个结论,所以后面写得很虚,只能沿着一个不严谨的贪心往下做。现在回头看,如果当时能够通过交换法确认这个形态,那么后续自然就会变成枚举分界点,再用前缀和或增量维护来计算答案。
赛后重做时也是这样:一旦意识到所有 ? 的替换结果可以按分界点划分,后面的建模和代码其实都能顺着推出来。初始把所有 ? 当成 Q,然后从左到右依次改成 L,每次维护损失和新增贡献,这一套实现并不算特别绕。
所以这题暴露的问题很明确:不是完全没有算法能力,而是考场上缺少把“直觉形态”转化为“可证明结构”的那一步。对于这类最优构造题,如果感觉某种答案形态是对的,应该优先尝试用交换法证明它。一旦形态被证明,问题往往就会从不确定的贪心变成可以枚举的确定模型。
T6:应急布线
点击展开/折叠 T6题面
题意简述
给定 台电脑和 条已经存在的连接线。把电脑看成点,连接线看成无向边,那么当前网络可能并不连通。
现在可以新增若干条应急跳线,使得整个网络最终连通。
题目要求输出两个值:
- 让整个网络连通所需新增跳线数量的最小值;
- 在新增跳线数量最小的前提下,最小化“单台电脑接入新增跳线数量”的最大值。
考场思路
这题第一问比较直接,只要统计当前图中有多少个连通块。设连通块数量为 ,那么最少需要新增:
条边,才能把所有连通块连成一个整体。
问题主要出在第二问。
考场上我当时偏向于把新增跳线理解成一种“星型连接”:找一个足够大的连通块作为中心,让它去连接其他所有连通块。于是我的思路会关注最大连通块的大小,如果最大连通块大小不少于 ,那么似乎可以让这个中心连通块里的不同电脑分别承担一条跳线,从而让最大接入数为 。
这个思路能覆盖一部分情况,但它默认了最优方案必须接近星型结构。赛后回头看,这个假设是不完备的。
正解思路
第一问仍然是连通块数量。
如果当前图中有 个连通块,那么为了让整个图连通,至少需要:
条新增边。
这是因为每新增一条边,最多只能把两个连通块合并成一个。要把 个连通块合并成一个,至少需要 次连接。同时,只要把这些连通块连成一棵树,就可以用 条边做到。
所以第一问答案为:
接下来考虑第二问。
在新增边数最少的前提下,新增边数量已经固定为:
每条新增边有两个端点,所以一共会产生:
个新增跳线端点。
第二问本质上就是:把这些新增跳线端点尽量均匀地分配到 台电脑上,使得单台电脑承担的端点数最大值最小。
因此答案至少是:
这个下界是可以达到的。
如果:
说明所有新增跳线端点可以分配给不同电脑,那么第二问答案为 。
如果:
则至少有一台电脑需要承担两个新增跳线端点。由于 ,此时答案不会超过 。例如可以把所有连通块按链状连接,每个连通块最多需要承担两个连接端点,而连通块中至少有一台电脑可以承担这些端点。
当 时,原图已经连通,不需要新增边,两个答案都为 。而公式:
此时也自然得到 。
所以第二问可以统一写成:
代码中使用整数上取整:
即可。
连通块数量可以用 DFS / BFS 或并查集统计。我这里使用 BFS 建图遍历(因为我还没学并查集)。
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题我考场上应该拿到了大部分分数,第一问的连通块判断没有问题,真正的问题出在第二问的结构理解上。
我当时的思路更偏向星型连接:找一个最大的连通块作为中心,让它承担连接其他连通块的任务。如果最大连通块大小至少为 ,那么确实可以让中心连通块里的不同电脑各接一根新增跳线,从而让最大接入数为 。
但这个条件只是充分条件,不是必要条件。最优方案并不一定要是星型,也可以是链状或其他树状结构。比如多个连通块可以共同分摊新增跳线端点,而不需要所有边都压在同一个中心连通块上。
正解的视角其实更简单:最少新增边数固定为 ,于是新增跳线端点总数固定为 。第二问要做的不是找中心,而是把这些端点尽量均摊到所有电脑上。
这题给我的经验是,遇到“在最少边数前提下最小化最大负载”这类问题时,不要急着假设某种具体结构,比如星型。应该先看总资源量和总负载量,再判断平均下界是否可以达到。考场上我差的就是这一层抽象:从“找一个中心连通块”转到“统计新增端点并均摊”。
T7:理想温度
点击展开/折叠 T7题面
题意简述
有 个位置,每个位置当前温度为 ,理想温度为 。
现在可以选择一个连续区间 ,并给这个区间内的所有温度同时加上同一个整数 。
操作后,若某个位置满足:
则这个位置达到理想温度。区间外的位置不变。
题目要求在最多一次这样的操作后,最多能让多少个位置达到理想温度。
考场思路
这题我考场上的思路是先计算每个位置的差值:
如果选择某个区间并加上 ,那么区间内只有满足 的位置会被调整到理想温度。
基于这个想法,我当时统计了每个差值对应的出现范围,并把数组整体分成三部分:区间前、区间内、区间后。然后比较原本已经达到理想温度的位置数量,以及对某个差值的完整覆盖区间进行调整后的收益。
但写到中途我已经意识到这个思路并不完整。
因为如果某个差值 的两次出现之间夹着很多 的位置,那么这些位置原本已经是理想温度,一旦被非零 覆盖,反而会被调整错。也就是说,完整覆盖某个差值的出现区间不一定最优,真正的最优区间可能只取这个差值出现位置中的一段。
当时剩余时间已经不允许我重新建模并推到正解,所以我只能沿着这个不完整的思路继续写,尽量拿到一部分分。
正解思路
首先仍然定义差值:
如果 ,说明这个位置本来就已经达到理想温度。设这些位置的数量为:
如果不进行任何有效调整,答案至少为 。
接下来考虑一次操作选择的加值为某个非零整数 。
对于区间中的每个位置,有三种情况:
- 如果 ,那么这个位置会从不正确变成正确,贡献 ;
- 如果 ,那么这个位置原本正确,但被加上非零 后会变错,贡献 ;
- 如果 且 ,那么这个位置操作前后都不正确,贡献 。
因此,对于固定的 ,问题就变成了:
在一个由 组成的收益序列中,选择一个连续区间,使区间收益最大。
这就是最大子段和模型。
不过不能对每一个 都完整扫描一遍数组,否则复杂度会退化到 。
注意到对于固定的 ,真正产生正贡献的位置只有 的位置。其他非零且不等于 的位置贡献为 ,只有 的位置会作为负贡献出现。
所以可以把每个非零差值 的出现位置存下来,只在这些位置上做“稀疏最大子段和”。
假设某个差值 出现的位置依次为:
每个 自身贡献 。
如果把上一个出现位置 和当前出现位置 放在同一个区间中,那么中间夹着的 的位置会产生负贡献。
用前缀数组 统计 的个数,则:
表示 和 之间有多少个原本已经正确的位置。
于是稀疏最大子段和的转移为:
其中:
- 表示从当前位置重新开一段;
- 表示接在前面的最优段后面,当前 贡献 ,中间的 贡献负数。
对每个非零差值 计算最大收益,最终答案就是:
由于每个非零位置只属于一个差值分组,所以所有分组的总处理次数为 。使用 unordered_map 存储每个差值的出现位置,平均复杂度为:
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题是我这次复盘里花时间比较久的一题。考场上我并不是完全没有意识到问题,实际上我已经发现“完整覆盖同一差值区间”这个思路不对,因为中间的 会变成负贡献,最优区间很可能只取其中一段。
但发现原思路不对,和在考场上重新抽象出正解,是两回事。
这题真正的转化是:固定一个非零差值 ,把每个位置的影响变成 ,然后做最大子段和。再进一步,由于不能对每个 扫完整数组,还要把它压缩成只遍历同差值出现位置的稀疏最大子段和。
这几层抽象在赛后复盘时我都花了不少时间,考场上剩余时间不足的情况下,基本不可能完整推出来。因此当时选择沿着已经写了一半的部分分思路继续提交,我觉得是可以接受的。
这题给我的经验是,如果在考场上已经意识到当前思路不完整,但又无法在短时间内完成重新建模,就应该果断止损,把能写出的部分分先落地。赛后真正要补的是模型归类能力:一旦看到“选一个区间,某些位置加分、某些位置扣分”,就应该尽快联想到最大子段和。
T8:足球训练
点击展开/折叠 T8题面
题意简述
有 名队员,第 名队员的初始能力值为 ,每训练一天可以增加 的能力值。
现在一共有 天训练时间,需要把这些训练天数分配给队员。设第 名队员被训练了 天,那么最终能力值为:
并且:
题目要求最大化所有队员最终能力值的乘积:
并对 取模。
考场思路
这题作为最后一题,我在考场上没有考虑正解。
当时我的策略很明确:直接写 DFS 暴力枚举训练天数分配,尽量拿到至少 的部分分。对于小范围数据,枚举每个队员分到多少天训练,再计算乘积最大值即可。
这不是完整做法,但作为压轴题,在我没有正解思路的情况下,先把能稳拿的部分分写出来,是比较现实的选择。
正解思路
这题的关键在于把“分配训练天数最大化乘积”转化为“每一天训练带来的边际收益”。
假设第 名队员已经训练了 天,那么他当前能力值为:
如果再给他训练一天,能力值会变成:
此时整体乘积会被乘上一个倍率:
这个倍率就是“再训练他一天”的边际收益。
将它变形:
可以看出,随着 增大,分母变大,所以同一个队员继续训练的边际收益会逐渐下降。
也就是说:
同一个队员训练越多,继续训练他的性价比越低。
因此,最优策略可以理解为:
从所有队员的所有“下一天训练收益”中,选出最大的 个。
如果 很小,可以直接用优先队列,每次选择当前边际收益最大的队员训练一天。但本题中 很大,不能一天一天模拟。
为了批量处理,需要进一步引入“水位线”模型。
将能力值写成:
其中 是固定的。令:
可以把 理解为第 名队员当前的“水位”。
每训练一天,就是让他的水位增加 。
从边际收益公式:
可以看出,水位越低,下一次训练的边际收益越高。
所以问题等价于从所有序列:
中选出最小的 个水位。
接下来二分一个安全水位线 。
对于某个队员 ,如果:
那么这一次训练对应的水位不超过 ,可以先被选中。
满足条件的 为:
所以这个队员在水位线 下会被分配:
天训练。
对所有队员求和,就可以判断当前水位线下会选出多少次训练。
二分时维护一个尽可能高、但选出的训练天数不超过 的水位线。二分结束后,先根据这个水位线批量计算每个队员的训练天数 ,并统计还剩多少天没有分配,记为 rest。
由于水位可能存在并列,二分得到的水位线通常不能刚好选出 天训练。因此还需要用优先队列补齐剩余天数。
此时,对于每个队员,下一次训练对应的水位是:
每次从优先队列中取出当前水位最小的队员,给他训练一天,然后更新他的水位并重新放入队列,直到补完剩余的 rest 天。
最后,每个队员的训练天数 已经确定,直接计算:
即可。
AC代码
点击展开/折叠 最终 AC 代码
1 |
|
小结
这题我承认是考场上真正不会的题。
和前面一些题不同,这题不是差一步证明、差一层抽象,或者考场上没有写稳。它的正解从建模开始就很难:需要先意识到训练天数分配可以转化为边际收益,再发现同一队员的边际收益递减,最后进一步转成水位线模型。
即使看出了“训练越多,继续训练的性价比越低”,后面的实现也并不轻松。二分水位线、用 floor 统计训练次数、处理 +1 的边界、二分后用优先队列补齐剩余天数、最终乘积时防止溢出,这些细节任何一个写错都可能导致错误。
我赛后复盘这题也花了很长时间。最后能把它写出来,更多是通过一点点拆解:先理解边际收益递减,再理解“选前 个最大收益”等价于选最小水位,再理解为什么二分只能批量分配大部分训练天数,最后再用堆补齐边界。
所以考场上直接写 DFS 暴力拿 部分分,我认为是合理的。压轴题如果短时间内完全看不到正解入口,与其硬耗,不如先把小数据部分分拿下。
这题值得反复回味。它给我的经验是,乘积最大化问题经常可以从边际收益入手;如果边际收益具有单调性,就可能进一步转化为贪心、二分答案或优先队列维护。对我来说,这题目前还不能算真正熟练掌握,但至少通过这次复盘,我已经把主要思路和关键实现细节补上了。
考场整体复盘
从整场来看,我大致稳住了两三道题,也在最后的难题拿到了一些部分分。但对于中间几道完全有能力AC的题,发挥并不稳定。
稳住的部分
虽然我对这场比赛的发挥很不满意,但从结果和复盘来看,这场比赛并不是完全失控的。
首先,部分题目我还是稳住了的。T1 虽然开局被题面干扰了一下,但最终及时把问题抽象成整数拆分计数,没有因为第一题的轻微卡顿继续影响判断;T3 虽然考场上没有给出严格证明,但凭直觉抓住了“合法数组只能全相等”的核心结论,最终方向是对的;T6 第一问的连通块判断是稳的,第二问虽然卡在了星型结构的错误理解上,但至少抓住了“连通块数量决定新增边数”的主线,这足以拿到大部分分数。
其次,我在一些题目上做出了比较合理的取舍。T2 看了约十分钟没有思路后直接跳过,没有继续投入大量时间;T8 作为最后一题,在完全看不到正解入口的情况下,直接写 DFS 暴力去拿小数据部分分。这些选择现在回头看都是合理的。比赛中不是每一道题都值得死磕,尤其是高难填空题和压轴题,如果短时间内没有有效模型,及时止损本身就是一种能力。
再者,即使一些题目没有完全做出正解,我也不是完全空白。T4 在心态崩盘 + 时间紧促的情况下,依旧写出了一个繁琐但能拿到部分分数的递归;T7 虽然没有推出最大子段和模型,但已经意识到差值和区间调整之间的关系,也意识到完整覆盖区间并不严谨,从结果上来看似乎也拿到了小部分分数;T8 也至少通过暴力拿到了能拿的部分分数。
所以从整体来看,这场比赛里我确实有不少没做好的地方,但也有一些下限是保住了的:基础题没有大面积崩盘,遇到高难题时有止损意识,除了 T2 蒙了个答案上去, 其他题尽量都写了能拿分的东西。这些共同构成了最后省一的结果。
没稳住的部分
这场比赛最让我不满意的地方,是很多题并不是完全没有方向,而是在关键一步上没有稳住。
T1 虽然最后做对了,但第一题上来就被题面卡了一下,本身就说明我的考场状态并不理想。第一道填空题本该快速确认、快速通过,但我却一度被“拆分”和年份拼接这些信息干扰。这种开局轻微卡顿虽然没有直接造成失分,但确实影响了后续的心理状态。
T3 虽然这道题AC了,但是没有想出严谨的证明。这个难度的题不应该想不出来证明。
T4 是最典型的失误。这题赛后重做发现其实只需要判断两个条件:总人数能否被 整除,以及最大位置人数是否超过队伍数。它本来是可以很快做出来的题,但我在考场上没有识别出这个充要条件,而是被“分组”这个表述带进了复杂递归和构造思路里。这不仅浪费了时间,也明显打乱了我的答题节奏。
T5 的问题则是没有推出来 ? 的最优替换形态。事实上,只要证明所有 ? 一定可以写成前面一段 L、后面一段 Q,后面就会自然变成枚举分界点和增量维护。但考场上我只是隐约猜到了这个形态,却没有把它证明出来,也没有敢沿着这个方向继续推进。最后写出的贪心缺乏严格依据,只能拿一些小样例的部分分。
T6 第二问的问题在于,我把最优结构想成了星型连接。这个思路能覆盖一部分情况,但它只是充分条件,不是必要条件。真正的正解应该从新增跳线端点总数出发,把 个端点尽量均摊到 台电脑上。这里我没有及时从具体构造跳到总量约束。实际上我已经把大部分的问题都解决了,就差最后这“临门一脚”。
T7 是另一类问题。我已经意识到自己原来的完整区间思路不对,也意识到 的位置会成为负贡献,但当时已经没有时间重新建模。赛后复盘时才发现,它真正应该转成“固定差值后的稀疏最大子段和”。这题说明我在考场上即使摸到了正解附近,也未必能在时间压力下完成最后的模型归类。
T8 则是完全不会正解。边际收益递减、水位线二分、优先队列补齐这些东西,考场上我基本不可能完整想出来。虽然写暴力拿部分分是合理选择,但从能力角度看,这题确实暴露出我对高阶贪心、二分批量分配和复杂边界实现的掌握还不够。
整体来看,这场比赛没稳住的核心并不是单纯“不会写代码”,而是几个关键抽象没有完成:T4 没有压缩出充要条件,T5 没有证明答案形态,T6 没有跳出星型构造,T7 没有归类到最大子段和,T8 则是从建模到实现都超出了我的考场能力范围。
暴露出的问题
这些题共同说明,我当前最大的问题仍然在于:有时能摸到方向,但无法在考场压力下把方向转化成稳定、可证明、可实现的正解。
1. 抽象建模能力还不够稳定
很多题我不是完全没有方向,而是差在最后一层抽象。
有些题需要从具体构造跳到充分必要条件,有些题需要从局部贪心跳到答案形态证明,有些题需要从区间操作跳到收益模型。赛后重做时,这些转化往往可以慢慢推出来;但在考场上,时间有限、压力很大,一旦第一反应没走对,就很容易停在一个不完整的思路里。
2. 证明意识不足
考场上我有时能凭直觉猜到某个结论,但没有及时把它证明出来。
直觉在比赛里当然很重要,但如果一个结论不能被证明,它就很难支撑后续实现。尤其是最优形态、充分必要条件、贪心正确性这几类题,必须尽快找到一个能说服自己的证明方式,否则写出来的代码就会很虚。
3. 实现细节距离稳定 AC 还有差距
有些题即使赛后理解了思路,真正写代码时也会反复卡在细节上。
比如最大子段和转移、前缀统计边界、二分中的 floor 和 +1、取模乘法防溢出等。这说明我目前还没有把一些模型练到“看到就能稳写”的程度。理解思路和稳定 AC 之间,仍然有一段距离。
4. 考场心态和节奏控制仍然不稳
前面题目一旦卡住,我的心态会受到明显影响。
有些题本来不应该消耗太多时间,但卡住之后会影响后面的答题节奏。考场上不只是比会不会做题,也是在比能不能及时判断:这题该不该继续想,当前思路值不值得写,写到什么程度应该止损。
5. 部分分策略还不够成熟
这次我确实在一些题上写了部分分,后面的复杂题也没有完全空着;但现在回头看,我还没有做到真正意义上的“稳定骗分”。
稳定骗分不是随便写一个错误贪心,而是在明确数据范围和部分性质的基础上,写出尽可能可靠、可控、能覆盖一部分测试点的做法。考场上如果正解一时想不出来,如何设计一个高可信度的部分分方案,也是我后续需要训练的能力。
总的来说,这次省一说明我有一定的基础和下限,但也暴露出我距离更稳定的竞赛能力还有差距。后续需要补的不是某一个孤立知识点,而是一整套能力:抽象建模、证明结论、实现细节、考场节奏,以及在不会正解时稳定拿部分分的能力。
结语
省赛一等奖,北京市第 25。
从结果上说,这已经是一个足够好的阶段性结果。这份奖项于我也有着特殊的意义——它似乎印证着我已从两三年的阴霾中走了出来。
在复盘完整套题之后,我也很清楚,我并不满意本场比赛的发挥。这也是为什么我在走出考场的时候郁闷至极。我感觉自己的这个发挥可能也就是省三了,运气好能到省二。很多题不是完全不会做,而是都被一些本应想通的点给卡住;有些题本可以更快做出来,却在考场上被题面或心态带偏;还有些题虽然写了部分分,但并没有做到真正稳定、可控地拿分。
所以这个省一对我来说,更像是一个阶段性证明,而不是终点。
它证明了我为自己的热爱所付出的努力没有白费,证明了过去半年多的算法积累、刷题、博客复盘和赛前准备不是无用功;也说明了即使在状态不佳的情况下,我依然有一定的下限。
但它同样提醒我,我在数学推导、结构转化、证明意识、实现细节和考场稳定性上,还有很多不够成熟的地方。
省赛已经结束,不管这场比赛有多少遗憾,都不能再一直停留在复盘情绪里。复盘的意义不是反复证明自己哪里没做好,而是把这些问题提炼出来,带到下一阶段训练中去。
接下来最现实的目标就是国赛。满打满算,距离国赛也只剩下一个月左右。
我需要迅速调整状态,重新进入备赛节奏。推进一些还没学过的算法知识点,对已发现的问题和不足之处查漏补缺,也要继续训练限时模拟考场、部分分设计和考场决策。
我会带着一如既往的热爱,继续走下去:)