集训队作业 2020

开始做集训队作业，但是我是菜狗。

感谢 CYJ。

PART I

50 道很多，搞一个分割线。

树剖将字符串区间取出，然后一个一个匹配，匹配不了的就二分。我在 2023/3/23 依然不会 SA，只会哈希，没救了。代码。

二分答案，然后倒着做，设每一棵竹子初始高度为二分出的 $M$ ，然后每次减去 $a_i$ ，使得最终答案大于等于 $h_i$ ，并且过程中高度不能变成负的。直接贪心就行。代码。

这题，太牛逼了。不会。

环上的点是根本选不到的，剩下的可以分解成森林。如果一棵树连接着两个环那么连着的这些点就废掉了。

这样树可以变成有根树和无根树，都可以通过树形背包计算出选点的方案数，然后可以简单组合起来。代码。

两次 DFS 可以简单求出 $f$ 数组，然后开始神比了：

$f$ 最小的 $u$ 将其称为“中心点”，以这个点为根，一个子树中的节点一定比这个节点的 $f$ 大，因此将 $f$ 从大到小排序， $f$ 变小的过程中连通块的范围只会变大。
按照 $f$ 从小到达排序，直接双指针开扫，然后发现连通块只会不断合并，并查集维护即可。代码。

貌似是神仙同余最短路，省选以后填坑。

最后求的是乘积，因此 $3$ 操作的顺序是无所谓的。考虑将 $2$ 操作转化为 $3$ 操作（显然只会一开始赋值一次，转成加法即可）。对于加我们可以将其转化成乘上一个分数，分子是加上的东西，分母是前面加上的和（包括原来的数），乘法操作乘上的东西则都减去 $1$ 。

这样算的其实是增加的量，直接贪心即可。代码。

将问题转到一维上，就是问有多少个子区间满足 $\max-\min-\operatorname{len} = -1$ ，单调栈维护后缀最大最小值，扫描线加线段树维护答案。代码。

嘿嘿嘿！

求出最短路后直接 DP 即可。代码。

可能不更新了，以后的集训队作业会放在加训记录里。