§ Desc.

Link.

给出 $n$ 个最高位不超过 $m$ 二进制数, 对于每个 $i \in [1, n]$, 找到一个 $j \neq i$, 使得删去 $i$ 和 $j$ 后, 满足票数超过 $\lfloor \frac n2 \rfloor$ 的数位数最大. 某个二进制数的某一位为 $1$ 就相当于给这一位投票.

$3 \leqslant n \leqslant 3\times 10^5$, $1 \leqslant m \leqslant 20$.

§ Sol.

这篇题解写得很玄学, 不好理解, 建议不看.

考虑如下暴力:

int n, m, s[300100], cnt[30];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i=0,x;i<n;++i)
        for (int j=0;j<m;++j) {
            cin >> x;
            s[i] |= x<<j;
            cnt[j] += x;
        }
    for (int i=0;i<n;++i) { // enumerating chairman
        for (int j=0;j<m;++j) cnt[j] -= s[i]>>j&1;
        int ans = 0;
        for (int j=0;j<m;++j) ans += cnt[j] >= n/2;
        int sw = 0; // set waiting to be determined
        for (int j=0;j<m;++j)
            sw |= (cnt[j] == n/2)<<j;
        int ext = 233;
        for (int j=0;j<n;++j)
            if (j != i) chkmin(ext, __builtin_popcount(s[j]&sw));
        cout << ans-ext << "\n";
        for (int j=0;j<m;++j) cnt[j] += s[i]>>j&1;
    }
}

那么问题转化为, 对于 $S$, 求 $\min\{\mid S \cup T_i \mid\}$, 将 $T_i$ 取补集, 则求 $\max\{\mid S\cup T_i\mid\}$. 令 $g_S$ 表示与 $S$ 的交集最大的 $T_i$ 的 $i$. 由于交集一定是 $S$ 的子集, 因此可以从子集转移过来. 很难说, 只能意会, DJ 给我讲了半天才懂.

大概是, 首先求出 $S$ 的某个超集的编号, 这个可以直接用超集和. 然后以这个为初值, 求解上述的 DP. 当然, 正确的思考顺序是为了上面的 DP 构造初值, 这才是我们的 Motivation.

int n, m, s[300100], cnt[30];
int f[1<<20], g[1<<20];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    memset(f, -1, sizeof f);
    memset(g, -1, sizeof g);
    for (int i=0;i<n;++i) {
        for (int j=0,x;j<m;++j) {
            cin >> x;
            cnt[j] += x;
            s[i] |= (x^1)<<j;
        }
        if (f[s[i]] == -1) f[s[i]] = i;
        else g[s[i]] = i;
    }
    // == computing f[i], such that @i \in @s[f[i]]
    for (int i=(1<<m)-1;i>=0;--i) {
        for (int j=0;j<m;++j) {
            if (!(i&(1<<j))) {
                int ni = i|(1<<j);
                if (f[i] == -1) {
                    f[i] = f[ni];
                    if (g[ni] != f[i] && g[i] == -1) g[i] = g[ni];
                } else {
                    if (f[i] != f[ni] && g[i] == -1) g[i] = f[ni];
                    else if (f[i] != g[ni] && g[i] == -1) g[i] = g[ni];
                }
            }
        }
    }
    // == end computing f[i]
    // == computing f[i], such that |i&s[f[i]]| is max
    for (int i=0;i<1<<m;++i) {
        for (int j=0;j<m;++j) {
            if (i&(1<<j)) {
                int ni = i^(1<<j);
                vi v;
                for (int x : {f[i], g[i], f[ni], g[ni]})
                    if (x > -1) v.pb(x);
                if (v.empty()) continue;
                sort(v.begin(), v.end(), [&](int x, int y) {
                    return __builtin_popcount(s[x]&i) > __builtin_popcount(s[y]&i);
                });
                v.erase(unique(v.begin(), v.end()), v.end());
                f[i] = v[0];
                if ((int) v.size() > 1) g[i] = v[1];
            }
        }
    }
    // == end computing f[i]
    for (int i=0;i<n;++i) {
        for (int j=0;j<m;++j) cnt[j] -= !(s[i]>>j&1);
        int ans = 0, cur = 0;
        for (int j=0;j<m;++j) ans += cnt[j] > n/2;
        for (int j=0;j<m;++j) cur |= (cnt[j] == n/2)<<j;
        if (i == f[cur]) ans += __builtin_popcount(cur&s[g[cur]]);
        else ans += __builtin_popcount(cur&s[f[cur]]);
        cout << ans << "\n";
        for (int j=0;j<m;++j) cnt[j] += !(s[i]>>j&1);
    }
}

/ 板斜尿流急，坑深屎落迟。/

—— 梁实秋 - 忆清华 [上]