P5372 [SNOI2019] 积木 题解
:::::info[题目基本信息]
考察：构造，图论（省选/NOI-）。
题目简介：
你有
数据范围：
-
1\le n,m\le 2000 -
::::: 这个题如果我们令一个木板相当于一条边，那么整个网格板就是整张图的最大匹配，现在我们令这两张图做异或，定义图的异或如下（这个应该有个名词但我忘了）： :::::info[图的异或] 有图 $A,B$，那么 $G=A\oplus B=\{(u,v)|[(u,v)\in A]+[(u,v)\in B]=1\}$。 ::::: 容易发现由于原两图均为匹配，故原图上每个点的度最多为 $1$，异或后度最多为 $2$ 且仅有最多 $2$ 个点度为 $1$，故最终异或图是由一条链和一堆环组成。 我们的思路就是在跑这一条链的过程中找到没有跑的环，然后跑过去进行交换，再跑回来。 具体地，我们跑一个 DFS，DFS 过程中先找到他所在的链，然后在其他方向找到别的没有被找链的点进行 DFS，最后再走找到的链。 DFS 极其不标准的伪代码如下： ``` DFS(x,y): if (x,y) has arrived: return find-the-chain-of(x,y) for (tx,ty) is near (x,y): if (tx,ty) has not been looked for the chain: move to (tx,ty) DFS(tx,ty) let (tx,ty) be the next node of (x,y) in the chain DFS(tx,ty) ``` 那么现在我们该如何找到这条链呢？ 我们现在的 $(x,y)$ 是空白格，那么我们可以通过末状态推出下一个点，再对下一个点通过初状态推出下下个点，移动木板并开始递归即可。 递归到被递归的点自然就不用递归了。 由于转移到环的这段过程中已经把木块移过去导致与终状态产生差异就不必在进行撤销操作的动作了。 这样我们就做完了此题。 容易发现构造次数不超过 $2nm$。 时空复杂度均为 $\Theta(nm)$。
code