(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 Laptop
可以先按Mi排成降序后，可以保证左侧的M一定比右侧的大。 对于每个j，如果有一个i，使得i<j且Si>Sj那么j就被“完虐”了。 所以我们只要排序后依次判断前面的最大的S是否比Si大就行了。
复杂度O（nlog2n）

T2 Distance
其实搞来搞去还是Manhattan距离，于是是经典问题。
我们可以设Xi=i2 Yi=Ai2 那么就是求Manhattan距离最远的两个点。
由于Xi=i2，所以我们其实可以直接用i来比较X的大小，那么按Y排序后，用2个线段树/树状数组维护Ai2-i2 和Ai +i的最大值即可。
复杂度O（nlog2n）

T3 Sum
算法一：暴力O(m*2n) 10%
根据询问的定义式枚举子集计算。
算法二：DP O(mnA)30%
每次询问可以暴力转移计算and后值为x的方案数。 通过n，m，A均较小的测试点。
算法三：线段树 O(nlog2n)50%
考虑Ai≤3的测试点，我们可以用线段树来计算方案数在线段树的update可以写成f(aand b)=∑f(a)f(b)，这样就快速计算DP值了。
算法四：二进制拆分+DPO(nlog2n) 80%
根据位运算的性质，各个二进制位上的运算是互不影响的，所以我们可以分开计算 对于m=1的点，我们可以对每个二进制位做一遍算法二中的DP。
算法五：二进制拆分+线段树 O(nlog22n) 其实我们把算法三和算法四结合起来就行了。
当只有01时，其实只需统计1的个数，方案数为(2x-1),用树状数组维护效率更佳。

T4 Fancy Signal Translate
算法一： O（n2ans） 50%+10%（福利数据） 由于答案一定很小，所以暴力枚举未出现的串去验证。 除了能通过复杂度计算中的50%测试点外，还可以通过10%的福利数据。
NOIP的数据一般是比较水的，暴力经常出奇迹，但是与这次不同的是，NOIP中 大力出奇迹一般是直接A题了。
算法二： O（nans+ans2ans）或O（nans+2ans） 100% 还是利用答案很小的性质，可以直接枚举答案长度。 对于每种长度，扫描字符串，2ans存储每种串有没有出现过 因为是01串，hash可以优化到O（n*ans+2ans）

T5 Factorial Surplus Tail
算法一： 最暴力的暴力 20%
直接把阶乘算出来数0的个数。
算法二： 较优美的暴力 40%
因为质因子2肯定比质因子5多（这个就不需要证明了吧），所以相当于统计质因 子5的个数，所以暴力可以写地更简单。
算法三： 分段打表 60%
我们可以每隔100W个数打个表，这样暴力复杂度为O(106)。
算法四： 类DP算法 100%
第一次DP，预处理计算[0，5k）的答案和0个数的奇偶变化，可以从5k-1转移。 可以观察下规律： （0表示偶数，1表示奇数）
k=0：0 k=1：00000
k=2：0000011111000001111100000
k=3：0000011111000001111100000000001111100000...... 有2种可能：
k是偶数，那么k-1是奇数，0个数的奇偶会变，ansk=3ansk-1+2(5k-1-ansk-1)
k是奇数，那么k-1是偶数，0个数的奇偶不会变，ansk=ansk-15
第二次DP，把n+1转化为5进制，从高位开始做。 然后我们可以分类讨论，例如当前位的数是3，当前位是奇数位，现在的奇偶性为
偶，那么转移答案为ansk2+(5k-ansk)*1，因为我们预处理的答案相当于从偶数开始， 然后奇数位会改奇偶性，分配给3段就是(ansk)(ansk取反)(ansk)。
每次复杂度O(log5n)

T6 Fantasy Strange Tree
算法一： 构树 30% 我们可以用某种方式把树构出来，然后枚举子序列在树上遍历。
表示出来的树的大小不会超过220。
算法二：构一部分树 50%
因为在树上遍历的范围只和操作串有关，所以构树时深度只要保留10层就行了。
算法三：特殊点讨论70%
操作没有U，也就是只会往下走，那么我们可以DP状态有4种，没有去过左儿子的点的个数，没有去过右儿子的点的个数，左右儿 子都没去过的点的个数，左右儿子都去过的点的个数。转移根据这个状态定义应该显然。
算法四：100%
对于U操作，我们只需做一些小修改。因为LR操作会和U操作抵消，所以我们的实际操作时的使用序列一定是这样的： UU...UUULRLLRLRLRLLRL.......
也就是U操作只会被用在开头，那么处于这个性质，我们可以对初始串（起点） 维护一个栈（维护LR方向），那么每次遇到U操作就取出栈顶，判断需要加入哪种新点。

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305