2023.5 做题记录

[Violet] 天使玩偶

显然发现我们需要在时间轴上进行 cdq 分治，然后统计答案。

问题在于这个绝对值不好维护，需要进行转化。如果我们钦定这个点最近的点在它的左下方，那么绝对值就可以化为 \(dis(A,B)=(A_x-B_x)+(A_y-B_y)=(A_x+A_y)-(B_x+B_y)\)。显然前面的括号是定值，那么我们维护 \(B_x+B_y\) 的最大值即可。这个可以用树状数组简单做。

但是显然我们最后的答案不一定在左下方，还可能在其他四个方向。那么我们每次做完 cdq 就把整个坐标系旋转 \(90\degree\)，然后再次 cdq 即可。

[CTSC2018] 混合果汁

首先发现题目中有最小值最大的含义，可以想到二分。我们二分这个最小值，那么接下来我们就考虑买 \(d_i\ge mid\) 的果汁。此时再利用贪心，由于选价格小的一定更优，所以我们再按 \(p_i\) 排序依次选。此时会出现三种情况：钱没有花完就达到了体积要求、钱花完了没有达到体积要求、所有果汁买完了也达不到体积要求。

对于第一种情况我们增加最小值，否则减少最小值。但是这样做 check 的复杂度似乎较高。

考虑到朴素的二分时间主要花费在 check 上，那我们考虑缩小 check 的时间。首先对于第三种情况，我们可以十分简单的利用前缀和求解。同时，第二种情况的另一种表述就是 “达到体积要求的钱数大于当前钱数”，那么我们只需要再维护 “达到体积要求的最小钱数” 即可。

考虑使用线段树，以 \(d_i\) 为下标，存储总体积之和和价格之和。那么前缀和便可以解决。现在考虑怎样在线段树上求 “达到体积要求的最小钱数”，我们可以在线段树上二分，以类似于查找排名的方式求解。

现在时间复杂度就是 \(O(n\log^2 n)\)，做 \(m\) 次操作的复杂度就是 \(O(n^2\log^2 n)\)，显然过不去。

这时候就可以考虑整体二分，把查询放一块处理，时间复杂度就变成 \(O(n\log ^2 n)\) 了，可以通过。

[SCOI2007] 蜥蜴

首先我们肯定想到是从一个柱子向另一个能跳的柱子连边，但是这样下来是错误的。

我们考虑到这张图的权值在点上，因此考虑拆点，将每一个点拆成入点和出点，这两个点之间的容量就是柱子高度。而对于两个点之间，将第一个点的出点与第二个点的入点连边，容量为 \(\infty\)。

接下来我们考虑源点和汇点。首先源点应该是每个蟋蟀在的柱子，但是这样会有多个源点，因此建立超级源点；同理，所有边框外的部分都是汇点，因此建立超级汇点。

由于每个柱子上只能放一只蟋蟀，因此超级源点到每个汇点的容量是 \(1\)。

最后我们直接跑最大流即可，答案需要用总蟋蟀数减去最大流流量。

士兵占领

首先看到方格问题，直接考虑连 \(x\to y\) 的边。

接下来我们发现题目要求的是最小值，由于我们只会最大流，因此这个最小值显然是做不了的。考虑转化，即求出空出的格子数量的最大值，这样我们就可以使用最大流了。

那么既然这样我们就要求出每一行每一列空出的格子数 \(r'_i,c'_i\)。接着我们建立超级源点，从源点到每一个 \(x\) 连容量 \(r'_x\) 的边；建立超级汇点，从每一个 \(y\) 向汇点连容量为 \(c'_i\)​ 的边。

那么既然这样我们上面提到的 \(x\to y\) 的容量自然就是 \(1\) 了。于是我们跑最大流，然后用 \(nm-k\) 把最大流流量减去即可。

[HNOI2007] 紧急疏散

这个题你的建图很容易假掉，然后这个题的数据还特别水，所以你的假做法大概能拿 \(50\sim 90\) 不等。

首先这道题是求出所有人撤离的最短时间，显然可以想到二分答案。我们假设当前要检查 \(mid\)，那么我们的门就有了时间限制。

既然这样，我们就可以采用按照时间拆点的方式来做。我们将每一个门拆成第 \(1,2,\cdots,mid\) 秒的门，接下来我们考虑连边。

首先建立超级源点，给所有空地连容量 \(1\) 的边，这表示每一块空地上有一个人。

然后我们计算出每一个空地到每一扇门的距离（可以从门开始用 BFS 求解），对于每一块空地，向任意一扇门的对应所用时间连边，容量为 \(1\)。

最后建立超级汇点，每一扇门向汇点连容量 \(1\) 的边，因为一扇门每次最多进一个人。

但是这样会有一个问题，尽管一扇门每次最多进一个人，但是先来的人可以等，然后再进门。也就是说门的时间也应该是变化的。因此将每一扇门的每个时刻向下一个时刻连边，容量为 \(\infty\)。

然后我们直接跑最大流就可以求出有多少人逃离了。