【题解】牛客练习赛63

A 牛牛的三角形

难度：签到题
大力for,或者一个更优的算法，先sort然后枚举相邻的三项判断是否构成三角形。

B 牛牛的鱼缸

难度：签到题
初中数学题，利用相似三角形求解。
注意分情况讨论以及h和l不要看反了（看反了也能过样例）。

C 牛牛的揠苗助长

难度：中等题
先考虑一个简单的版本，假设水稻不会生长，问最少操作几次使得所有的水稻高度相同？
这个就是一个经典题了，首先结论是：最优策略一定是将所有水稻都向某一个水稻看齐，也就是至少有一颗水稻是不用动的。
原因如下图：

首先按照水稻的高度大小排序，假设你将所有水稻都调整到的值为x，且x不与任何一颗初始输入的水稻高度相同，那么要么你将其调整到x-1更优，要么你将其调整到x+1更优。
当然也有特例，也就是n为偶数，且x整好在(a[n/2],a[n/2+1])范围内调整时，不过此时范围内所有的x都是最优解，也不影响此结论的正确性。
有个这个结论就好求解最小次数了

如图，求阴影部分面积，

回到这道题目水稻会生长了怎么办。
首先想这么一点，假设经过无限长的时间后，我终于将所有水稻都调整到了一样高，这个同样高的高度是否能持续保持？
显然是可以的对吧，因为每一天都仅有一个水稻的高度长高，所以我只要将自然长的水稻给他摁回去，就能一直保持他们都是同样高的。

也就是说明，此问题在答案天数上面具有单调性，若在水稻生长的条件下，仅用ans天就能够使得所有水稻都保持同样的高度，那么比ans多的天也一定可以。
所以就二分答案天数，检查是否能够全部调整成一样的就好。

因为已经确定了天数，那么我们就知道第i颗水稻一定生长了ans/n+[i<=ans%n]，所以就给每个水稻都先加上，但是因为大家都加了ans/n，所以反倒别加不然会爆掉。
既然水稻的高度已经确定，那么利用前面说的，用前缀和就可以求出此天数下的最小操作次数。
只要最小操作次数<=答案天数，就是合法的。

D 牛牛的01限定串

难度：中等题
这道题直接写DP就行了，也没什么难点。
说是这么说，但是实际上新手或者一些DP苦手的选手在写这种DP的时候还是可能会找不到突破口。
多做DP积累模型是学习DP一个很重要的部分。
这里就介绍一种模型吧，这种模型多用于01串，括号串，这种字符集为2的字符串，最好它的个数再给定。
先简化一下问题，假设下面给的t串全部为"?"，也就是只有“0”，“1”的个数有限制，对于放在哪里无限制。
假设现在有n个0，m个1让你填。
首先，拿出你的草稿纸，在上面画出一个n+1行m+1列的棋盘，行列下标从0开始计算，左上角为(0,0)。
我们就用题目中的样例1举例吧。

8 6 2 1 1
10110011
????????

样例1中n=6,m=0。
所以如图所示，画一个6+1行3+1列的棋盘，行列下标从0开始计算，左上角为(0,0)。

现在我问你，从左上角走到右下角有多少种走法？好的，是C(8,6)种。
那用6个0和2个1组成本质不同的字符串，有多少种？巧了，也是C(8,6)种。
所以假设你手中有一支笔一开始划在最左上角，然后你从头开始，每放一个0你就同时往下划，每放一个1你就同时往右划。
显然的是，如果你当前在棋盘中的位置坐标是(x,y)，那么我就非常清楚你已经放了x个0和y个1。
那么题目中的“前缀相似”，就可以在棋盘中先按照这个给出的s串走一遍

那么这条路径路上的点，只要我在构造01串时经过，就会获得权值。
同理“后缀相似”只要我倒着爬一边，就能知道哪些格子上的权值需要增加了。

那这个问题就又变成了经典的“过河卒”或者“传纸条”问题。
也就是从左上角走到右下角最多/最少能够获得多少权值，的问题。
那有01限制条件必须放0或者必须放1的位置，你就可以理解成“过河卒”问题中必须往下走或者必须往右走。
这个题目在使用此模型转化后变成了最最最简单的DP。

E 牛牛的斐波那契字符串

难度：中难题
先说一个神仙解法...神仙一看，斐波那契数列是线性递推，那斐波那契字符串匹配也可能是线性递推。
所以写了个暴力，外面接了一个杜教BM，然后就...AC了。

那说一下这个为什么是线性的吧，首先假设我们进行了足够多的“斐波那契”操作之后
观察字符串的前缀发现

观察字符串的后缀发现

仅有两种前缀和一种后缀
然后如果字符串足够长（比t串还要长）的时候。
中t串出现的次数就是他在中出现的次数+他在中出现的次数+的后缀与的前缀后匹配t的次数。
那显然因为只有一种后缀和两种前缀，所以转移方程为
dp[i]=dp[i-1]+dp[i-2]+(i为奇数)
dp[i]=dp[i-1]+dp[i-2]+(i为偶数)
与利用kmp求的。

如果WA了的话，此题的坑点在于，无论和是不是一开始就远长与t串，你都要先接一次。
因为只有的后缀为A，而非...BBAB，也就是此时转移方程是不适用的。

F 牛牛的树行棋

难度：中难题
树上的问题，有一种切题的切入点是将树分成两种情况。
1、单链  2、分叉
本题也使用这种思路，首先只考虑胜负，分成两种情况。

1、单链

如图，在树仅有单链时，可以等效成nim博弈，可以把棋子看成是堆，把棋子还能向下走几步看成是这堆物品还有多少。

2、分叉

做这种题一定要注意“等效”，对于有分叉的节点，假设分叉之后是单链。
那么现在下边的节点被等效成nim博弈中的几堆已经确定了，我们来看棋子放在最上边的节点时等效成一堆几个？
你发现你可以通过你的操作，将其转化成等效“一堆0个”，“一堆1个”，“一堆2个”，“一堆3个”。
问题来了，那一开始它等效几堆？显然，“一堆4个”。
因为只有一堆4堆才能通过取走一个或者多个物品，转移到一堆0个，一堆1个，一堆2个，一堆3个。
那么“等效几堆”就可以用树形dp求的，转移方程为

这个定义其实也就是“子树的深度maxdeep”的定义。
所以先求maxdeep，就转化为普通的nim博弈了。
普通的nim博弈怎么求方案数呢？nim博弈说，如果所有数字的亦或和不为0，先手只要找一堆取走Xorsum个，就是必胜的策略。
问的题来了，现在只有“等效几堆”，那我还得知道“等效取走”了几个。
那其实也简单，如果我通过某种操作使得，棋子的状态从“等效一堆x个”，转移到了“等效一堆y个”。那实际上这个操作等效取走几个？
这个操作也就等效“取走了x-y”个。
也就是说方案数等于
枚举每个节点覆盖的子树范围，求子树中maxdeep等于xor_sum^max_deep[x]的数目。
前提是能够取得走，也就是必须保证max_deep[x]>=(xor_sum^max_deep[x])。

接下来问题就转化成了“查询子树中权值等于x”的节点数目。

另一种思路就是大部分选手使用的SG函数，然后我本人是不会SG函数的（平时碰到直接扔sjf了），可能需要各位大佬在评论区补充一下。