小W的增长信心赛~Solution以及弱省蒟蒻出题人的感想

作为一个辣鸡，最近找不到做题的动力，而且被友校同学出的题目摁在地上摩擦，于是我在Luogu出了一套水题礼尚往来，这里是这套水题的题解。
Luogu上的地址：点我

Problem A：对战怪函数（Strange）

算法一

注意到区间的最大值一定在计算答案。
期望得分：20分

算法二

在算法一的基础上，在枚举区间的同时，计算区间最大值。
期望得分：40分

算法三

注意到，以一个数为最大值的区间，左端点一定在这个数往左最近的一个比它大的数的右边，右端点一定在这个数往右最近的一个比它大的数的左边。因为所给的数列是一个排列，所以不会有相同元素，所以我们对于每一个元素，找到它左边最近的比它大的数的位置个。
因此对于每一个位置，暴力向左右寻找。
期望得分：50分

算法四

在算法三的基础上，用一些神奇的东西（如线段树、树状数组、set或一些本蒟蒻不知道的奇技淫巧）维护，时间复杂度为。
期望得分：80分

算法五

在算法三的基础上，想办法加速查找的过程。
有一个利用一种叫单调栈的数据结构的算法：从左往右依次将元素入栈，对于每个元素记录两个值。
实际上我们要查找的。
期望得分：100分

Problem B：狂虐位运算（Sum）

算法一

暴力计算所求的异或和，时间复杂度。
期望得分：20分

算法二

我们可以计算每一位对答案产生的贡献，从右往左第。
期望得分：40分

算法三

我们只需想办法求每一位上为？
考虑数位DP的思想，对于呢？
我们发现，对于在。
如果听不懂我上面在说啥，讲一个例子：，那么我们考虑以下区间：
对于右往左第；
对于右往左第；
最后我们还需要计算。
这样应该就能很明了地看出应该如何计算了。
期望得分：70分

算法四

在算法三的基础上，分别计算从左往右和从右往左的贡献，并在计算的同时累计贡献，这样就可以做到的复杂度。
期望得分：100分

Problem C：修建地铁线（Subway）

算法一

分析题意，题目中要求的显然是，将，直接输出这个结果即可。
期望得分：20分

算法二

进一步分析，能用且至少需要用条没有公共边的路径覆盖。因此采用搜索的方法枚举方案或者打表可以通过测试点#3~#5。
期望得分：30~50分

算法三

通过算法二中的分析，注意到这是一个有关于构造一些点满足某些度数限制的情况下的树的方案数的问题。这时候需要用到一个叫做Prufer序列的知识。
对于一棵无根树，我们可以构造出它对应的Prufer序列。构造方法是：每次将编号最小的叶子节点删去，然后将该点所连接的那个节点编号记录在序列中，这样重复的序列，这就是这棵树所对应的Prufer序列。
可以证明树和Prufer序列之间是一一对应的关系（证明可以看看Matrix67大佬的文章）。那么当然也存在一种方法能从Prufer序列反回去构造无根树，不过由于篇幅限制这里就不讲了。
从上面大佬的文章中还可以得出一点：若一点在Prufer序列中出现
边界条件为，可以通过这一道题。
期望得分：100分

Problem D：攻入核系统（System）

算法一

用DFS或BFS预处理每个点到其他点的距离，然后暴力修改和查询，时间复杂度。
期望得分：20分

算法二

每次修改和查询时，暴力搜索周围在范围内的点，进行修改和查询。
期望得分：30分（多10分是因为#4太水）

算法三

对于测试点#3~#4，暴力分类讨论统计答案。
期望得分：40分（配合算法一）

算法四

我们先将无根树转化为有根树，然后发现，当个部分：询问点的父亲，询问点，询问点的儿子。我们发现一个点的儿子在树的BFS序上是连续的，所以先用BFS预处理，然后用线段树维护区间和即可。
期望得分：60分（配合算法一、三）

算法五

在算法四的基础上，我们讨论个部分：询问点的父亲的父亲，询问点的父亲，询问点父亲的儿子，询问点的儿子，询问点的儿子的儿子。每个部分中的点在树的BFS中都是连续的，所以用线段树维护即可。
期望得分：100分

感想

啊，作为一个弱省的蒟蒻，能出出这种题很不容易啊……以及第一题和第四题的数据真的好难出啊，当时就觉得，就算出成这样估计也会被艹的很难看，于是就弃疗了……
（结果因为各种撞题成功中道崩殂……）
不过还是感谢验题人一直以来的坚持，让我多考虑了几种可能会被艹的姿势（雾），而且验题人貌似写出来了第四题线性做法，然而我并不会，所以题目数据范围就没开到那么大。
至于题目英文名的四个S……本来的英文名其实并不是这样的，然后突然想到可以这样设计，于是就改成这样咯~S有Super之意，也算是给诸位图一个吉利吧。
（标题写成Solution也是故意的hhh）
那么，就这样啦，感谢大家对我比赛的支持！以及感谢你一直看到最后！