【较难题目题解】2025牛客寒假算法基础集训营1

C - 兢兢业业之移

这道题首先需要注意到 $n\le 100$ ，那么考虑暴力方法复杂度是否可行：

对于左上角 $\frac{1}{4}$ 区域的每一个位置，遍历每个位置的时间复杂度 $O(n^2)$ ，然后对于每一个位置 $(i, j)$ ，bfs搜索到一个矩阵中距离 $(i, j)$ 最近的“1”，记录下搜索的路径，这样做可以确保该路径上只有“0”，反过来将这个“1”移到 $(i, j)$ 中即可，记录每一步的操作，待会输出方案。最差时间复杂度 $O(n^2)$ 。总共时间复杂度 $O(n^4)$ ，常数很小，因此可以接受。

下面说明这样做的操作次数 $\le \frac{n^3}{2}$ 。一共有 $\frac{n^2}{4}$ 个元素，由于使用bfs搜索路径，每一个元素的移动距离均 $\le 2n$ ，因此总操作次数 $\le \frac{n^3}{2}$ 。

E - 双生双宿之错

考虑这样一个问题：

对于一个序列a，可以执行以下操作任意次：

将某个元素的值+1或-1。

求使得所有元素相同的最小操作次数。

可以证明，取到最小操作次数时，存在一种解，是将所有的元素变为原始序列a的中位数。

如：序列[1, 2, 4, 5, 8]，其中位数为4，则将所有的元素变为4，操作次数最小，最小为3+1+0+1+3=8。当序列为偶数时，存在两个中位数，则选择任意一个中位数，或是两个中位数中间的某个数，操作次数取到最小。

有了这个结论，答案就呼之欲出了：

首先将数组排序，根据“双生数组”的性质，两个元素的个数需相同，那么可以从 $n/2$ 处将数组分为两部分，前半部分和后半部分分别求变成中位数的最小操作次数即为答案。

但这样做还不够：可能存在两部分的中位数相同的情况。设两部分中位数为 $a$ ，在这种情况下，我们分两种情况讨论：

将数组前半部分所有元素变为a-1；
将数组后半部分所有元素变为a+1；

二者取最小值即可。

F - 双生双宿之探

乍一看非常困难的问题。

看到子数组计数问题应该想到使用map。关键是如何将原数组转变为可以计数的数字。

回忆“双生数组”定义，我们可以发现，如果一个数组已经包含超过2个元素，那么它必不可能成为“双生数组”，因此完全不用考虑超过2个元素的数组。

这样一想我们引申出了一条思路：使用一个“队列”，将元素一一放进去，当队列中出现3个不同的元素时，从队头弹出元素，直到队列中只剩两个相同的元素。这样我们就只用考虑统计位于队列中的元素了。

这样队列中就转变为：一个只含有2个元素的数组，求其中“双生子数组”的数量。那么这里可以想到使用map：将某一个元素设为1，另一个元素设为-1，在遍历的过程中使用map记录每一个前缀和。

设当前前缀和为sum，则每次更新map和答案：

ans += map[sum]
map[sum]++;

按照上述思路实现代码即可。时间复杂度 $O(n\log n)$ 。

I - 井然有序之桠

这题赛时没时间写了，感觉官方题解说的就非常清楚，这里就不阐述自己的思路了。

K - 硝基甲苯之魇

这道题是最有说法的一题。

首先需要明确一点：一个数组的不同前后缀gcd个数不超过 $O(\log n)$ 个。这个我就不详细证明了，大概意思就是每次gcd要么不变，要么至少是除以2。因此最多只有log个。

因此，在遍历数组时，我们直接就可以记录下来每一个gcd（比如用一个set存起来），然后同时记录下来取到这个gcd所对应的区间起始位置。例如，数组[5, 6, 8, 2, 4, 2]，当遍历到 $r=5$ 时，后缀gcd共有3个：1, 2, 4。其中：

gcd=1的最长后缀是[5, 6, 8, 2, 4]
gcd=2的最长后缀是[6, 8, 2, 4]
gcd=4的最长后缀是[4]。

对于每一个后缀gcd，我们可以使用一个map记录该后缀gcd所对应的前缀异或和的个数。例如，在上面的例子中，gcd=2的map中应该存储了如下的异或和：

5
5^6=3
5^6^8=11
5^6^8^2=9

因此gcd=2对应的map中存储的应该有：

5: 1（1代表有1个前缀异或和=5）
3: 1
11: 1
9: 1

然后，当遍历到下一个元素时，首先需要迭代一次所有存储的gcd值，例如刚才的数组[5, 6, 8, 2, 4, 2]，当 $r=5$ 时，原本gcd可以取1, 2, 4，显然当 $r=6$ 时gcd就只能取1, 2了。因此遍历到6时，就应该将原本gcd=4的map合并到gcd=2的map中，也就是两个map的元素合并到一起。我们来看看这个合并过程：