Fabulous Fungus Frenzy(3)
将过程逆序，\(1\)操作不变，\(2\)操作即将与模板矩阵匹配的子矩形变为通配符
借助\(1\)操作，可以在\(2(n+m)\)次操作内交换两个位置
在此基础上，不断找到一个"可操作"的模板矩阵，并调整后操作
（这里"可操作"是指可以构造出一个能匹配且不全为通配符的子矩形）
关于操作次数，这里分为四类：
-
每次\(2\)操作至少增加一个通配符，因此至多\(nm\)次\(2\)操作
-
每个模板矩阵第一次操作时，至多\(2knm(n+m)\)次\(1\)操作
-
之后每次在第一次的位置上操作，注意到上一次操作后已经全是通配符
换言之，此时每次交换均对应于某个位置变为通配符，至多\(2nm(n+m)\)次\(1\)操作
-
得到最终的矩阵后，若无法匹配则无解，否则至多\(nm(n+m)\)次\(1\)操作
综上，\(1\)操作总次数最多为\(6\times 20^{4}+4\times 20^{3}=992000\)，但实际显然跑不满
Neue Spiel(4)
参考这里
Topology
咕咕咕
Drawing
咕咕咕
Hoof and Brain(3)
考虑以下两种情况：
-
对于出度为\(0\)的点，后手不能移动到该点，不妨删除
-
对于出度为\(1\)的点，后手移动到该点后，下次只能移动对应出边
不妨合并两点，用线段树合并维护边集，并需去掉重边
重复上述过程，若最终\(x\)或\(y\)被删除或两者在同一点上，显然先手必胜
同时，若不为上述情况，每个点出度均\(\ge 2\)，显然后手必胜
换言之，该条件充分必要，时间复杂度为\(O(n+q+m\log m)\)
放学路(4)
参考这里
标签：讨论,至多,授课,矩阵,出度,通配符,WC2023,操作,模板 From： https://www.cnblogs.com/PYWBKTDA/p/17092056.html