比赛地址

Reconciled?

如果 $\lvert n-m\rvert>1$ 一定无解。

否则,如果 $n=m$ 则答案为 $2\times n!\times m!$,如果 $\lvert n-m\rvert =1$ 则答案为 $n!\times m!$。

代码

Built?

和某个切比雪夫距离最短路的题很像。

对于每个点 $(x,y)$,向 $x$、$y$ 各连一条 $0$ 边。然后再把相邻两个出现过的 $x$、$y$ 坐标间连 $x_{i+1}-x_i$ 或 $y_{i+1}-y_i$ 的边。

这样子 Kruskal 求最小生成树即可。

代码

Connected?

可以发现,如果一对点有一个不在边界上,那么不管其它的怎么连,这对点一定可以连上。

于是我们只要考虑边界上的点。可以发现这是一个类似于括号匹配的过程,把边界上的点按顺序排好后开个栈跑一遍即可。

代码

Exhausted?

标算是个奇妙的 Hall 定理+线段树+扫描线,然而被贪心暴打了(雾

我们先把所有人按 $l_i$ 从小到大排序,那么可能某时刻会有一个人塞不进去,那么我们可以丢一个 $r_i$ 最小的人到右边去坐着。

我们再把被丢到右边去的人按 $r_i$ 从大到小排序,如果某时刻有一个人塞不进去那就只能增加座位了。

代码

最后修改:2020 年 09 月 21 日 10 : 28 AM