杂题选做 2

· · 题解

P8179 「EZEC-11」Tyres

挺不错的题目。

如果 t=0，显然有一个 \mathcal{O}(m\log n) 的做法，其正确性在于每个轮胎跑圈的代价是递增的。

考虑扩展上述做法，将换轮胎的代价放在每个轮胎第一圈上，上述做法错误是因为其第一圈的代价破坏了代价递增这个良好的性质，但是在第二圈及其以后该性质仍然存在。

设阈值 B=\lceil\sqrt{t}\rceil，注意到每个轮胎第 B+1 圈后的代价严格大于前 B 圈的代价，于是做法就出来了，对轮胎的前 B 圈做一个背包 dp，然后大于 B 圈的就做一个贪心，然后合并一下两部分的答案即可。

复杂度为 \mathcal{O}(n^2t+m\log m)，如果使用决策单调性，容易做到 \mathcal{O}(n^2\sqrt{t}\log(n\sqrt{t})+m\log n)。

P8484「HGOI-1」Mole

考虑模拟费用流。这里的模型是增量-最大费用任意流。

考虑每次增加一个区间，相当于多加了一个点，并向对应的点连边，由于区间是没有权值的，所以没有必要考虑正环，同时与 t 相连的边是不会退流的。所以只需要考虑增广路即可，但是显然直接增广会超时。这种题目由于其不会退流直接考虑 Hall 定理，即假设现在已经选了集合 S，如果要再加入一个点 x，只需要用 Hall 定理检验对于集合 S\cup\{x\} 是否存在完美匹配即可。这里的图挺好推的，对前 l 个/后 l 个/中间的区间分别进行 Hall 定理的检验即可，然后可以用线段树维护。复杂度为 1log。

[ABC225H] Social Distance 2

通过组合意义推出来的，难绷。

其实通过生成函数也可以推。

设两个编号之差为 x 的人中间再塞 y 个所有可能方案的贡献之和为 f(x,y)。

直接算确实不太好算啊，看上去很像一个差板法的变体。

考虑 \prod 的组合意义，本质上是在计算 \le b_{i+1}-b_i 的 y 元组个数。

于是反过来枚举这个 y 元组，然后计算该 y 元组的贡献次数。

通过上指标求和容易列出

f(x,y)=\sum_{i=y}^x \binom{i-1}{y-1}\binom{x-i+y-1}{y-1}=\binom{x+y-1}{2y-1}

会做这个整个题就很容易了，套一个分治 NTT 即可。

2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

唐完了，就写三个题。

https://codeforces.com/gym/101986

H.Homework

求最大值非常简单，写个弱智贪心即可。

考虑最小值怎么做。注意到 Taro 的策略在每天已知选哪门课程后是最优的，即让做的作业最多。那么问题转化为 \min_{S}f(S)，S 为一个长度为 n 的二进制数，描述了 n 天中每天做哪门课程的状态。f(S) 表示在 S 条件下的最大做作业数，容易用一个二分图匹配的模型描述。

但是问题依然棘手。考虑这样一个思路，先找到一个问题答案的尽量紧的下界，然后证明答案可以取到这个下界。

建立如下网络流模型：源点 S 向第一门课程的作业连流量为 1 的 edge，然后让第一门课程的作业分别向其 s_i\sim t_i 的所有时间对应的点连边，汇点 T 向第二门课程的作业连流量为 1 的 edge，然后让第二门课程的作业分别向其 s_i\sim t_i 的所有时间对应的点连边。注意每一天只能做一个作业，所以每个时间点要建立两个点，两个点之间连流量为 1 的边，然后第一门课程作业向第一个点连，第二门课程作业向第二个点连。

显然上述模型的最大流就是问题答案的一个下界。因为有匹配的每个时间点无论这一天做啥作业都肯定有作业可以做。然后就是要去构造一个 S 使得 f(S) 可以取到这个下界，似乎比较容易构造？官方题解也没说咋构造。

J.String Puzzle

死掉了，这也不会做。

考虑题目输入给出的奇怪性质，即每个条件的右区间都两两不交。考虑每个条件实际上是描述了一些边，但是暴力找出所有连通块就爆炸了。一个经典 trick 是找出每个连通块的最小编号的点作为其代表点。现在问题转换为如何快速找出一个点所在连通块的最小编号点。注意到当一个条件的右区间与左区间不同时，显然从右区间的点只可能跳到左区间对应的点，也就是只有一种跳法。当一个条件的右区间与左区间相交时，由于所有条件的右区间都两两不交，手玩一下发现其实也只有一种跳法跳出去。所以当起点固定时，每个区间其实都只有一种跳法。故能往前就往前跳就是正确的，不可能往后跳。

K.Counting Cycles

求一个无向图的简单环个数。

考虑求出一颗生成树，然后枚举简单环包含了哪些非树边，实际上包含一个非树边的集合对应的简单环是唯一的。考虑如下 trick，将一个非树边上包含的所有树边的权值全部加 1。最后权值为奇数的树边包含在这个简单环上，实际上手玩一下这个过程，其准确描述了环的合并。由于得到了每条边最后是否存在，只需要快速 check 即可。如果暴力 check 复杂度就爆炸了，显然只需要建立出虚树即可。复杂度 \mathcal{O}(2^K\operatorname{poly}(K))，其中 K 为非树边数量。

「SWTR-7」Spider Solitaire

非常棒的题目。

注意到一个非常关键的点：非空数堆的最右边。为什么是非空？将一个递减且公差为 -1 的极长连续段称之为一个牌堆，那么一次操作其实上相当于合并了两个牌堆，于是得到第一问答案其实就是牌堆个数减一。

考虑图论建模处理该问题，设有向边 u\rightarrow v 的含义为要让牌堆 u 动起来与下一个牌堆接起来需要先把牌堆 v 移走。那么一个暴力建图是把牌堆 u 向所在数堆后面的所有牌堆都连一个边，显然这个牌堆需要移走，且设牌堆 u 的下一个牌堆为 w，那么显然 w 所在数堆后面的所有牌堆也需要移走。容易通过后缀优化建图优化边数。那么问题有解当且仅当图是一个 DAG，移动 i 的最少步数就是点 i 所在牌堆的点在图上到达的点数。使用 bitset 优化即可。复杂度 \mathcal{O}(\dfrac{n^2}{w})。

比较类似的题目：CF1753D The Beach。

[AGC022E] Median Replace

差点做出来，只能说见过差不多的模型。

注意到操作 000 是非常优秀的，可以一下子干掉两个 0。而操作 001/011 本质上等价于同时扔掉一个 0 和一个 1，跟第三个数是什么完全没有关系！ 于是考虑设计一个栈来判断一个 01 串是否合法，从左往右扫过去。

如果当前加入一个 0:

如果当前加入一个 1:

最后判断栈内是否 1 的个数大于 0 的个数。注意到这个栈本质上是由一段连续的 1 + 一段连续的 0 构成的，且 0 的个数不超过 2。

那么只需要保存不超过 3 个 1 即可，dp 就做完了。