• 2023.9.14
  • P3920 [WC2014] 紫荆花之恋
  • CF1408H Rainbow Triples
• 2023.9.15
  • CF1534G A New Beginning
  • CF1696G Fishingprince Plays With Array Again

2023.9.14

哇哦，居然出现了第二篇博客。

前两天 whk，顺便感了个冒，所以 whk 也没咋看。今天还没完全恢复，浅更一下吧。

先把 AGC 优先级调低点，天天做 AGC 好像也不是很好。

做点数据结构吧，ds 好啊（

P3920 [WC2014] 紫荆花之恋

其实是待办事项放了好久的东西。简单练练码力。

我们每次加入一个点，所以只需要考虑这个点与其它哪些点能够造成贡献即可。题目要求点对贡献且与距离有关，这显然是点分树能够解决的问题，设 \(dis(u)\) 为 \(u\) 到分治中心的距离，那么条件就是 \(dis(u) + dis(v) \ge r_u + r_v\)，即 \(r_v - dis(v) \le dis(u) - r_u\)。那么我们只需要用平衡树维护 \(r_v - dis(v)\)，查询只需要知道有多少数小于等于 \(dis(u) - r_u\) 即可。

难点在于题目强制在线，我们不能直接建点分树。可以每次直接在点分树下拓展，然后类似于替罪羊树的方法进行大力重构即可。

难点在实现。

CF1408H Rainbow Triples

假如我们将最后选择的方案看做若干个区间，那么是存在一种方案使得所有区间都有交的，因为如果两个区间无交交换两个端点一定是合法的。而这样我们可以使得所有选择的区间全部尽量靠左和靠右，于是一定存在一种方案使得选择的 \(0\) 是一个前缀加一个后缀。

设一共有 \(m\) 个 \(0\)，那么每个区间的左端点一定在 \([1, \lfloor m/2 \rfloor]\) 个 \(0\) 中，右端点一定在 \([\lceil m/2 \rceil, m]\) 中。考虑从中间划分开这个序列，那么对于左边的数，我们只需要考虑左边能否匹配上一个 \(0\)，因为右边无论如何都能找到一个进行匹配。同理右边的数只需要考虑在右边找一个 \(0\) 进行匹配。于是，我们将问题转化成了一个类似于二分图的问题，每个颜色可以选择一个数，从一个前缀或一个后缀中选择一个数进行匹配。这非常网络流，所以我们可以建一个网络流模型出来。

（复制了一张图）

考虑最大流等于最小割，每个颜色要不然将上面的前缀后缀边全部割掉，要不然割源点向颜色点连的一条边。考虑枚举割的前缀后缀的边，那么如果某个颜色没有全部被割那么就要割下面的边。这个过程是容易线段树维护的。

2023.9.15

昨天有点摆。虽然今天应该不会有任何改进。

嗓子还是疼，感冒真 nm 难受。寄。

上午一直在水，哈哈。看了眼初赛，SoyTony 将不定积分的总习题课做完了，膜拜。我只会积最简单的，我好弱。

然后下午更水了。算了我水吧。

CF1534G A New Beginning

挺简单的题其实是，不过我把贡献函数看成曼哈顿距离了然后想了半天不会，非常弱智。

考虑到贡献是一个形如正方形的东西，那么我们在正方形的左上角或右下角进行操作一定不劣，也就是在斜率 \(-1\) 的直线上进行操作。按照截距排序后，问题变为：

每次可以将 \(x\) 加 \([0, a]\) 中的任意数，并将 \(|x-b|\) 贡献到答案上。

这个显然是可以 DP 的，而且贡献函数是绝对值函数，直接上 Slope Trick。前面的操作可以看做一个区间取 \(\min\)，凸函数进行这个操作发现就相当于从斜率为 \(0\) 处断开，右半部分向右平移一段距离。那么我们分开维护左右两部分即可，打一个 tag 维护。

CF1696G Fishingprince Plays With Array Again

好题啊好题啊好题啊好题啊好题啊好题啊好题，一开始想线性规划了但是感觉应该不会有太大关系，然后想贪心去了，然后结果还真就线性规划。

以下默认 \(X < Y\)。

题目给出的限制很容易写成线性规划的形式。设 \(x_i\) 为在 \(i\) 处操作 \((+X, +Y)\) 的次数，\(y_i\) 为在 \(i\) 处操作 \((+Y, +X)\) 的次数，那么容易写出线性规划的问题：

欲最小化 \(\sum_{i=1}^{n - 1} x_i + y_i\)，满足：

• \(X(x_i + y_{i-1}) + Y(x_{i-1}+y_i) \ge a_i\)；
• \(x_i, y_i \ge 0\)。

考虑其对偶问题，可以画一个系数矩阵出来，容易发现其对偶为：

欲最大化 \(\sum_{i=1}^n a_i z_i\)，满足：

• \(X z_i + Y z_{i+1} \le 1\)；
• \(Y z_i + X z_{i+1} \le 1\)；
• \(z_i \ge 0\)

发现这个问题的形式优美了极多，而且变量之间的限制也少了很多。此时我们若直接记录上一个 \(z_i\) 选的什么，那么就可以直接 DP 了。但是显然没法直接记录。

众所周知线性规划可能取到的点一定是某个交点，那么考虑将上述问题画在二位坐标系上考虑。发现三个交点分别是 \((0, \frac{1}{Y}), (\frac{1}{X+Y}, \frac{1}{X+Y}), (\frac{1}{Y}, 0)\)。发现所有交点实际上只会出现三个坐标 \(0, \frac{1}{X+Y}, \frac{1}{Y}\)。这样我们就将值域减少到了 \(3\)。然后就很容易直接 \(O(n)\) 进行 DP 求解了。

考虑区间查询，这个东西容易写成 max-add 矩阵的形式，直接线段树维护矩阵即可。