[ARC125D] Unique Subsequence
可以用一个树状数组来维护当前有多少个合法子序列以 \(i\) 结尾，记作 \(f_i\) 。那么每次有 \(f_i = \sum_{j=las_{i}}^i f_j\) . \(las_i\) 表示 \(a_i\) 上一次出现的位置 . 同时要把 \(f_{las_i}\) 设为 \(0\) .
[ARC125E] Snack
可以很简单的建出来一个网络流模型，然后考虑求最小割。枚举左边割了 \(x\) 个点，显然优先割掉 \(a_i\) 较小的点。然后考虑右边的贡献，右边每个点要么割掉和汇点相连的边 \(c_i\)， 要么割掉和左部点相连的边 \((n - x)b_i\) ， 所以每个右部点的贡献为 \(min(c_i, (n - x)b_i)\) , 把贡献加起来就是一个 \(n\) 段的一次分段函数。枚举 \(x\) 就行。
[ARC125F] Tree Degree Subset Sum
设每个点的度数为 \(d_x\) , 首先给每个 \(d_x\) 减 \(1\) 不影响答案。
设 \(L_x\) 表示最少用多少点可以使度数和为 \(x\) ， \(R_x\) 表示最多用多少点可以使度数和为 \(x\) ， 那么发现合法的方案是区间 \([L_x, R_x]\) , 考虑证明。设有 \(z\) 个点 \(d_x = 0\) , 有性质对于任意合法的 \((x, y)\) 即 \(x\) 个点，度数和为 \(y\) 有 \(y - x \in [-z, z - 2]\) ，那么 \(L_x - x \in [-z,z-2], R_x - x \in [-z, z-2]\) , 就有 \(R_x - L_x \leq 2z - 2\) , \(L_x\) 通过加上这 \(z\) 个点使 \([L_x, L_x + z]\) 合法， \(R_x\) 通过去掉这 \(z\) 个点使 \([R_x -z, R_x]\) 合法。所以 \([L_x, R_x]\) 合法。
关于证明 \(y - x \in [-z, z - 2]\) ， 当只取 \(d_x = 0\) 的点时 \(y - x = -z\) 是最小值，当只取 \(d_x > 0\) 时 \(y - x = \sum_x d_x - \sum_x [d_x \geq 1] = n - 2 - (n - z) = z - 2\)
然后跑多重背包把 \(L_x\) 和 \(R_x\) 求出来就行，一共只有 \(O(\sqrt{n})\) 种不同的度数。复杂度 \(O(n\sqrt{n})\)
标签：度数,专场,个点,训练,sum,合法,20230406ARC,割掉,las From： https://www.cnblogs.com/i209M/p/17294420.html