【题解】牛客小白月赛36

前言

出题人：(ABC)Flash_plus、(DEFG)沙烬、(HIJ)hx073269
三毒瘤一拍即合，于是这场小白赛就孕育而出啦，希望大家玩的还算开心。
B题数据弱了，赛后已加强。

正文

A-好哥哥

考点：贪心
我们可以对括号序列进行建树操作，即：对于每对括号向他的好哥哥连边。你会发现，对于每对括号，我们可以走的其实就是他的祖先以及他的儿子，代价都是一样的。那么题目就可以转化成：在一颗树上，我们从根节点出发，规定步数内，最多可以遍历多少节点。
考虑最后的整个路径是一段重复的边，再加上一条从根开始的链。那么这个可以贪心，把两边的贡献分开考虑：对于那些需要重复的路径，代价是2 $\times$ (节点数 - 1)；对于最后那条链，代价就是链的长度 - 1。那么贪心策略很明显，找出最长链，其他随意遍历，最后跑完最长链就行了。
时间复杂度： $图片说明$ 。

B-最短串

考点：字符串匹配
首先判断一个字符串是否为另一个字符串的子串，如果是则答案为这两个字符串长度的较大值，否则进行以下操作：
设字符串 $a$ 的前缀与字符串 $b$ 的后缀的最大匹配长度为 $len1$ ，字符串 $a$ 的后缀与字符串 $b$ 的前缀的最大匹配长度为 $len2$ ，那么不难发现答案就是 $|a|+|b|-max(len1,len2)$ 。所以我们可以暴力枚举这个最大匹配长度，然后再判断相应长度的前缀和后缀是否匹配即可。
时间复杂度： $O(|a|\times|b|)$ 。

C-杨辉三角

考点：组合数学
题目可以转化成这个样子：

$\sum\limits_{i=1}^ni^2\binom ni$

那么推一波柿子:

$\sum^{n}_{i = 1}{i^2\binom ni} =$ $(\sum^{n - 1}_{0}{\binom {n-1}i} \times (i + 1)) \times n =$ $(\sum^{n - 1}_{0}{\binom {n-1}i} \times i + \sum^{n - 1}_{0} \binom {n-1}i) \times n =$ $(2 ^ {n - 2} \times (n - 1) + 2 ^ {n - 1}) \times n =$ $2 ^ {n - 2} \times (n + 1) \times n$

注意本题是从 $0$ 到 $n-1$ ，所以就是相当于求 $该柿子$ 的值就可以了。
时间复杂度： $O(log(n))$ 。

D-哥三好

考点：动态规划
总共三个人，每次三个人都有可能请客，对于该次请客我们只需要记录三个人未请客之前的情况方法数，加起来即可。所以最朴素的思想便是建立一个三维的DP，然后采用数字三角形模型递推即可。由于最低消费都是300/450/750，可以看到都是150的倍数，所以我们可以提前除掉150减少数组的大小。由于最后剩下150也请不了客，所以我们还需要加上人剩下钱的数目。
时间复杂度： $O((a/150)*(b/150)*(c/150))$ 。

E-皇城PK

考点：签到
简单来说就是有人输过，就会发生实力和别人相等或者比别人低的情况，所以只需要记录没有输过的人即可，这里我们可以用桶纪录输过的人。
时间复杂度： $O(n+m)$ 。

F-象棋

考点：思维
首先炮的攻击方式能保证结束的时候每一行最多不超过两个炮，这样我们可以先选取两行的跑，利用这两行去消灭其他行所有的炮（虽然炮消灭敌人会到敌人的位置，但是我们也可以反过来，让需要被消灭的跑打过来，这样该位置的炮就被消灭了）。然后在这两行里选取两列，重复上述操作，最后只会剩下两行两列，最多四个。
时间复杂度： $O(T)$ 。

G-永不言弃

考点：拓扑排序+优先队列
首先一定要从第一个关卡开始打，如果第一个关卡都打不过去一定无法通过。其次每次通过一个关卡，都会获得一个道具，这个道具可以帮助我们通过其他关卡，所以我们可以将其他关卡的通关属性变成0，这样遇到该关卡时就一定能通过。我们每次保证先打当前解锁关卡中关卡属性需求最小的，这样如果打不过我们肯定无法通关，如果能打过，则将能解锁关卡打完。打完后由于游戏需要通过全部关卡，所以我们检验一遍是否通过了全部关卡即可。
可以用优先队列解决本题。
时间复杂度： $O((n+sum(k))*log(n))$ 。

H-卷王之王

考点：暴力
首先我们得发现，每个数被加一次，至少倍增，因此每个数最多进行 $O(log(x))$ 次加法。所以我们可以使用一个优先队列去暴力模拟这个过程，把所有小于等于 $x$ 的数弹出来，对他们加上 $x$ 后再加入优先队列。注意数据范围是非负整数，因此对于 $x$ 为 $0$ 的情况我们直接跳过不处理，否则会导致超时的情况出现。
另外还有其他解法也可通过此题，但是从内测情况来看该题错误率较高，主要是因为数据中 $0$ 的情况导致的。对于无法通过此题的选手，可以思考一下是否是含 $0$ 的情况导致了程序错误。
时间复杂度： $图片说明$ 。

I-四面楚歌

考点：搜索
简单的搜索题。我们使用DFS可以判断一个连通块是否是能够移动出边界的连通块，如果是我们则对这块连通块染色，最后统计所有染色的联通块内 $0$ 的个数即可。
时间复杂度： $O(n\times m)$ 。

J-科学幻想

考点：线段树+字符串hash+二分
首先思考一下不带修改的版本如何做。对于判断两个字符串相等，我们可以使用字符串hash算法实现。但是题目要求的勉强相等，允许有一个字符不同。我们二分字符串的长度，对于每次的mid来说：
1.如果 $[l1,l1+mid-1]$ 区间的hash值不等于 $[l2,l2+mid-1]$ 区间的hash值且 $[l1+mid,r1]$ 区间的hash值不等于 $[l2+mid,r2]$ 区间的hash值，则证明两个字符串左区间和右区间都至少存在一个字符不同，即两个字符串不算勉强相等。
2.若只有 $[l1,l1+mid-1]$ 区间的hash值不等于 $[l2,l2+mid-1]$ 区间的hash值，则证明不同字符在左区间，令 $r=mid-1$ 。
3.若只有 $[l1+mid,r1]$ 区间的hash值不等于 $[l2+mid,r2]$ 区间的hash值，则证明不同字符在右区间，令 $l=mid+1$ 。
通过字符串hash+二分的做法即可判断两个字符串是否勉强相等。至于带修改的版本，使用线段树维护区间hash值即可实现。
时间复杂度： $O(n\times log(n)+m\times log(n) \times log(n))$ 。