CF2026E Best Subsequence

BMnya · 2024-10-30 13:35:13 · 题解

设 \operatorname{zerocnt}(x) 表示 x 的二进制表示低 60 位中 0 的个数，那么一个集合的价值也可以表示为 n+\operatorname{zerocnt}(a_1\operatorname{or} a_2\operatorname{or} \dots\operatorname{or} a_n)-60，这样答案就可以表示为所选数的个数的贡献加上数位中 0 的贡献。

考虑建一张二分图，左部点为 n 个数，右部点为 60 个数位。

如果选择了 a_i 并且 a_i 二进制下第 j 位为 1，那么数 i 和数位 j 无法同时产生贡献，那么就连一条 i\rightarrow j 的边；如果这位为 0 那么可以同时产生贡献。

所求最大值为这张图的最大独立集 -60，二分图的最大独立集等于点数减去最大匹配数，假设最大匹配为 mx，答案即为 (n+60-mx)-60=n-mx。

求解二分图最大匹配可以用网络流或者其他做法解决。