模拟赛时间

T1

感觉好像有点眼熟
感觉要证明些贪心的结论啥的

不管了，乱搞
首先对于最大的元素，显然有答案要么是最大次大的和取模，要么是双指针搞定

得到答案后显然后续的模数都必须大于这个值，发现砍掉了很大一块
所以乱搞即可

T2

草，典
思考我需要什么
一个朴素的LCA，一个向上的 $2^k$ 级父亲的位置，一个向下的 $2^k$ 级父亲的位置
我还需要知道某个点往上的第一个 xx 点的位置，这个其实倍增顺带求解即可

T3

发现他要求的其实是“结束排名的可能顺序有多少种”
而我们知道一种排名想要合法，那么应该满足其最小的使用数小于等于m
考虑设 $f_{S,i,j,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次额外加的数为 $j$ ，总共额外加了 $k$ 的方案数

然后你发现其实 j 根本就没有意义，因为 j 显然与 $S$ 中的 $a_i$ 的最大值相等最好(或加减1)

所以就变成 $f_{S,i,0/1,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次的值为最大值是否加1 ，总共额外加了 $k$ 的方案数
应该就做完啦？

忘记一个条件了：$b_i$ 必须单调不降
那么也就是说，当我们产生一个 $b$ 时，后面的所有数都会吃到增益
我们发现这进而也就代表着“这一次的增大不会对后边的相对大小产生影响”
所以直接先一步统计即可
所以 $j$ 确实没什么用，我们用 $f_{S,i,k}$ 表示即可

晚上练习题：链接

T1

主席树乱搞

T2

感觉有点神秘

是不是可以按照dfs序双指针着选择相邻两个不同集合的节点？

考虑设每个节点的贡献为 “其能够选择的深度最大的LCA”

那么显然这个 LCA 一定位于其的祖先上

所以倍增的找到第一个满足子树内有另一个集合的点即可

T3

有点唐了

看到同时移动很本能的就能想到二分答案

显然每个点一定越往上越优

特别的，当一个点能到达首都时，他就需要做抉择——到哪个首都的子节点上

剩下的其实就是一个叶子节点区间染色问题，dfs序即可

T4

典

T5

怎么做过啊（

显然的一个序列分割问题

设 $f_{i,j}$ 表示当前在点 $i$ ，不和谐度和为 $j$ 的方案数

转移方程是好想的

$$f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-\max{a_{i,k}+\min{a_{i,k}}}}$$

晚上聊了一下，感觉最近还是把dp / ds 搞好为重

部分分大概率也不会以很难的形式给出，所以要尽可能的不被拉开差距

接下来重点练习些 CF2000* 的 dp 题，尽可能的将思维转化这一步做好

目标在进队，银牌，并不需要过难的知识点

尽可能的不要犯错，不 nt 就是赢

再开一题：Dp

其实就是问你能构造出多少个数组 $a$ ，使得其满足对于所有的 $A_i$ 都有“其中的每个元素都被且仅被一个该串包含”

发现若一个 $A_i$ 中有重复元素，那么必死

对于两个 $A_i$ ，若他们有相同元素，那么必定两两拼接，若不能拼接，则死

剩下的情况那就是序列分割，中间插入未出现过的元素

然后就做完了？