Hall 定理 笔记

定义邻域 $N(S)$ 为所有和 $S$ 中的点有连边的点组成的集合。

• 二分图一部中选出点集 $S$，$S$ 中的每个点都能匹配，当且仅当 $\mathrm{\forall }T\subseteq S,|T|\le |N(T)|$；

• 若不存在能覆盖二分图的完全匹配，则二分图最大独立集的数目为 $\underset{T\subseteq S}{max}\{|T|-|N(T)|\}$。

1. P3488 [POI 2009] LYZ-Ice Skates

可以建出二分图，让人连向所有他能穿的鞋子。

套用 Hall 定理，从人这一部的点考虑，我们发现在 $|S|$ 相同的情况下，如果 $S$ 内的点集越分散，就会导致 $|N(S)|$ 更大，进而导致 $|S|-|N(S)|$ 更小。

因此，连续的子区间更容易不合法，问题转化成判断是否 $\mathrm{\forall }l,r$，满足 $\sum _{i=l}^r{a}_i\le k(r-l+1+d)$，即 $\sum _{i=l}^r(a_i-k)\le dk$，使用线段树维护最大子段和判断是否合法即可。

2. AT_arc076_d [ARC076F] Exhausted?

同上一题理建图转换。

我们发现对于一个 $S$，他们的 $N(S)$ 是一堆区间的并集，难以处理。正难则反转换为 $S$ 里所有人都不能坐的区间的交集 $N^{\prime }(S)$，则变为要求 $|S|-(m-|N^{\prime }(S)|)$ 最大，即 $|S|+|N^{\prime }(S)|-m$ 最大。

从 $S$ 的角度选择不容易，考虑从 $N^{\prime }(S)$ 的角度入手，若 $N^{\prime }(S)=[l,r]$，则 $|S|=|\{i\mid L_i<l\cap r<R_i\}|$，转换为扫描线二维数点问题，时间复杂度 $O(n\log n)$。