CF1710E Two Arrays

MiniLong · 2025-08-27 14:35:27 · 题解

首先二分答案 mid，将 a_i + b_j \le mid 的看成是 0，否则是 1。那么 A 想最后留在 0，B 最后留在 1。每一步肯定是在 01 间交替，可以建一个二分图，将它复制 1000 次，使得每条边 (u,v) 在任意两个复制的图之间都出现。

则这个问题等价于一开始在一个 1 的点，每次走到二分图的另一边，把上个点删掉，走不了的就输了。这是一个经典结论：

• 二分图博弈，每次走到相邻的一个点并删除上个点，走不了的人输，先手获胜的充要条件是：二分图的所有最大匹配都包含起始点。

  • 充分性：由于起始点在所有最大匹配都出现，所以不存在一条从起始点的增广路，使得可以走匹配-非匹配边最后走到一个非匹配点（否则可以把起始点扔掉换成这个点），那么先手就一直走匹配边即可。
  • 必要性：假设存在一个不包含起始点的最大匹配，在先手走完第一步后后手可以一直沿着匹配边走，而先手不可能走到一个非匹配点（否则最大匹配 +1），所以先手肯定会输。

那么只需要求出这个二分图的最大匹配，删掉起始点再求一次看看是否相等即可，而复制了 k 次的二分图 G^k 的最大匹配 |M^k|=k|M|，证明如下：

所以只需求出原图最大匹配，可以将 a,b 从大到小排序，1 的点是左上角的一个凸的轮廓线。考虑 hall 定理，即求出 \max\limits_S (|S| - |N(S)|)。那么选出的 S 中，一定不存在 (i,t),(j,t) 使得 i<j 且 (i,t) \notin S, (j,t) \in S，这是因为 i 行的 0 个数肯定小于等于 j 行 0 个数，换成它肯定不劣，列也同理。所以 S 肯定是一个左上角的矩形（只有前缀的行列），那么枚举行数是 i，再双指针处理一下列 j，当且仅当 j+1 列权值 >0 才加入，做个前缀和优化一下即可线性求出。

对于删掉起始点 (x,y) 的最大匹配也类似，不过要将 (x,y) 移到行中 1、列中 1 数量相同的行/列中最后一个就行。

复杂度 \Theta(n\log V)。