题解 | #河南萌新联赛2024第（二）场：南阳理工学院#

河南萌新联赛2024第（二）场：南阳理工学院

本场题目对于萌新来说，可能代码量稍微大一点，比较考验选手的基本功。

预期难度 F I A easy， J D H G mid，E C mid - hard, B K hard.

其中mid难度的题目多以模拟为主，考察选手stl的使用或者模拟的思路。

A:国际旅行 Ⅰ

签到题,根据题意可以得知国与国之间互相联通所以从任意一个国家出发都可以到其他所有国家，故按照权值排序后输出就可以了.

B:国际旅行 Ⅱ

根据题意可以得知国际道路就是该图中的桥边,所以可以先通过 tarjan 缩点得到一颗树，树上的每个节点都代表一个国家，每个节点的权值就是该国家的城市数量这些参数都可以通过 tarjan 求出.记缩完点后的总结点个数为 $n$ 解法1:tarjan 缩点后，我们考虑一种离线做法,将所有询问离线下来,按照询问给出的边权限制进行升序排序，然后把缩完点后的图中所有边去掉,将当前权值不大于询问边权限制的边，依次加入图中,然后再查询u所在的联通块第 $k$ 小的权值，用并查集维护每个连通块，用线段树维护每个连通块权值第 $k$ 小的点,每次合并都在线段树上直接合并.总的复杂度为 $O$ ( $q$ $log$ $n$ ) 解法2:原图一共有 $n$ 个结点的话那么缩点后每个国家拥有的城市数量的种类不超过 $\sqrt{n}$ 种,那么对于解法1种使用线段树维护第 $k$ 小的做法,我们可以使用 map 直接暴力维护联通块中第 $k$ 小的国家查找为 $O$ ( $\sqrt{n}$ ) 暴力合并的复杂度为 $O$ ( $n$ $log$ $\sqrt{n}$ ) 总的复杂度为 $O$ ( $q$ $\sqrt{n}$ + $n$ $log$ $\sqrt{n}$ ) 解法3:在线做法,利用克鲁斯卡尔重构树的性质,(这里不过多展开讲解,有兴趣可以自行了解),对缩完点后的图进行重构,在重构树上,每次从询问结点所在的叶子结点往上跳,找到满足条件的结点后,查询该结点所在子树包含的叶子结点中权值第 $k$ 大的叶子结点实际上就是查询区间第 $k$ 大采用主席树维护,进行克鲁斯卡尔重构复杂度为 $O$ ( $n$ $log$ $n$ ) ,每次向上查找满足条件的结点采用二分或者倍增的方法复杂度为 $O$ ( $log$ $n$ )，主席树每次查询的复杂度为 $O$ ( $log$ $n$ ) 总的复杂度为 $O$ (( $q$ + $n$ ) $log$ $n$ )

C:小w和大W的决斗。

题意可简化为，有 $n$ 堆石子, 每堆石子数量不同，每次操作可以选取其中一堆，取走任意个或者将其分成三堆非空的石子。先把石子全部取完的获胜。

满足 $SG$ 的条件，因为 $1 \leq a_i \leq 100$ 。采用 $SG$ 暴力即可。

当然通过打表我们也可以发现规律。假设某堆石子的数量为 $x$ ，设 $sg(x)$ 为这堆石子 sg 值。

$if$ $x\mod\ 8 == 0$ , $sg(x) = x - 1$

$if$ $x\mod\ 8 == 7$ , $sg(x) = x 1$

$else$ $sg(x) = x$ .

D:A*BBBB

首先大数肯定不能直接去乘，但是发现B的每一位都相同，然后自己模拟乘法发现，当B每一位相同时假设为x，那么就是A乘x，然后B有多少位就往前移多少次，然后再用前缀和进行维护当前位数为多少。答案长度最多为2e6+2。

E:“好”字符

