牛客周赛140 | 完整题解 – 逢絮聆风—

这场属于康复训练，也是近期来第一场不是苯环命题场。

顺带解释一下为什么网站隔了一段时间没有更新，因为前些日子赛程排得很满（蓝桥杯+天梯赛），再加上身体不堪重负大病一场，所以搁置了好久没有更新。

这一期题解包括了所有题目，G课后花了一点时间补完了。为大家奉上。由于wordpress抽风，CPP代码没有办法被解析，所以暂时不放个人std，对于由此带来的不便深感抱歉。您可以在https://ac.nowcoder.com/acm/contest/132940#submit/%22searchUserName%22%3A%22YeYiTong_Eason%22上看到我的所有提交。

钝评

AB两题偏难，CDEFG属于正常范围。由于前面的开胃菜不开胃了，所以整场做下来不算很顺手，但是题目上还是可以的。

A：小红的区间计数

A题不难但是烦，最开始写的时候以为是签到题就想着速切，结果反而弄巧成拙了。

考虑 $[l,r]$ 区间范围一共会有 $r-l+1$ 个数字，接下来判断 $a,b,c$ 三个数字有没有在这个区间中，如果出现在区间中则将数字总数减一。需要小心的是有几组数据中三个数字中会有至少两个是相等的，所以不要多减。

B：小红的牛魔

这个B题难度也是有点变态了，不过本质还是模拟题。大概和大家拆分一下题意吧。对于给定的字符串，你只能选择字符串中连续的字串"niu"和"mo"进行删除，删除完成后剩余部分会自动拼接。你需要判断能不能通过不断删除最后删除完整个串。

不难发现，如果出现了子串中相对顺序不能满足"niu"或"mo"或者有别的非"n","i","u","m","o"字符，必然就无法删除完毕。具体实现过程中，由于需要不断插入和删除字符，并且顺序上满足从容器顶部向下遍历，我们很容易想到可以用栈完成记录。我们读入字符串，然后遍历字符串中每一个元素，将其入栈，然后判断目前栈顶往下有没有可以删除的元素，一旦发现可以删除，我们就删去字串。遍历完成后如果栈非空，那么必然不可实现。

C：小红的矩阵计数

这个题目其实还行，数据范围比较小明摆着就直接暴力做法即可。由于是各种方向摆放的L形块，我们直接检测2*2的正方形即可。

D&E：小红的排序

两题并在一起讲解。放在前几期大概是D的位置，总体来说还是比较友好的。我们考虑对于一个1-based的升序排列，第 $a_i$ 个元素必然是 $i$ . 而题目中交换顺序只会往后，所以我们可以通过简单的举例得到一个结论：对于第 $i$ 个位置，如果元素不为 $i$ 且第 $i+x$ 、 $i+y$ 个位置的元素不为 $i$ ，即可判断最终不能得到升序序列。而具有能快速归类、判断是否为同一类型的数据结构的特征让我们不难想到可以用并查集维护。

具体地说，我们会创建并查集，然后遍历每一个位置。对于当前遍历到的位置 $i$ ，我们检查 $i+x$ 和 $i+y$ 的索引值是否合法，如果合法就加入同一个集合中。接下来，遍历从1到n的所有元素，如果当前元素和元素值作为下标的集合不在同一个集合，那么可以判断无论怎么交换都不会满足最后的要求。

F：小红的三角形构造

这应该算是一道数学题（）

由于是直角三角形，有 $a^2+b^2=c^2$ 性质，并且是给定一条边构造剩下两条边。如果有一些数学直觉，你应该能想到一种很简单粗暴的构造方法： $(a-b)^2+4ab=(a+b)^2$

所以本题可以有多种构造方法，下面展示一种思路。对于一个直角三角形的三条边，我们可以用下面的方式描述：

\begin{cases} a = n^2 - m^2 \\ b = 2nm \\ c = n^2 + m^2 \end{cases}

对于给定的x，分类讨论：

如果 $x$ 是奇数，我们令 $a = x = n^{2} - m^{2} = (n + m) (n - m)$ ，取 $n - m = 1, n + m = x$ ，解得 $n = \frac{x + 1}{2}, m = \frac{x - 1}{2}$ 计算出 $b, c$ 即可。
如果 $x$ 是偶数，我们令 $b = x = 2 m n$ ，取 $n = \frac{x}{2}, m = 1$ ，计算 $a, c$ 即可。

G：小红的生成树构造

首先，什么是生成树？简而言之，给你n个节点，你用一些边将他们全部联通。不难发现有一种最好的办法就是把所有节点编排在一条链上，而且对于一颗最小生成树，是不会出现环的。

我们首先要尽可能构造符合题意的连通块。根据题意，我们可以用一句话概括：把所有点分成两类，AB归为一类，CD归为一类，每一类的点之间自己联通，构成两个连通块，最后用一条边把两个连通块连起来即可。提到连通块想来已经有人想到并查集了（）在这里声明一下，由于连通块问题我们经常用并查集进行维护，所以下文提到的“集合”和”连通块“是同一个概念。

如何考虑无法构造？如果对于一种点，没有同一类的另一个点可以和它连接，那么就无法构造满足题意的图。我们可以用一点优化思想，对于ABCD四种点，可以用二进制状态压缩存储某个连通块里有的节点种类，如果某个连通块的种类数不为2，也就意味着这个连通块不合法，那么可以判断不成立。

在完成两类点的连接之后，我们会把两个连通块之间连接起来。所以最后构成了一个大连通块，且这个连通块的大小为n。所以最后，只需要判断任何一个节点所在集合的大小是否为n即可判断最终情况合法与否。

具体实现过程，我们先读入原来有的边，并检查这条边连接的元素是否符合上面提到的构造规则，如果符合规则并且这两个元素没有被加入并查集，我们将其加入并查集。如果不符合构造规则，这条边是额外的边，我们会先将这些边存储下来。

本题用到的并查集是魔改版本，我们会多维护一个数组，用于记录每个连通块的种类数（但是状态压缩版本）。具体来说，如果是A我们会设置对应的状态数为0，B则是1<<1，C则为1<<2，D则为1<<3；然后在合并过程中我们将集合u和集合v的状态数进行或运算即可。

接下来，我们遍历每个节点，检查节点属于的连通块种类数是否为2.我们可以用内置的biultin_popcount统计状态数中1的数量，由此推导连通块内节点种类数，只要连通块中节点种类数不为2，即可判断无法构造。处理完所有节点，我们再遍历存储下来的额外的边，把这些边连接起来。因为经过上文的推导，我们知道这些边可以让两个连通块连接在一起，所以这些边是有必要处理连接的。

最后，我们检查任意一个节点所属连通块的大小是否为n即可判断是否满足构造要求。