ACGO 第8次排位赛题解
写在前面
本次排位赛为了让所有的同学都能够参与到排位赛中来，调整了所有题目的难度，并且对各个题目之间的难度差异做了一定的平衡。
从结果上来看，各个题目的通过率还是比较符合预期的。
但是对排位赛的难度调整很难一步到位，本场排位赛的 AAA 从通过表现上来说相对于 BBB 题要难一些。
本场排位赛的所有题目的难度评级为：
A B C D E F aaaccgo 矩阵匹配度 龟兔赛跑 二叉树叶结点的深度之和 棋子的气 普尔亚的委托 入门 入门 入门 普及- 普及/提高- 普及/提高-
入门难度的题目其跨度有时反而会比较大，后续对于排位赛的 A,B,CA, B, CA,B,C 三道题目的难度会做更好的平衡调整。
并且在本次排位赛中，发现了大家，尤其是第一次参加比赛的同学，对于排位赛题目的形式会有些不适应，一开始接触会有些不知所措，后面如果大家需要的话，会考虑出一份「Acgo排位赛参赛攻略」。
非常感谢大家参加本场排位赛！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
直播预告
直播时间：5月25日（周六）16:00 开始
直播地址：B站ACGO官方账号
直播内容：排位赛#8复盘
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - AAACCGO
首先使用以下方法将字符串 SSS 「去重」：
1. 从第二个字符开始遍历字符串 SSS；
2. 若当前字符和前一个保留的字符不相同，则保留该字符；
3. 若当前字符和前一个保留的字符相同，则不保留该字符。
去重后的字符串一定为 "acgo"\tt{"acgo"}"acgo"，否则说明不能够按照题目要求进行拆分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 矩阵匹配度
本题考查二维数组和取余。
遍历二维数组，将数组元素对 101010 取余得到元素个位上的数字，比较是否相等即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 龟兔赛跑
题目给出了乌龟和兔子的行进速度，并且特别的：兔子每跑 101010 分钟会根据自己和乌龟的位置来决定是否休息。
我们可以根据以上信息，按照时间顺序来模拟整场比赛：
1. rabbit 表示当前兔子跑过的距离；
2. turtle 表示当前乌龟跑过的距离；
3. i 表示当前时间；
4. 对于一般情况，我们使用「循环」模拟每分钟发生的事件：兔子乌龟都向前跑；
5. 每跑 101010 分钟，判断下兔子和乌龟的行进距离，如果兔子在乌龟前兔子开始休息，我们使用一个「子循环」来处理兔子休息时的事件：乌龟向前跑。
6. 不论是「循环」还是「子循环」一旦时间到达 NNN 分钟，立刻结束比赛，结束所有循环。
7. 根据 rabbit 和 turtle 的大小关系来判断比赛结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 二叉树的叶结点的深度之和
本题考查树的重构，根据二叉树的先序遍历和中序遍历，构建二叉树。
由于题目中给出的先序遍历和中序遍历不一定合法，所以我们首先思考，合法的先序遍历和中序遍历是什么样子的。
对于一个颗二叉树的先序遍历和中序遍历：
1. 令当前先序序列为 [preBegin,preEnd)[\tt{preBegin}, \tt{preEnd})[preBegin,preEnd)；
2. 令当前中序序列为 [inBegin,inEnd)[\tt{inBegin}, \tt{inEnd})[inBegin,inEnd)；
3. 当前先序序列的第一个元素即 preBegin\tt{preBegin}preBegin 上的元素，为当前子序列对应子树的根节点；
4. 在当前中序序列中找到根节点的位置 rootOfInOrd\tt{rootOfInOrd}rootOfInOrd，访问当前子树根节点；
5. 将当前中序序列以 rootOfInOrd\tt{rootOfInOrd}rootOfInOrd 分为左子树 [inBegin, rootOfInOrd)[\tt{inBegin},\ \tt{rootOfInOrd})[inBegin, rootOfInOrd) 和 右子树 [rootOfInOrd+1, inEnd)[\tt{rootOfInOrd+1},\ \tt{inEnd})[rootOfInOrd+1, inEnd) 两部分；同时可以获取左子树的大小 loLen=rootOfInOrd−inBegin\tt{loLen} = \tt{rootOfInOrd} -
\tt{inBegin}loLen=rootOfInOrd−inBegin 和右子树的大小 hiLen=inEnd−(rootOfInOrd+1)\tt{hiLen} = \tt{inEnd} - \tt{(rootOfInOrd + 1)}hiLen=inEnd−(rootOfInOrd+1)；
6. 根据左子树的大小和右子树的大小，将先序序列分为左子树 [preBegin+1, preBegin+1+loLen)[\tt{preBegin+1},\ \tt{preBegin+1+loLen})[preBegin+1, preBegin+1+loLen) 和右子树 [preBegin+1+loLen, preEnd)[\tt{preBegin+1+loLen},\ \tt{preEnd})[preBegin+1+loLen, preEnd)；
7. 重复以上步骤，直至先序序列和中序序列为空。
上述过程中，若发现当前的先序序列中元素和中序序列中的元素不匹配则说明序列不合法。我们可以使用集合 std::set 来完成这个判断。
对于本题我们需要访问所有叶结点，并统计叶结点的深度信息。
那么在构建过程中，带着参数 depth\tt{depth}depth 记录这一信息即可。若发现当前先序序列和中序序列的大小为 111，则说明序列中元素为叶结点。在递归的过程中，递归获取左子树的叶结点深度之和 loSum\tt{loSum}loSum，右子树的叶结点深度之和 hiSum\tt{hiSum}hiSum，loSum+hiSum\tt{loSum + hiSum}loSum+hiSum 便是当前子树中所有叶结点深度之和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 棋子的气
一颗棋子的气就是它上下左右 「空点」的数量。
若一颗棋子不和其他棋子共享气，我们直接统计下其周围的「空点」的数量即可；
如果棋子和其他棋子共享气，那么我们可以使用 DFS/BFS\tt{DFS/BFS}DFS/BFS 把这一整块共享气的棋子全部找出来，然后把这些棋子周围的空点数量 XXX 统计出来，那么对于这块共享气的棋子每个棋子的气都是 XXX。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 普尔亚的委托
提示1
* 如果 NNN 和 MMM 的范围为 [3,1000][3, 1000][3,1000] 如何解决这个问题？
提示2
* 每个遗迹的坐标具体是多少真的很重要吗？
如果 NNN 和 MMM 比较小的话，我们可以使用「二维数组」存储地图信息，把所有遗迹在「二维数组」中标注出来，然后在地图上做 DFS/BFS\tt{DFS/BFS}DFS/BFS 求「连通块」的数量即可。
但是现在 NNN 和 MMM 很大，我们完整无法去存储整个地图及遗迹的细节。
但是遗迹的坐标具体是多少，真的很重要吗？
不妨设想，这是一个可以放缩的地图。
那么可以发现，对地图放大或者缩小并不会影响其被分成几个部分的结果。
那么其实我们真正需要记录的只是遗迹之间的相对关系。
前后没有遗迹的行和列，并不需要被记录下来，不会影响答案。
所以我们可以使用「坐标离散化」的技巧：
对于每个遗迹我们只需要存储遗迹的坐标以及其前后的行和列就足够了，即：
Ai−1,Ai,Ai+1 (1≤Ai−1<Ai+1≤N)\tt{A_i - 1, A_i, A_i + 1\ (1 \le A_i - 1 < A_i + 1 \le N)}Ai −1,Ai ,Ai +1 (1≤Ai −1<Ai +1≤N)，
Bi−1,Bi,Bi+1 (1≤Bi−1<Bi+1≤M)\tt{B_i - 1, B_i, B_i + 1\ (1 \le B_i - 1 < B_i + 1 \le M)}Bi −1,Bi ,Bi +1 (1≤Bi −1<Bi +1≤M)，
Ci−1,Ci,Ci+1 (1≤Ci−1<Ci+1≤N)\tt{C_i - 1, C_i, C_i + 1\ (1 \le C_i - 1 < C_i + 1 \le N)}Ci −1,Ci ,Ci +1 (1≤Ci −1<Ci +1≤N)，
Di−1,Di,Di+1 (1≤Di−1<Di+1≤M)\tt{D_i - 1, D_i, D_i + 1\ (1 \le D_i - 1 < D_i + 1 \le M)}Di −1,Di ,Di +1 (1≤Di −1<Di +1≤M)。
这样地图上最多存储 6K×6K\tt{6K \times 6K}6K×6K 的信息对于本题 1≤K≤5001 \le K \le 5001≤K≤500 完全可以使用「二维数组」存储离散化后的地图。
然后将遗迹及其前后的 XXX 坐标和 YYY 坐标分别做离散化处理，保留他们的相对关系。
完成「坐标离散化」后，我们使用离散化后的遗迹对离散化后的地图进行标记，并在离散化后的地图上做 DFS/BFS\tt{DFS/BFS}DFS/BFS 求「连通块」的数量即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
