2025 长训第四周 (1015 to 1020)

任何时候每个点相连重边数不超过 2

1016【模拟赛 #10】

有一些小把戏还是被卡了一些时间。以及 T1 对着看错的题目想了半个多小时。

相当于放一些区间将其覆盖。可以预处理出经过区间 $[l, r]$ 背包体积为 $v$ 的价值，然后 dp 目前到第 $i$ 个位置，用了前 $j$ 个背包的最大价值。

然后发现因为物品只有两百个，所以背包只有最后面两百个有用。然后就能过了。有点恶趣味。

显然，初始排列 $[1, 2, 3, \dots, n]$ ，选一个点集将其循环右移，发现消耗 $r - l + c$ ，其中 $c$ 为区间内没被选的数个数。

那我们枚举每个区间，在满足要求的情况下最大化选的个数，这样就可以了。

这题出在这是何意味，暴力跳跳跳完事了，加个倍增就可以正确了。

agc068_c

搞笑，T2 忘分讨一种情况，挂成 14 分了。

赛时有点搞笑，虽然有一瞬间闪过二分的念头，但是没仔细想，后面瞎分析 30min 无果后再想了一下二分，发现果然有单调性，然后二分就行了。

容易发现最优分法一定是整个序列被分成三个连续段，由于又是个环，所以只有两种本质不同的方法，枚举限制最大的组的元素个数再瞎判一下就行了。

直接对着整个序列 dp 没有什么前途，我们先分析一下相邻两个出入事件对答案的贡献。

分析一下容易发现，现在组成了若干条链。对每条链分别做 dp：直到 $i$ ，当前已经分配了 $j$ 把钥匙， $i$ 分没分时的答案。

如果给一个点分配的话，就把它的单点贡献加上；与此同时如果前面的点也有贡献的话，就把连接它俩的边的贡献也算上。

具体实现时可以把若干条链直接用权为 0 的边串起来，这样子就可以直接一起处理了。

直接做即可

特判掉其中有一维是 $1$ 的情况，然后发现操作次数即为经过的连续 $1$ 段个数，这个可以直接 dp。

差一点场切紫了，幸好时间不够我卡常以及改一个小地方！

考虑答案如此形成：一个子树内的直径加上去掉这棵子树之后剩下的树去掉根节点之后的若干连通块的直径。

不妨枚举每个子树。求出子树内直径是容易的，直接跑一遍 dp 即可。

现在要求【去掉这棵子树之后剩下的树去掉根节点之后的若干连通块的直径】。

我们预处理出每个点在删完根节点之后属于哪个连通块。

与这个子树无关的连通块的直径显然没有受到影响，直接 checkmax 即可。

现在来考虑剩下的这个连通块的直径。

我们可以将树拍到 dfs 序上面，然后对于每个连通块维护前缀直径和后缀直径。

上述利用到了直径的可合并性质。

然后每次查一个子树，设其 dfs 区间为 $[L, R]$ ，我们只需要将 $L - 1$ 前缀的直径和 $R + 1$ 后缀的直径合并起来，然后就能得出该连通块去掉这个子树之后的直径了。

如果写 $O (\log n)$ 单次询问的 LCA 求距离会被卡常，换成 $O (1)$ LCA 就可以了。

简单分析一下就行，有时间再来写一下。