2024/05/31(#46)：只身航行于生命与信仰的海洋

菜就多练。

61 PA 2015 Final Edycja

可以视作搞出一个内向基环树森林。先贪心选择，然后要处理环。设 $f_{i,S,t}$ 代表考虑到第 $i$ 个点，枚举其出边，拆掉了 $S$ 的环，是否存在入度为 $0$ 的点（因为全是环，且不是全是自环是合法的）。

60 CEOI2019 Building Skyscrapers

来补昨天的东西。

我们显然要去删大楼（字典序是倒着比的也提示了这一点），考虑当前子问题有解的充要条件：当前大楼八连通。

一个点能被删掉的充要条件是：

• 它能够到达无穷远处；
• 它不是八连通图的割点。

考虑将非大楼点称为白点，那么能到达无穷远的白点的大楼满足条件一，这个很好维护。

条件二说明我们只能删圆方树的叶子，但是这样发现我们需要维护动态图的圆方树，基本上是死了。但这是网格图，性质很好，出现问题只有类似以下两种情况（B 表示楼，X 表示是割点，W 表示白点）：

B W B
W X B
B B B

B B B
W X W
B B B

其中 W 要在同一个连通块内，每次更新即可。但是我一开始写了各种奇怪的东西，一个简单题被我断断续续写了两天，只能说我是唐氏。

62 QOJ6320 Parallel Processing

如果我们能使用每一条指令，那么大概率它是很优的。对于 $n$ 较小的手玩，较大的直接递归即可。