处理循环字符串时，可以将该字符串复制并连接在结尾（这样处理后的字符串的所有长度为 $n$ 的子串都是原串的循环同构串。）

在对某个字符 $x$ 进行判断时，因为我们在匹配的时候只需要考虑某个字符是否为 $x$ ，所以我们可以将字符串 $a$ 和 $b$ 中除了 $x$ 以外的字符全部转化为 '#' 等特殊字符，或者将字符串 $a$ 和 $b$ 根据每个字符是否为字符 $x$ 转化为一个01串。

然后我们定义两种操作：

操作1 ：将字符串复制并连接在结尾。

操作2 ：将字符串根据每个字符是否为字符 $x$ 转化为一个01串（或将字符x以外的字符全部转化为特殊字符）。

接下来有两种解题思路：

思路一：将字符串 $a$ 进行操作 $1$ ，然后将字符串 $a$ 和 $b$ 分别进行操作2 ，接着利用字符串哈希或者 $KMP$ 算法来判断字符串 $b$ 是否为字符串 $a$ 的子串。

思路二：将字符串 $a$ 和 $b$ 分别进行操作1，然后将字符串 $a$ 和 $b$ 分别进行操作2，接着利用最小表示法分别找到字符串 $a$ 和 $b$ 的最小起点，再判断从最小起点开始的长度为 $n$ 的子串是否相等即可。

F:水灵灵的小学弟

签到。

两个人名字首字母大写一样，无论谁赢都是输出DHY。

当然这个博弈并非无解，具体详见威佐夫博弈。

G:lxy的通风报信

本题是一道典型的图论问题，涉及到图的遍历和最小生成树的构建。在二维网格中如果要想将军队合并，就需要知道每个军队之间的距离，我们可以跑bfs来实现，当知道每个点之间的距离之后我们跑一下最小生成树就可以知道最少多少天可以将军队合并了，如果军队与军队之间被阻挡无法到达，则输出No。

H:狼狼的备忘录

题意：给出一堆的成员名字和该成员的一些星座信息，如果同一个成员的星座信息中有一个星座信息是另一个星座信息的后缀，将前者删去。

本题数据很小，只有 $20 * 10$ ，做法很多，利用 STL 解更方便。这里我们用 $map$ 映射所有成员名字所对应的编号，每个成员的星座信息按照题意暴力去重和舍去后缀。时间复杂度： $O((n * op)^2)$

I:重生之zbk要拿回属于他的一切

暴力，签到。暴力遍历查找即可。

J:数学王国

由于数据范围很小，直接根据模拟就能过，模拟过程中可以直接调用全排列函数缩减代码量。

K:Magic Cube

本题主要考察空间想象能力和代码策略。已知魔方存在 6 种不同操作，且一定存在步数小于等于 8 的正解，很容易算出若使用暴力搜索的复杂度约为 $6^8 \approx 2e6$ ，若考虑简单剪枝（即不做上次操作的逆操作）则真正的复杂度为 $6 \times 5^7 \approx 5e5$ ，显然直接暴力 dfs 或 bfs 搜索答案即可。

但你也一定注意到了，此题的主要难点不在于以上推导，而在于如何规划代码实现魔方的 6 种操作。关于这部分的方法不唯一，有直接对展开图操作的，有先保存初始状态在 struct 或 class 中，再进行操作的。总之方法非常多，不存在绝对的正解，篇幅所限在此仅提供一种可行方案。

考虑魔方在转动某一面时，转动面的 9 个颜色会进行顺时针或逆时针移位，与转动面相邻的 4 个侧面中，直接与转动面相邻的 3 个颜色也会按顺时针或逆时针顺序循环移位。故可使用 struct Plane 定义一个面按顺序排列的九种颜色，结构体内部实现单面的顺时针或逆时针移位。使用 struct Cube 定义整个魔方的状态，每次操作先转动单面，再按顺序移位相邻 4 个侧面中的 3 个相邻颜色即可。