2023.1.2 营业日志

新年快乐。

P3895 [湖南集训]Hungry Rabbit

Analysis

考虑网络流。发现限制相当于每天最多添加 \(l\) 个兔子，扔掉 \(l\) 个兔子，为了方便讨论我们认为刚刚加入的兔子可以被扔掉，这样相当于这个兔子没有出现。那么添加 \(l\) 个兔子就相当于从源点到当天的所有点连一条边，流量最多 \(l\)，扔掉 \(l\) 个就相当于往汇点连，然后还有一些兔子可以留下的，就往下一天连边。最后判断是否满流即可。直接写网络流交上去 \(50\) 分，开 O2 有 \(80\)。

这题如果关注恰好 \(k\) 个的条件就不太好做，因为不可能把 \(k\) 个的限制转化成流量限制，这 \(k\) 个兔子对应的流量还要参与接下来的过程。用模型表示兔子的加入和离开就好很多。当然刻画恰好 \(k\) 个用上下界也不是不可以。

Solution

正解是神秘贪心。

一个直觉是我们要尽量选活的更久的兔子，所以每次换的时候把所有兔子按照存活时间排序，在换最多 \(l\) 个的前提下，尽可能选大的即可。

P1251 餐巾计划问题

Analysis

直接上下界费用流不是不可以。建立两排点，一排表示用的餐巾，一排表示脏的，用的点 \(i\) 向脏的点 \(i'\) 连流量为 \([r_i,\inf]\) 的边，脏的点 \(i'\) 向 \(i'+1\) 连边，或者向 \(i+n\) 连一条边。最后最后一天脏的向汇点连个边就好了。

考虑转成普通费用流。参考P3358 最长k可重区间集问题，这种只有下界的问题转成普通费用流的经典方法是考虑“剩下”的那一部分。所以可以想到先钦定每天都是买 \(r_i\) 条新的餐巾，然后考虑用以前的脏餐巾来替代这些餐巾。然后可以注意到无论怎样，一天都会产生恰好 \(r_i\) 条脏餐巾，于是可以 \(i\) 向 \(i'+n\) 连费用为 \(s-p\) 的边，表示替代买的餐巾个数，然后两排点分别向源汇连流量为 \(r_i\) 的边。然后就转化成了一个任意流问题了，优化建图之后可以通过。

这种东西一脸可以模拟流的样子，事实上一位上古神仙提出了一个做法，不过细节未知。

感觉最为迷惑的实际上是那个钦定部分，先钦定再调整的方法很常见但是也没啥规律，现在我唯一见过的比较常见的模型是双选模型，比如说这里一堆餐巾可以选择买或者洗，那就钦定全买然后就只需要考虑洗的问题，其它就不太清楚了。

CF1208H Red Blue Tree

Analysis

好像会了个 \(\mathcal{O}(n\sqrt{n\log n})\)，但是好难写！！！1111

暴力每次求一遍可以做到 \(\mathcal{O}(n^2)\)，比较困难的点是一次 \(3\) 操作对信息的改变量是可以达到 \(\mathcal{O}(n)\) 级别的，而且递归定义也比较烦人。

考虑没有 \(3\) 操作怎么做，发现一个点的影响是一条连续的链，链上所有点满足同色且 \(b_i-r_i\) 的值是相等的，直接使用树剖大力维护链 min 然后链上二分可以得到一个 \(\mathcal{O}(n\log^2n)\) 做法。

接下来我尝试寻找 \(3\) 操作的性质，唯一发现的性质是，当 \(k\) 增大的时候只会存在由蓝变红的点，归纳不难证明。我一直在尝试解析这个红蓝点的递归定义，但是没有找到很好的解释方式。

考虑只有 \(3\) 操作怎么做，发现随着 \(k\) 的递增，一个点只会从蓝点变成红点一次，从叶子到根二分可以求出每个点变红的时刻，这是一个 \(\mathcal{O}(n\log n)\) 的做法。

只有操作 \(3\) 的做法引导我考虑询问分块，对于连续的 \(B\) 个操作，考虑每次都把前缀的叶子修改操作都进行一次，那么一个叶子会影响它所有的祖先结点，影响的形态和虚树非常类似。所以可以把叶子结点可以询问结点都拉出来建立一棵虚树，于是每次考虑操作的时候只需要考虑虚树上一条链的影响，关键点的颜色可以利用暴力做法直接求出。套用树剖做法可以得到一个 \(2\log\) 做法。观察可以发现，如果要让一条链整体反色的条件非常严苛，以蓝色变成红色为例，需要满足 \(b_i-r_i\geq k\) 且 \(b_i-r_i-2<k\)（因为增加一个红色点会让 \(b_i\gets b_i-1,r_i\gets r_i+1\)），而且容易发现一个点的 \(b_i-r_i\) 奇偶性是不变的，且随着 \(k\) 变大，\(b_i-r_i\) 的值递减。所以可以维护一条链上 \(b_i-r_i\) 的奇数最小值和偶数最小值，套用条件就可以得到 \(\mathcal{O}(1)\) 判断整条链能否反色的方法。

这样我们在 \(\mathcal{O}(n\log n)\) 预处理和总共 \(\mathcal{O}(B^2+n)\) 的时间内解决了连续 \(B\) 个操作，选取合适的 \(B\) 值可以做到 \(\mathcal{O}(n\sqrt{n\log n})\)。取 \(B=3000\) 可以通过本题。

标算在看了。