24.10.09

KinNa-Sky / 2024-10-10 / 原文

哈哈写总结最早一天。改不动根本改不动。

NOIp 模拟赛放三道神秘题不知道出题人是不是考过这种 NOIp 哈哈。

A

根据猜结论（~~并通过大样例验证~~）可以得到划分的每组点要么是祖先-后代点对，要么是孤点。每组代价是 $1$。

然后简单 dp 是设 $f_x$ 表示 $x$ 子树内最少的孤点。

\[f_x= \begin{cases} (\sum_{y\in son} f_y) - 1 & (\sum_{y \in son} f_y \neq 0)\\ 1 & \operatorname{otherwise} \end{cases} \]

答案为 $\dfrac{i + 1 - f_0}{2} + f_0$。

~~然后场上 $O(n^2)$ 写挂~~。

然后考虑类似 DDP 写法。

每个点维护轻子树传上来的贡献，考虑一条重链上怎么匹配：

上部的链上点可以匹配下部的点，考虑先用上部链上点匹配下部轻子树内点，最后链上点可以两两匹配。

更新完一条链记得更新链顶父亲。

B

讲评：

题解直接把结论摆上来了啊。~~怎么证？我也不会。~~

我建议你们直接把式子抄上 NTT。

如果排列 $p$ 在区间 $[l,r]$ 上是值域连续段，那么该区间做一次置换后也是一个区间。因为 $p$ 做任意次置换后 $[l,r]$ 都是值域连续段。

如果这些区间互不相交，则在置换环上，这些区间构成一个圆排列。每一段区间都是值域连续段，在确定该区间跳到的区间后，它的值域也确定了，并且内部可以任意排列。因此这部分对答案的贡献是：

\[\sum_{i=1}^{\left\lfloor \frac{n}{k}\right\rfloor} (k!)^i\cdot (i-1)!\cdot (n - ik)! \cdot F_{i,l-1,n-r,k} \]

其中

\[F_{i,x,y,k}=\sum_{j = 0}^{i-1} \binom{x-j(k-1)}{j}\binom{y-(i-j-1)(k-1)}{i-j-1} \]

可以 NTT 计算。

对于相交的情况，有结论：如果将所有相交的区间合并成一个连续段，则每一个连续段有且仅有两个区间，且所有连续段长度相同。在通过置换环向后跳的过程中，会首先依次经过每个连续段中的一个区间，再按相同的顺序经过每个连续段中的另一个区间，最后回到初始区间。

若一个连续段是区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 构成的，设 $l_1 < l_2$，若区间 $[l_1,r_1]$ 中的最小值小于区间 $[l_2,r_2]$ 中的最小值，则称该连续段是上升的，否则是下降的。

假设一共形成了 $m$ 个连续段，这些连续段的指向关系会构成一个圆排列，并且其中一定有奇数个下降的连续段。类似于不交的情况，不妨设 $[l,r]$ 所在的连续段是上升的，该部分的贡献是：

\[\sum_{d=1}^{k-1} \sum_{i=1}^{\left\lfloor \frac{n}{k}\right\rfloor} 2^{i-1}\cdot \left((k-d)!^2\cdot d!\right)^i\cdot (i-1)! \cdot \left(n-i(2k-d)\right)!\cdot F_{i,l-1,n-r-k+d,2k-d} \]

P3147

P3147 [USACO16OPEN] 262144 P

“区间 dp”，emmm...你说是就是吧。

在弱化版里 $f_{l, r}$ 表示 $[l, r]$ 能合成的最大西瓜数，但是这个题里连数组都开不下。

那反正区间和值都是要维护的，值域又很小，考虑把值放到状态里。

$f_{l, v}$ 表示以 $l$ 为左端点，合成 $v$ 的右端点，为 $0$ 表示不能合成。

那么转移显然 $f_{l, v} = f_{f_{l, v - 1} + 1, v - 1}$。

哦，$\log_2 262144 = 18$，所以最大能合成 $58$，遍历上界要足够大。

P4342

P4342 [IOI1998] Polygon

第一眼：很典的环上 X 运算最大，破环成链区间 dp 一眼了，这怎么蓝。

写的时候很突然就想到两个负数相乘可以乘出个大正数，那两个负数想要乘数最大只需关注绝对值最大，那维护一个区间绝对值最大值不就好了（？）。

然后过了...当时我还在想会不会维护出的绝对值最大值一直是一个正一个负导致乘不出正值，远古 IOI 数据这么水嘛...。

然后题解说维护一个最大值一个最小值，确实绝对值最大不出这两种情况。转移暴力两两组合就好：）。

f[0][l][r] = -inf, f[1][l][r] = inf;
rep(k, l, r - 1) rep(lop, 0, 1) rep(rop, 0, 1)
	if (op[k])
		chkmax(f[0][l][r], f[lop][l][k] + f[rop][k + 1][r]),
		chkmin(f[1][l][r], f[lop][l][k] + f[rop][k + 1][r]);
	else
		chkmax(f[0][l][r], f[lop][l][k] * f[rop][k + 1][r]),
		chkmin(f[1][l][r], f[lop][l][k] * f[rop][k + 1][r]);

P2656/CF894E

P2656 采蘑菇 / Ralph and Mushrooms

为啥 Tarjan 板子放 dp 题单里。

缩点，同一个强连通分量里可以边权取到 $0$，否则只有第一次走的权。

P2656 里暴力往下乘，回复系数小于等于 $0.8$，$2^{31} - 1$ 乘到 $0$ 不超过 100 次。

注意不要用 double 有误差，先给系数乘 $10$，之后每次除以 $10$。

CF894E 最多走 $k$ 次，$k$ 是 $\dfrac{k(k + 1)}{2} \le w$ 的最大值，多走的贡献是 $\displaystyle w\times k - \sum_{i=1}^k \frac{i(i + 1)}{2} = w\times k - \frac{1}{2}(\sum_{i=1}^k i ^2 + \sum_{i = 1}^k i)$。点和边很多，需要快读。