2026天梯赛游记

_•́へ•́╬_ · 2026-04-18 17:15:18 · 题解

提前到了，等比赛开始，跟同学打了一会麻将。

比赛开始就狂做 200 分，但是还是没拿到手速分。再喷一遍这个不能有行末空格的要求。

倒数第二个题是最小点覆盖。dinic 加点优化应该能过。

但是我写的是假做法。先全选左部点，然后逐渐删去左部点，每次删除度数最小的，这样就会有若干边没被覆盖；转而选择右部点来覆盖这些边。注意我们左部点的度数是动态统计的，只统计还没有被右部点覆盖的边数。在整个过程中记录左右点数之和的最小值。

说再多都是假做法。。。

最后一个题好难。最后打表找到了 a 为排列的规律，拿了 13 分。

正解是个 \mathcal O(n^2) 的 dp。好难。