集训队作业泛做

题解

感谢vfk,xhr等老司机的题解

我已经做了$9$题

235C
$WJMZBMR$老司机出的$SAM$裸题，将模式串$x$倍增然后在串$S$的$SAM$上跑一跑即可。

241E
差分约束系统
设$dis[i]$为$i$到$n$的最短距离
首先把$1$不能到的点和不能到$n$的点删去，然后只要剩下的边 $(u,v)$满足

251D
高斯消元64次，由大到小先强制加入使第$i$位贡献为$1$的方程，然后因为要最小化$x_0$，我们再由大到小强制加入使得第$i$位贡献为$0$的方程，详见跳蚤国王题解

323C
主席树裸题，1A

261D
注意到$max_b$不大，于是我们对每个元素记录当前可以从第几项开始更新。

BZOJ 1597
斜率优化入门题，去除冗余再推一推式子即可。

123E
期望题，结论是$n$个点的树从任意根走到任意叶子（$根\neq 叶子$）$dfs$走过的边数为树的总边数（即$n-1$）（证明见胡渊鸣课件或者国家队论文）。于是这题dfs一次然后每个点单独统计即可。

17E
回文树裸题，但是十分卡空间，把$next临接矩阵$改成$链式前向星$才卡过去。

266E
先感谢yanQval大爷让我验了他的NOI·professionalNOIP模拟题，然后这题就是用线段树维护$a_i*i^k(0<=k<=5)$.略微卡常。