02-06 17:53 北京邮电大学发布于海南

关注

2026牛客寒假营第一场题解

A+B Problem

https://ac.nowcoder.com/acm/contest/120561/A

2026牛客寒假营第一场题解

A. A+B Problem

题目链接：https://ac.nowcoder.com/acm/contest/120561/A
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81946967

shit 给定一个数码管七个管的显示概率，然后就可以当成七个独立事件，求出显示每一个数字的概率，然后代码的做法是设计了一个dp[2][2][10]，第一个状态表示是否接受了进位，第二个状态表示是否向前进位，第三个状态表示个位数是多少，然后枚举i从0到9，j从0到9，得到个位数为n的不同情况概率，然后枚举结果c的每一位，设计另一个ans[4][2][2]，分别表示第几位，是否接受进位，是否向前进位，做状态转移就行，但是这道题可以更加的粗暴，就是枚举得到从0到c的概率，然后再双重枚举a和b的做法就行。

B. Card Game

题目链接：https://ac.nowcoder.com/acm/contest/120561/B
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81927387

赛场上挣扎了很久，一定要注意：一旦比赛开始，卡牌的顺序就不会再重排，顺序是固定好的，输的牌不会离开场上。那么做法其实也显然：假设小红最小的牌上面的数字是 $a_{min}$ ，只要我的数字比这个 $a_{min}$ 大，能放得到牌堆顶上，他一定能出去，哪怕赢的不是 $a_{min}$ ；而这个数字比 $a_{min}$ 小，那他怎么都出不去，而且一旦轮到牌堆顶，后面的牌也别想出去，所以小苯的牌其实就分成两类，能出去的和出不去的，把能出去的牌堆到前面，不能出去的牌全部堆到后面，顺序不重要，那就是做两次排列再相乘就行。

C. Array Covering

题目链接：https://ac.nowcoder.com/acm/contest/120561/C
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81900379

首先可以发现，1和n这两个位置肯定动不了，而且所有的数经过操作之后肯定不会大于最大值，假设这个数组在 $i=maxi$ 的时候 $a_i$ 取到最大值 $maxn$ ，那上面的话可以转述为

\sum_{i=1}^{n}a_i \leq a_1+a_n+(n-2)*maxn

而且这个等式肯定是成立的，如果 $i=1$ 或者 $i=n$ ，那直接取 $l=1,r=n$ 就能取到，否则我做两次操作，一次取 $l=1,r=i$ ，另一次取 $l=i,r=n$ ，也能取到等号。这里有一个特殊情况，当 $n=1$ 的时候，实际上我们一次操作也做不了，但是经验证这个式子依然成立。

D. Sequential Coloring

题目链接：https://ac.nowcoder.com/acm/contest/120561/D
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81996971

很有巧思的一道二分答案的题目，首先这个二分性质还是挺好发现的，就是如果我用 $t$ 秒能把所有白色都染红，用 $t+1$ 秒肯定也能全部染红。这道题真正的难点在于check函数的设计。代码的实现是设计一个nxt函数，表示染红当前元素之后能到达的右边界，对于白色元素而言 $nxt[i]=a[i]+i$ ，对于黑色元素来说这么写其实也影响不大，然后nxt数组做一个前缀最大值，表示到达当前位置的时候能够到达的最大右边界是多少，在写check函数的时候，一次拓展就是直接跳到最大右边界，t秒就是做t次拓展，当然如果时间超限或者拓展完了发现没有办法拓展下去（即nxt[i]=i，没有产生能突破当前边界的红色元素），就要做一次新的涂色，最后用涂色次数直接去和k相比，就能写出来check函数。check函数的细节比较多需要注意。

E. Block Game

题目链接：http://ac.nowcoder.com/acm/contest/120561/E
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81911868

如果我们把数字k也插到数组a的最前面，然后我们把这个位置叫作万能方块位，然后我们会发现，做一次操作就相当于把数组a往后推一位，然后最后一位的数字跑到数组a的第一位，这个数组就可以当作一个环来处理，问题就转化成了：求这个换上相邻两个数字的和的最大值。

F. Permutation Counting

题目链接：https://ac.nowcoder.com/acm/contest/120561/F
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82000449

