Fengwu Round - CSP 模拟 8
大概是最水的一次模拟赛了。
T1 Coprime 2
原题：ABC215D
直接质因数分解，复杂度为 \(O(n\log n)\)。
T2 Dist Max 2
原题：ABC215F
一眼二分，考虑如何在 \(O(n)\) 时间内实现 check 函数。
将每个点按 \(x\) 为关键字排序，然后双指针，在 \(x\) 满足的条件下检查 \(y\) 是否满足即可。
T3 Count Multiset
原题：ABC221H
考虑拆分数 dp，设 \(f_{i,j}\) 为有 \(i\) 个数，总和为 \(j\) 的方案数，如果不存在限制的话我们有一个转移：
\[f_{i,j}=f_{i-1,j-1}+f_{i,j-i} \]表示向序列中加一个 \(1\)，或者序列中所有数加 \(1\)，考虑加上限制的话就不能有连续 \(m+1\) 个 \(1\) 了，所以减去 \(f_{i-(m+1),j-i}\)。
T4 Julia the snail
原题：CF793F
以下标进行扫描线，吉司机线段树维护一个点能到达的最大值，然后对于每个以 \(r\) 结尾的绳子，在 \([1,l]\) 的地方如果能到达的位置 \(\ge l\)，则改为 \(r\)。
ZZ Round - CSP 模拟 9
垫底了。。。
T1 最短路
原题：[USACO09DEC] Cow Toll Paths G
按点权对点升序排序然后跑 Floyd，这样能满足路径的中间点的最大权值递增，因为 Floyd 只有枚举过的中间点才能作为路径中除了起点和终点的点存在。
T2 方格取数
原题：[POI2008] KUP-Plot purchase
先除去所有 \(\ge k\) 的点，然后在剩下的里面找到一个权值和最大的矩形，考虑将这个矩形一行一行删去，如果删的这一行权值 $ >2k $ 的话直接将这一行一个一个删就能得到答案，如果权值 \(x\) 满足 \(k\le x\le 2k\) 的话就是答案，如果不是的话继续删，一定能把剩下的矩形删成满足条件的。
T3 数组
原题：CF1114F
肯定是应用欧拉函数的通项公式：
\[\varphi (n)=n\cdot\prod_{p\mid n,p\in\mathbb P }\left(1-\frac1p\right) \]我们需要维护两个东西，一个是区间乘，一个是后边的质因子相关的东西。
观察到 \(a_i\le 300\)，然后 \(\le 300\) 的质数为 62 个，可以直接压缩到一个 long long 中，然后线段树维护区间乘区间或即可。
T4 树
根号分治，保证是排列的性质一点用没有。
如果步长 \(\le \sqrt n\) 的话，可以直接预处理，时间复杂度 \(O(n\sqrt n)\)。
如果步长 $ > \sqrt n$ 的话可以直接暴力跳，时间复杂度为 \(O(n\sqrt n \log n)\)（如果用长链剖分可以做到 \(O(n\sqrt n)\) 我在这里使用的是倍增）。
Max_QAQ Round - CSP 模拟 10
T1 Because
\(n=2\) 的情况没有判断，坑爹啊。
答案平凡，对于 \(n\ne 2\) 的情况下期望为 \(\displaystyle\frac{2(n-1)}{n}\)。
T2 Love
将每个数变成一个数对 \((x,y)\)，表示值和所属集合，按值排序，然后双指针，在满足区间内存在所有集合的数的情况下更新答案即可。
T3 yoU
考虑 \(k=2\) 的情况，其他情况就是乘上一个 \(\displaystyle\binom{n-2}{k-2}\) 罢了。
对于 \(k=2\) 的情况只需要考虑每条边做的贡献即可。
设这条边为 \((u,v)\)，其中 \(v\) 为深度较大的点，只需要考虑一个路径的两侧分别放在哪里能有贡献即可。
点权 \(w_u\) 定义为从父亲连向该点的边权。
设 \(siz_u\) 为以 \(u\) 为根的子树的节点数，\(ans_u\) 为 \(u\) 的子树内到 \(u\) 的路径上没有和 \(u\) 一样的点权的点数，\(top_u\) 为 \(u\) 的祖先中第一个和 \(u\) 权值相同的点，如果不存在为 0。
则 \(ans_u\) 求法如下：
\[ans_u=siz_u-\sum_{top_v=u}siz_v \]设路径两端选在 \(v\) 一侧的为 \(x\)，反之为 \(y\)。
\(x\) 的选取方案为 \(ans_v\)。
\(y\) 的方案分两种情况讨论：
- \(top_v\ne 0\) 选取方案为 \(ans_{top_v}\)。
- \(top_v=0\) 选取方案为 \(\displaystyle siz_{rt}-\sum_{top_x=0,w_x=w_v}siz_x\)。
T4 Everyday
在随机数据下能保证连续段不会太多，所以直接用线段树+ vector 暴力合并即可。
就是线段树维护当前区间能组成的连续段，pushup 的时候全部取出来合并即可。
Letitdown Round - CSP 模拟 11
Letitdown 学长还给方舟代抽，感动。
但是这个比赛状况的确有点多。。。
T1 原
原题：CF55D
之前做过，所以首 A 了。
其实是数位 dp 基础题，怎么维护都可以，在这里说一下我的做法。
\(1\sim9\) 的 \(\operatorname{lcm}\) 为 \(2520\)，所以考虑用这个进行状态压缩。
定义 \(f_{i,j,k}\) 为考虑到第 \(i\) 位，目前的数 \(\bmod 2520\) 的值，目前的数的 \(\operatorname{lcm}\) ，然后转移即可，因为目前的数的 \(\operatorname{lcm}\) 情况不多，压缩一下就可以了。
T2 神
原题：CF163E
有点水，感觉学过 AC 自动机就应该会。
AC 自动机插入时对于单词末尾打个标记，在构建失配指针时向下累加标记，查询的时候让那个字符串在 AC 自动机上跑，对于每个点的标记总数累加进答案。
如果要求更改删除的话，发现就是在对应字符串末尾位置的 fail 树子树内直接修改，所以写一个支持区间修改和单点查询的数据结构即可。
T3 启
考场上写出正解来了但是忘了交了（别人问我：你分挂哪里了？ 我：我挂后台了）。
假设序列以某种方式排序，先手选奇数位，后手选偶数位，并且都为最优策略。
然后考虑交换相邻项，然后就可以导出是按 \(a_i+b_i\) 为关键字排序即可。
时间复杂度 \(O(n\log n)\)。
T4 动
原题：CF932F
设 \(f_u\) 为 \(u\) 的最小答案。
我们可以简单写出它的朴素 dp 式：
\[f_u=\min_{v\in \operatorname{subtree}(u)}( f_v+a_ub_v ) \]然后发现如果将 \(f_v\) 看作 \(y=kx+b\) 中的 \(b\)，\(b_v\) 看作 \(k\)，则这两个变量确定一条直线，\(a_u\) 则为 \(x\)，那就是找这些直线在 \(x=a_u\) 的情况下的最小值，李超线段树合并即可，时间复杂度 \(O(n\log n)\)。
标签：le,原题,siz,top,学长,即可,复杂度,Rounds From： https://www.cnblogs.com/Rolling-star/p/17598537.html