2026牛客寒假营第三场题解

宙天

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

2026牛客寒假营第三场题解

A. 宙天

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

注意到x的范围很小，只有100，直接枚举k就行

B. Random

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

注意到数据是随机生成的。这道题的做法很多，比如随机枚举两个数，判断他们的gcd是否大于1，然后随机若干遍，再比如枚举整个数组，判断其中是2的倍数的数字有多少个，由于n很大的时候全为奇数的概率几乎为0，如果找不到大于等于2个奇数就说明n不大，直接暴力双重循环枚举i和j就可以。代码的做法是通过筛法，经实验当筛到5000的时候可以通过这道题

C. Inverted World

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

既然题目最后要让s中任意两个相邻元素互不相同，按照s的开头为0/1，会发现实际上最后的结果只有两种，而肯定不做重复操作，只改变不同的位置是操作数最少的。对于每一种答案的情况，维护 $cnt[0]$ 和 $cnt[1]$ ，分别表示最后改变0和最后改变1的作用子串的数量，尽可能接在已有数组的后面，实在没有选择再开辟新的作用子串，最后把 $cnt[0]$ 和 $cnt[1]$ 加起来就是答案。

D. 系ぎて

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

做两次bfs，第一次尝试直接把1和1连接起来，然后用染色法判定2和2是否能连通，然后交换1和2，再做两次bfs，只要有一次能成功连通就说明题目存在这样的两条路径。

E. 躯树の墓守

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

可以参考最小生成树Krustal算法的思路。我们先框定能满足题目条件的k的范围，最小的k的取值可以取到从1到m，也就是 $n*(n-1)/2$ ，最大能取到从m-n+2到m，也就是 $(2*m-n+2)*(n-1)/2$ ，如果k不在这个范围里肯定不行。然后我们考虑先取从1到m，这样产生的k值可能有剩余，然后我们考虑把最短边加入连通块当中，加入结束之后，可能会产生连通块里的一些无效边，这时候我们判断，有没有无效边可以填，可以不可以把剩下的所有边的边权都加一，如果可以就把下一个最小边权填在无效边权上。依此类推即可。

F. Energy Synergy Matrix

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

可以画一张图辅助理解。小小红每次只能走一步，最多是列数+1，也就是从第一列走到第 $n$ 列至少要走 $n-1$ 步，想要小小红走的步数尽可能少，就是希望小小红能尽可能少的出现拐弯的情况，也就是让向上或者向下走的步数尽可能少，而且肯定不会掉头往回走。如果 $n=1$ ，小小红出生就在终点，不需要移动，如果 $n=2$ ,小红可以直接放在第二行第二列，小紫不能把终点堵住，只能放在第一行第二列，小小红还是直接向右走一步到终点。如果 $n=3$ ，小红可以放在第二行的第三列，这时候，无论后续再怎么放，小紫也不可能把箱子放在第一行，否则会把路直接堵死，违背题意，所以小小红会直接走到终点。 $n=4$ 同理。但是到了 $n=5$ ，小红还是按照同样的策略，小紫可以直接放在第一行的第五列，让小小红拐一次弯。根据上面的讨论，我们可以发现，小红每次放一个箱子，可以直接控制小紫没有办法在这一列和相邻的两列放箱子，而第一列不需要控制，因为小紫不可能放在第一行第一列。所以，小红开始放在第二行第三列，小紫只能放在第一行的第五列，控制小小红在这里拐一次弯，然后小红放在第一行的第八列，让小紫放在第十行的第二列，小小红又转一次弯...所以我们可以得到一个最小步数的公式 $n-1+n/5$ 。

G. スピカの天秤

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

根据题目，我们只能拿走砝码，所以，如果一开始天平是平衡的，我们在两边随便挑一边拿走一颗，就能让天平不平衡，就能改变状态，而如果天平一开始不是平衡的，我们拿轻的一边的砝码肯定对天平的状态没有影响，甚至会让天平像重的一边更加倾斜。所以答案很明显，就是把砝码拿到天平向另一边倾斜或者平衡，而且为了要拿的数目尽可能少，我们肯定要从重的开始拿。

H. Tic Tac DREAMIN’

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

这道题可以用叉乘的公式求。但赛时的代码是用分类讨论做的：如果A和B重合，显然无解。如果A和B在同一条水平线上，无论x取什么，三角形的面积都是固定的，如果这个面积就是2，可以直接随便输出一个x轴上的点，如果这个面积不是2，直接输出无解。如果A和B在同一竖直线上，并且现段长度为 $l$ ，那么我们只需要找一个x轴上和这条线段水平距离为 $4/l$ 的点就可以。对于更为一般的情况，我们直接找直线 $AB$ 和x轴的交叉点 $C$ ，这时候，把 $AB$ 的竖直方向上的距离作为高，找的点 $O$ 和 $C$ 的水平距离作为底，这个求出来的面积就是三角形的面积。让这个面积为2就可以。

I. BenzenE

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

最开始，我们直接令所有的 $i$ ，都有 $c_i=a_i$ ，这时候得到一个结果 $sum$ ，现在我们开始做替换，如果我们要把 $a_i$ 替换成 $b_i$ ，相当于先给 $sum$ 里去掉 $a_i$ ，即 $sum\oplus a_i$ ，然后再异或上 $b_i$ ，即 $sum\oplus a_i \oplus b_i$ ，然后异或满足结合律，也就是每做一次替换，相当于给 $sum$ 异或上 $a_i\oplus b_i$ 。如果有这么一个替换方案，让 $sum=0$ ，那方案就存在，如果没有相应的替换方案，那就不存在这样的c数组。所以实际上问题就是，由 $a_i \oplus b_i$ 构成的线性基，能不能表达出 $sum$ ，然后还要把方案还原出来。代码里用的set维护还原方案，时间上可能偏慢，但实际上对于用于线性基的表示的数不多，我们只需要用01串来维护就可以？