CSP考完打算写题解了
写题解有啥用呢，大抵是总结吧。。
~~总不能让博客一直没东西~~
~~第一场走丢了（确信）~~

10.25 模拟2 mp场

100+70+0+0=170 pts rk13

T3暴力 INT_MAX，给我输出了mp的题解密码（蚌），T4暴力没时间测就交了。
T1挺能签的，大部分时间花在 T2 上，T3T4 没咋想
T3 考场上想的DP但是不会转移。

T1 集训

首先按权值从小到大排序，然后我们一定是让平均数尽可能小，所以一定是选一个前缀，但全选不一定最优，所以从前往后枚举集合的右端点，每次更新平均数，然后可以维护单指针表示权值第一个大于平均数的下标，因为平均数单调不降，所以指针是单调的，除排序复杂度 $\mathit{\Theta}(n)$，也可以每次二分找。

T2 害怕

考场写了个树剖+线段树优化建图+两次拓扑排序+优先队列，怒写200+行，复杂度 $\mathit{\Theta}(n \log^2 n)$ 满，被卡70pts。

正解思路很简单，按照编号从小到大枚举每一条边，对于树边（蓝边）直接赋当前时间戳，对于非树边（白边）先将链上没有访问过的边按编号从小到大赋时间戳，再给该边赋时间戳，实现的时候使用并查集维护已经访问过的边，直接跳并查集根的父亲，这样总共遍历的复杂度是 $\mathit{\Theta}(n)$ 的，因为需要排序所以总复杂度还要带个 $\log$。

T3 负责

首先断开连通块就一定会出现一个位置左右两边都不包含，否则就会有交，考虑枚举这个位置（断点）。

先将区间按右端点排序，我们设 $dp_i$ 表示只考虑前 $i$ 个区间，以 $r_i$ 为一个断点符合要求的最大贡献，转移考虑枚举之后的一个断点 $j$，即所有区间都不包括 $j$，计算从 $i \to j$ 的区间选出前 $k$ 大的贡献，使用优先队列维护 $size$，时间复杂度 $\mathit{\Theta}(n^2\log n)$。

T4 分神

咕

10.26 模拟3 A层联测18

100+80+30=210 pts rk8

T1就想了半天，不知道埃氏筛复杂度，看着 $1e7$ 跑着差不多就交了。

T2出博弈论，以为不可做，后来想到了直径端点是必胜的，就可以反着推回去了，没看猜出来性质，打了个 $n^3$，~~但是数据太水了~~。

T3是 xuany 的T2，好像还比那个简单点，考场上没看出性质，打最低档暴力和特殊性质。

T1 新的阶乘

分别考虑每一个素数，对该素数能造成贡献的只有它的倍数，直接枚举每个素数的倍数，再枚举该倍数能整除它的次数，对于第 $x$ 个数，其次数为 $n+1-x$，累加答案即可，复杂度 $o(n \log\log n \log n)$。

T2 博弈树

60(80)pts:

博弈论，能转移到一个必败状态就是必胜状态，转移到的全是必胜状态才是必败状态，记住这句话就行。

设 $dp_{x,i}$ 表示当前棋子在 $x$ 点，下一步要走的距离需要 $ >i$ 是必胜状态还是必败状态，我们设直径长度为 $mx$，则 $dp_{x,mx}=0$，解释为不可能有长度大于 $mx$ 的路径，必败，对于每个询问 $x$，即询问 $dp_{x,0}$，考虑从后往前转移，转移时枚举每一个符合要求的点，lca 求距离要再套个 $\log$，复杂度 $\mathit{\mathit{\Theta}}(n^3\log n)$。

小优化：提前预处理每个点对间的距离，复杂度 $\mathit{\Theta}(n^2+n^3)$。

正解：

首先直径端点一定是必胜状态，那考虑删除直径端点得到一个新树（命名为 $t2$），那么 $t2$ 的直径端点也是必胜状态，因为先手可以先把棋子移动到 $t2$ 另一个端点，然后后手就会移动到原树的一个端点，且后手移动距离一定大于先手移动距离所以合法。这样一直删的话最后只会剩下一个（直径长度为奇数）或两个点（直径长度为偶数），前者该点先手必败，因为它不能自己跳自己，只能让给后手，后者都是先手必胜，所以只需要判断直径长度，若为奇数则判断该点是否为原树直径中点。

T3 划分

如果有长度 $\ge K$ 的 $0$ 前缀，最优情况就是后面的全放一段，计算前面划分出 $\ge K-1$ 段的方案数。

否则就一定是找最大的长度为 $n-k+1$ 的一段（整段），再把其它的单个划分出来（散段），枚举起始点，取模后如何比较两个二进制数的大小？

可以发现类似于比较字典序大小，一个方法是二分哈希找到两个 $01$ 串的最长公共前缀，比较其下一位即可，并且我们只需要比较整段而不需要比较散段，因为一个字符 $1$ 再整段里的贡献是 $2^i \ge 1$，而在散段里的贡献只能是 $1$，所以加上散段后贡献不会变劣，但是存在 $2^0=1$ 的特殊情况，即最后一位在整段和散段的贡献相同，我们的处理就是只要最长公共前缀长度 $\ge n-k$ 则判相等，累计方案数，否则再进行比较即可，时间复杂度 $\mathit{\Theta}(n\log n)$。

写自然溢出会被卡，不要写自然溢出。