由于集训队作业出来了，所以这篇文章就不再更新了QwQ
\(\color{red}{\bullet}\) 是抄的题解
10.8
[PKUWC2018]随机游走 \(\color{red}{\bullet}\)
显然用 \(\min-\max\) 容斥将所求变成到达一个点集的最早期望时间。考虑最早时间如何求出，对于一个点集 \(S\)，不妨设 \(f_x\) 为 \(x\) 内的点到 \(S\) 的最早期望时间。 则对于 \(x\in S\) 有 \(f_x=0\)。
对于 \(x\notin S\) 有
\[ f_x=1+\frac{1}{\deg x}\sum_{(x,y)\in E}f_y \]
这样需要高斯消元，但考虑到本题的树形结构，我们以起点 \(x\) 为根，通过一次函数来分离父子关系，即设
\[ f_x=A_x\times f_{fa_x}+B_x \]
那么对于 \(x\notin S\) 即可改写为
\[ f_x=1+\frac{1}{\deg x}(f_{fa_x}+\sum_{y\in son_x}(A_yf_x+B_y)) \]
化简得
\[ \begin{aligned} A_x&=\frac{1}{\deg x-\sum_{y\in son_x}A_x}\\\\B_x&=\frac{\deg x+\sum_{y\in son_x}B_x}{\deg x-\sum_{y\in son_x}A_x} \end{aligned} \]
显然对于起点 \(x\) 而言，\(f_x=B_x\)，对于 \(x\in S\) 而言 \(A_x=B_x=0\)。
之后就是一个高维前缀和了，复杂度 \(O(n2^n\log P+q)\)。
CF1422F Boring Queries \(\color{red}{\bullet}\)
这道题就类似于在线区间数颜色。先离线考虑，会发现确定右端点后存在一个类似单调栈的结构，用主席树存下来就行了。
CF1422E Minlexes \(\color{red}{\bullet}\)
会发现题中的最优化具有最优子结构，直接 dp 就行了，比较字典序大小的时候大力猜结论，需要比较的前缀一定都是同一个字母就好了，或者封装一个哈希表。
CF1422D Returning Home \(\color{red}{\bullet}\)
降智题，自己写的时候优化建图写歪了。正解就是排序后按顺序连边。
[10.8模拟赛] 石子游戏 \(\color{red}{\bullet}\)
根据 \((x-y)_2{[j]}=(x-y-k\times2^{j+1})_2{[j]}\) 进行合理的后缀和加减即可得出。
10.9
今天什么是也没干，帮学弟写完题解之后就一直在颓颓颓，就把题解搬到这里吧。
签到题
考虑最优解的形态，一定是一个字符依次非严格递减且最长的序列，用单调栈维护即可，也可以存一个后缀最大值暴力跳。复杂度 \(O(n)\)。
送分题
题目来源 [EER1]代价。
通过观察样例，我们不难得到一个较优解，它的值为：
\[ \sum_{i=1}^{n-1}a_i\times a_{i-1}+\min_{i=1}^na_i \]
我们记最小值的位置为 \(p\)，则这个解的一种构造方式为先删除 \(1\) 到 \(p-1\) 的数，在删除 \(n\) 到 \(p\) 的数。我们注意到 \(a_i\times a_{i-1}\) 无论以什么方式删除，至少都会产生一次的贡献，因此这样构造已经比大多数情况优了。考虑少数情况何时取到，注意到满足
\[ a_{i-1}\times a_i+a_i\times a_{i+1}>a_{i-1}\times a_i \times a_{i+1} \]
时这种构造就不够优秀了，此时 \(a_{i-1}\le 1\) 或 \(a_{i+1}\le 1\) 因此我们以 \(1\) 为分界点，重复上述构造即可，复杂度 \(O(n)\)。
白给题
依旧是考虑最优解的形态，不难发现最优解一定是从 \(X\)先走一段 \(X\) 到 \(Y\) 的最短路，再走 \(0\) 边，通过 \(X\) 到 \(Y\) 的最短路走到 \(Y\)。若出现中间交错显然不优，所以我们建立
\(S-T\) 的最短路图，在上面
dp 即可。
简单题
题目来源 [MtOI2019]恶魔之树。
一个很粗糙的想法就是先离散化，记 \(x\) 出现次数为 \(c_x\) 则若它被选中有 \(2^{c_x}-1\) 的贡献，然后状压质因数的次数。从这个想法出发，如果我们只关注 \(\le\sqrt{300}\) 的 \(7\) 个质数，对他们的指数进行状压，剩下用 \(0-1\) 背包的形式添加贡献就可做到 \(O(300\times9\times6\times4\times3\times3\times3\times3)\) 的复杂度。
具体的就是设 \(f(i)\) 表示最后子集 \(\le\sqrt{300}\) 的质数构成的数为 \(\prod p_k^{i_k}\) 的带权方案数，这里的带权是指它会带上那些 \(>\sqrt{300}\) 质数的权值。我们对于 \(>\sqrt{300}\) 的质数一批一批的考虑，记当前考虑的数为 \(p\)，那么我们把所有 \(p|x\) 的 \(x\)，先带上 \(2^{c_x}-1\) 的贡献，加入到这个 \(\max\) 卷积的背包中，最后统一乘上 \(p\) 即可。注意实现过程中的不要出现自己更新自己的情况。