2026-09-13(#13)：恐惧领域

Ashrount × 打打だいず —— DREAD AREA

28 qoj14708 Crossing River

$f(i,j)$ 代表运送了两边的前多少个人的最小时间，但是状态数不太能优化。

当已知最终时间时，直接倒着检查是非常容易的，因为所有人都可以送。于是直接二分 $O(n)$ 检查即可。

29 qoj14306 Robot

在远处造墙，连着两个空一个，这样跑得比它快，于是就可以在右边堵死它。围死后二维分治绝杀即可。

实际上细节很多，如果看不了数据对于笔者来说不是很好写。代码。

30 qoj20029 Red Sequence

很容易得到一个有两个维度限制的 DP（消除掉红色元素的影响，得到 $y_j\ge y_i,b_j\ge b_i$，但是问题是如果真的有这样一个东西，为什么不把它拆成两段呢？比如说，找到一个 $k\in(j,i)$，使得 $b_k=b_i$，这样答案依然是等效的。唯一的例外就是这一段除了红色没有别的，因此要允许 $b_j=b_i+1$ 类的查询。

31 qoj20025 String

为啥没开这个题啊。。。

发现是二进制某一位加法，然后做完了。

32 qoj15437 Find the Circuit

想多了。

首先做成内向基环树状物，但是环上有多余的连边，因此按照环顺序钦定排名即可，这样我们只需要拆掉一条环边然后能变成 DAG 就是合法的。在这个过程中走到的能被拆掉的点都不用再尝试去拆了。

复杂度好像是对的，不管了。

33 qoj20236 All Closed

怎么又是赛后过题。。。

沃日了直接暴力就是对的。场上瞪了一万年 K 不知道写错哪里了。再给我十分钟我都把思路整理得差不多了然后就写了。

就你轮着去扫每个集合，如果不封闭就暴力加。最多加 $O(2^m)$ 次，每次加是 $O(1)$ 的（因为维护加的数的集合的线性基最多加 $m$ 次，只有这 $m$ 次是 $O(nm)$ 的）。

如果一个能扩展出很多数的集合只会给答案添加很少的数，那么它本来就不大。复杂度大概是对的。

没过是我的问题。