251124 Larunatrecy 讲题

CF1764H Doremy’s Paint 2

枚举左端点 \(l\)，然后动态维护每种颜色的存活时间。发现扩展左端点是容易维护的。

[AGC062B] Split and Insert

首先时光倒流，发现最后一次操作形如把两个在值域上连续且单增的子序列拎出来。然后发现最后一次操作的代价只和划分点的位置有关。然后又发现在最后一次操作之前的所有操作对两个子问题是完全独立的。然后区间 dp 即可。

CF1889D Game of Stacks

对于第一层图，注意到一个环对全体节点的作用都是完全相同的：走一圈走回到第一次接触环的那个点，环上所有点 pop。因此不断找环然后 pop 即可。

CF1712F Triameter

求出每个点到叶子的距离 \(f_x\)，然后维护 \(f_x\) 一段后缀全体节点的直径，每次询问时直接把所有点扫一遍即可。时间复杂度 \(O(nq)\)。

[USACO23FEB] Watching Cowflix P

发现连通块代价为 \(k\) 时，两个距离为 \(k\) 的连通块可以直接合并。因此可以不断合并直到连通块数量不超过 \(\frac{n}{k}\)。此时建出虚树然后暴力 dp，时间复杂度是调和级数。

CF1787I Treasure Hunt

首先答案上界为最大前缀和+最大子段和。如果它俩相交那么可以调整为包含。因此问题转为求所有区间的最大前缀和+最大子段和之和。前者直接单调栈，后者考虑分治，对于一段区间 \([L,R]\) 考虑跨过分治重心 \(mid\) 的区间 \([l,r]\)。记 \(a_i\) 为 \([i,mid]\) 的后缀和最大值，\(b_i\) 为 \([mid+1,i]\) 的前缀和最大值，\(c_i\) 为 \([i,mid]\) 的最大子段和，\(d_i\) 为 \([mid+1,i]\) 的最大子段和。那么 \([l,r]\) 的最大子段和可以表示为 \(\max(a_l+b_r,c_l,d_r)\)。分讨哪个成为最大值，注意到 \(d_r-b_r\) 是 \([mid+1,r]\) 的一段前缀，并且具有单调性，\(c_l-a_l\) 同理。然后可以双指针分别处理三种情况。

[HNOI2012] 集合选数

将所有数字写成 \(2^x3^yz\) 的形式，按 \(z\) 划分为若干等价类，只有等价类内的数字才回互相影响。发现一个等价类内的数字形成一个网格图，对网格图进行状压 dp 即可。时间复杂度能过。

AT_arc087_d [ARC087F] Squirrel Migration

给你一棵树，计数 \(\sum dis(i,p_i)\) 取到最大值的排列 \(p\) 数量。

重心的转化比较显然，见CF468D。问题转化为：给你 \(k\) 个不交集合，称一组单项匹配合法，当且仅当每个元素匹配的都不是同组的元素，计数合法匹配数。

对限制进行容斥，设第 \(i\) 组包含 \(s_i\) 个点，钦定 \(x_i\) 个点匹配到同组元素，那么方案数为 \((n-\sum x_i)!\prod\binom{s_i}{x_i}^2x_i!\)，容斥系数为 \((-1)^{\sum x_i}\)。设计一个 2d-1d dp 即可。

AT_agc061_c [AGC061C] First Come First Serve

发现两种方案不同但本质相同（即会算重）当且仅当存在一个 \(i\) 满足开区间 \((a_i,b_i)\) 内没有其他人写名字。证明考虑从左往右找到第一个不同的位置。

如果开区间 \((a_i,b_i)\) 内确实没有人写名字，就强行钦定必须选 \(a_i\)。尝试容斥掉这个限制，发现钦定 \((a_i,b_i)\) 内没有其它人写名字等价于 \([l_i,i)\) 的所有人都选 \(a_i\)，\((i,r_i]\) 的所有人都选 \(b_i\)，其中 \(l_i,r_i\) 是和 \(i\) 有关的数，可以双指针求出。发现一定不会同时钦定 \(i\) 和 \(j\) 使得 \([l_i,r_i]\) 和 \([l_j,r_j]\) 有交，因为一定会出现矛盾。于是直接 1d-0d dp 即可。