8.30 属于是在家调整的时间所以没做题，那么这一周的总结就是8.31-9.3的总结

8.31

T1是离谱的组合计数，于是对于形状奇怪的组合数可以考虑对分子和分母提出来一些东西变成其他的组合数，然后求个和考虑组合意义就可以拼成一个新的组合数

T2是NOIP2021D1T1的加强版，事实证明我对于字符串的模拟题练的还不够

T3是困难的gcd卷积。

T4考虑发现一些性质，把问题转化成矩形然后使用LCT动态维护最小生成树。

9.1

T1发现每个人给同样的球相当于都没给，所以至少有一个人没有给出球。然后每次指定前边所有人都给了球，DP。优化就是加个预处理然后用矩阵优化转移。

T2由于小区间不重叠且c很小，容易发现最终状态数较少，考虑寻找第k小的反转结果，用deque维护一个预处理，使用二分实现就可以了。

T3考虑伴随子集的性质，容易发现所有的小序列的伴随子集必然是整个大序列的伴随子集，于是所有小序列中都应该包含原来大序列伴随子集中的所有元素，用DP转移即可。

9.2

T1是友好的大模拟，~~但是因为没有大样例挂到0分祭~~，错因是装弹的细节（语句顺序写反了一个），以及 输出执行引起错误的语句之前的状态 ，而我输出了错误时的状态导致爆零。其他的实现一次写完也没出什么错。给的唯一的小样例不光连所有操作都没覆盖全还跑到一半就error，结果啥都de不出来，写完之后还肉眼看出三个错（然后依然挂到0分）-_-。 OI赛制下没有大样例的大模拟千万别碰，全是坑QAQ

T2一个图论题，发现可以用二位前缀和预处理出来每个点的尺寸值，在DIJ的过程中把尺寸当成第二关键字就行。

T3结论题，可以用线段树维护区间立方模的修改，查询区间长度大于等于14时一定有解，否则可以考了折半搜索，复杂度可以接受。

9.3

T1简单题，好像咋写都能过，预处理阶乘计算组合数然后离散化一下值域扫描一遍统计贡献就行。

T2注意最终的特殊点就是起点，即必须回到起点。设一个f二维数组表示x个单位时间距离起始点y个单位距离的方案数。

T3是找循环节的题，每个循环节内部可以快速求解。

by Pozhu
2022.9.4