[ARC147E] Examination

2023 年集训队论文《浅谈一些二分图匹配相关问题》的例题。

感觉看完论文以后做起来行云流水，但是自己想应该是想不出来，所以还是记录一下。以下都是瞎扯。

拆解问题，乍一看不存在好的策略，但是我们知道 \(A_i<B_i\) 的部分一定要换，而剩下的部分要求我们自行抉择。

因为要求我们自己决定选哪些，所以之后的判定过程要么可以分步跟着决策走，要么有一个简洁的充要条件之类。

考虑决策结束后如何判定，使用一个经典的贪心：\(A, B\) 都升序排，顺序枚举 \(A\)，选一个最大的 \(B\)。

这个贪心过程只能分布刻画，但是又很难记录状态，基本是寄了。直接从贪心的角度想没啥前途。

抽象模型，对于这类匹配贪心，我们有经典的二分图模型。而二分图上我们就可以用 Hall 定理判定：考虑最大的 \(A\) 为 \(A_x\) 时，右侧所有 \(\le A_x\) 的 \(B\) 都会被算进 \(N(X)\)，最严格的情况自然是 \(X\) 包含所有 \(\le A_x\) 的部分的情况。

找等价表述，这一步我们已经知道了可以对于每个位置进行计算，泛化以下扔到值域上就是后缀 \(+,-\)，判断最小值是否非负。

现在知道了判定，回来看原问题。

我们选上一个 \(A_i\ge B_i\) 的人，对于判定的影响就是 \([B_i, A_i)\) 区间 \(+1\)。于是转化为这样一个子问题：

选择若干个区间覆盖到点上，使得点 \(x\) 至少被覆盖 \(a_x\) 次。

仍然可以贪心求解，此时从区间角度贪心不太好想，而从点的方向开始考虑就会变得简单：从左往右扫 \(x\)，当 \(a_x>0\) 的时候选一个包含 \(x\) 且 \(r\) 最大的区间即可。

时间复杂度 \(\mathcal O(n\log n)\)。

我认为转化判定方式这一步不看论文我是不会的，但是看样子对于大部分人来说这题并不难？还是菜了。

不过这种思维方式挺对啊。还是欠缺一些灵活转化的能力。