图论强化训练！！!1 2023-02-15 16:00 folder 学术

1. 「JOISC 2020 Day1」汉堡肉
2. 「NOI2021」庆典
3. 「ABC077D」Small Multiple

「JOISC 2020 Day1」汉堡肉

第一个观察是，只需考虑最右的左边界，最左的右边界，最上的下边界，最下的上边界四条线段。
\(K \le 3\) 时必定存在一个点选在交点处。爆搜，选择一个交点，然后删除包含其的矩形，递归即可。

\(K=4\) 时，讨论每个矩形与这四条线段中的多少条有交：

1. 限制了一个子线段内的点至少选择一个。
2. 限制了两个子线段内的点至少选择一个。
3. 一定至少完整包含四条线段的一条。可以忽略。
4. 同上。

可以发现我们得到了一个 2-SAT。

然后可以把子线段离散化，用线段树优化建图，但是已经够难写了……
另一个做法是，对于每个矩形相交的两条线段各建一个布尔变量，这样再处理不相交的部分，可以用前后缀优化建图。

「NOI2021」庆典

前面忘了，折戟沉沙，后面忘了。

注意到给定的性质可以用来刻画树。缩点之后，每个点保留拓扑序最大的入点即可。
然后建虚树，跑 35 分的暴力即可。

「ABC077D」Small Multiple

考虑 \(\times 10\) 和 \(+1\) 可以刻画所有数。注意到不用考虑进位，因为不优。
同余最短路。