题解：AT_wtf22_day2_c Jewel Pairs

· · 题解

提供一个赛时写的常数巨大的不算排序也要 O(n\log n) 的唐龙做法。

唉我草这个模拟赛怎么这么坏啊把这题放 t1 还卡常导致我没做后面两个远小于这题难度的题！！！

考虑一个类似的经典问题是二分图，左部点带点权，最大化匹配点点权和。这个问题中我们的做法是左部点按照点权降序排序，顺次枚举尝试进行匹配，由匈牙利算法可以发现你的点集是不删的，所以正确性有保证。

我们尝试放到这个题上，发现类增广路显然都可以改到长度不超过 4 个点，两个点时是朴素的，四个点时找到最小的一个 k 满足它当前在匹配且且它和它的匹配点都与 i 的颜色不同，然后在此基础上找一个小于 i 且和 i 同色的符合 k 限制的最大 j 进行交换匹配即可。

但是这里的问题主要出在 j 的顺序问题，它一定在 i 后面看起来不一定能用上原先说的正确性证明，但是你考虑到我们保证了比 j 更大的点一定是没法通过 i 的类增广路匹配上的（或者已经被匹配过了），所以你退掉 j 点一定是不优的。

这样大力维护下时间复杂度是 O(n\log n)。

submission