笔记 2023.12.19：题目选讲

不会的题目没在这里展现。一共 14 道题。

gym103371I Organizing Colored Sheets

猜结论：两个同一行的 sharp 的间隙的 \(\min\) 是 \(W\) 上界，同一列的 sharp 的间隙的 \(\min\) 是 \(H\) 上界，然后相乘。

这是假的，是答案上界，过不去样例二。每个 \(H\) 对应的 \(W\) 上界不一定相同。

结论：不合法的尺寸，不能被覆盖的网格一定有至少一个与边界或有色网格相邻。

如果 \((x, y)\) 无色，\((x+1, y)\) 有色，尝试计算 \((x, y)\) 的限制，发现只需要记 \(L, R, U\) 表示向左、向右、向上走多少格到有色网格，那么暴力枚举 \(1\sim U_{xy}\) 的高度，用 \(L, R\) 取一点 \(\min\) 加以限制，发现复杂度是对的。

QOJ1884 Mission Impossible: Grand Theft Auto

考虑到缩链后有最多 \(2m-2\) 个点（\(m+x\) 个点，\(x\) 个点至少三度，\(m+3x=2(m+x-1), m-x=2\)），\(2m-3\) 条边，每条边对应了至多一个叶子。而共有 \(m\) 个叶子，根据鸽巢原理，存在一个叶子使得它有至多一条坏边。用这个叶子开始操作，直到最后一次操作覆盖掉坏边即可。

*gym102341B Bulbasaur

考虑固定左端点之后暴力向后流，例如 \(F(1, n)\)，流满了以后把最后的一些点删掉，删到增广最远的地方，然后继续流。移动左端点只需要把左端点删掉。\(O(nk^3)\)？

*QOJ4214 Deja Vu

设 \(a, b, c\) 表示长度为 \(1, 2, 3\) 的子序列，初始 \(\infty\)，从左往右扫描到 \(x\)：

• 如果 \(x\leq a\)，\(a=x\)。
• 否则如果 \(x\leq b\)，\(b=x\)。
• 否则如果 \(x\leq c\)，\(c=x\)。
• 否则我们得到了答案。

就很像二分求 LIS 的过程。注意时刻有 \(a<b<c\)。然后他说势能线段树，不知道是啥。

ARC156F Make Same Set

直接网络流，但是会不会有问题呢，不会。

你考虑那些没有流量的点。称一个点为空点，当且仅当它连出去的两条边都没有匹配，它是严重不合法的。实点就是相反。考虑一个空点变为实点以后不会再变回去？因为变回去的时候反悔到那里就不是最短路了，有个更近的从实点过来走两步的流，它是个假的流。所以一开始强制所有 \(A_i\) 流掉再进行 dinic，因为这样全是实点，且 dinic 每次增广都是最短路，就对了。\(O(n\sqrt n)\)。