对于区间里的每一个数 $i$ ,我们可以维护两个集合：以这个数为最大值的所有集合的交集，以这个数为最大值的所有集合的并集。然后有几件事：i一定在交集里，并集里一定没有比i更大的数。当然这里有一个特判：如果我们发现交集成空集了，那一定不存在满足条件的填法。我们从1到n枚举所有数，如果这个数没有作为提供的区间最大值提供过，那就先放着不考虑，如果出现过，那我们就要在交集里找一个位置给i填上，假如有 $emp$ 个位置还没填，答案就是要乘上一个 $emp$ ，然后再考虑并集，为了防止后面处理麻烦，我们把并集里所有还没填的位置填上，填的数字也就是前面还没用过的数字，假如有 $cnt$ 个没用过的数字，有 $pos$ 个没填过的位置，那这里就可以用排列数处理，即给答案乘上 $A_{cnt}^{pos}$ ，这里要特判一件事：如果 $cnt<pos$ ，说明并集里不能用更小的数字填充完，也就是这里面肯定要填一个更大的数，这显然与我们上面的条件相违背，所以这种情况直接乘0就行，不可能存在满足条件的方案。问题的关键在于怎么记录和查询 $emp$ 和 $pos$ 的数量。一种处理方法是用线段树，我们先把区间所有位置记为1， $emp$ 就是交集里的区间和，这里不着急给交集全部记为0，我们直接去查并集里的区间和，然后我们减去1，表示给 $i$ 填上，得到的就是 $pos$ ，然后我们更新一下 $cnt$ ，把所有跳过的数补上。到这里好像这道问题已经解决了，但是这道题的时限卡掉了线段树，我们要用更快的方法处理。实际代码用的是链式并查集。区间推平就是把区间里所有的块合并到区间外，这件事有点像缩点，只要这个点不是父节点，我们就当他不存在。区间查询就是有点像暴力枚举，遇到一个父节点不是自己的点，我们直接跳到它的父节点，然后进行计数。

G. Digital Folding

题目链接：https://ac.nowcoder.com/acm/contest/120561/G
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81958417

shit 既然要翻转最大，那很自然的可以想到一种构造方法是一个数后面跟着一堆9，由于r的位数不超过15，那直接枚举每一位上的数减1，然后后面重复填9，得到的数显然小于r，我们只要判断它会不会大于l，然后再翻转过来和maxn比就可以，但是这里有几个特例，l和r的差别仅仅只是个位，那我们上面的构造都不会满足条件，这里可以证明的是由于 $r \geq l$ ，r的翻转一定是最大的，所以我们直接把 $maxn$ 的默认值设为r的翻转就行。

H. BlackBoard

题目链接：https://ac.nowcoder.com/acm/contest/120561/H
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81986815

这道题一定一定要想想2025年校赛的时候那道区间dp我们是怎么变成 $O(n^2)$ 的，这道题很类似。首先我们明确一件事：如果两个数在某一位上均为1，这两个数或起来的结果一定比它们的和小，而我们从某一位开始往回推，0的数字我们就不看了，就看大于0的位置，我们会发现，要满足这几个数没有至少两个数字在某一位上均为1，最多只能找到31个数字。所以我们直接令 $dp[i]$ 表示以i为结尾的方案数，考虑i的时候我们直接往回推，如果 $[j+1,i]$ 这段区间满足和等于或，我们就 $dp[i]=dp[i]+dp[j]$ ，这件事情可以用前缀和维护。

I. AND vs MEX

题目链接：https://ac.nowcoder.com/acm/contest/120561/I
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=81997513

如果 $l=0$ ，这里显然 $mex_{max}=r+1$ 。如果 $l\not=0$ ，我们用 $b1$ 表示l的二进制长度，用 $b2$ 表示r的二进制长度，如果 $b2\geq b1+2$ ，我们可以知道区间里有，00111...，然后从0到l的数就都可以通过构造出来，自然答案也是 $r+1$ 。如果 $b2=b1$ ，无论我们选取什么数字，最高位一定为1，按位与得到的结果一定不为0，那答案自然也是0。如果 $b2=b1+1$ ，我们同样还有01111...这样的数字，可以得到 $[0,r-2^b]$ 这些数字，与此同时，比如 $l=(1101100)_2$ ，我们有这样的数字： $(1101111)_2$ ，然后用111....这样的数字可以得到 $(1110000)_2$ 往上的数字，我们只要判断这两个区间能不能合在一起就行。

J. MST Problem

题目链接；https://ac.nowcoder.com/acm/contest/120561/J
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=82008861

首先Prim算法：维护一个连通块，每一次把距离这个连通块最近的点连进来，然后利用与这个点相连的所有边更新其他点与连通块的距离，然后持续下去。这道题实际上并不用把整个图建立起来，我们是在抽象的图上进行操作。我们用线段树维护每个点与连通块的距离。线段树中维护的值应有：区间里的点权最小值，区间里的点与连通块相连的最小值。每一次操作，就是找到整个线段树区间里与连通块最近的点，把这个点的点权和与连通块的距离更新为无穷大，然后通过分析不能与这个点相连的点，拆成多个区间进行更新。每次做完一次更新，就把最小边权加到答案里，总共操作 $n-1$ 次，对应最小生成树的 $n-1$ 条边。很牛逼的题和想法！