BNU 34988 Happy Reversal：二進制按位取反最大差值

問題大意

給定 N 個長度為 K 的二進制串，可對任意串執行「按位取反」（0↔1）。操作後最大值 M、最小值 P，求最大化 M - P。

關鍵觀察

每個串只有兩種形態：原值 val 和取反值 rev = (2^K - 1) - val。我們從這 2N 個候選值中選一個作為 M、一個作為 P，但不能選同一原始串的兩種形態（因一個串只能取一種狀態）。

貪心策略

1. 計算所有 2N 個值，記錄來源串索引 id。
2. 按值降序排序。
3. 若最大值與最小值來源不同（id_max != id_min），直接相減即為答案。
4. 否若相同，則答案為 max(第二大 - 最小, 最大 - 第二小)。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL b2[61];
struct Item { int id; LL val; };

int main() {
    b2[0] = 1;
    for (int i=1;i<=60;++i) b2[i] = b2[i-1]*2;
    int T; cin >> T;
    for (int cs=1; cs<=T; ++cs) {
        int N, K; cin >> N >> K;
        vector a;
        a.reserve(2*N);
        string s;
        for (int i=0;i> s;
            LL v = 0, rv = 0;
            for (int j=0;j y.val; });
        LL ans;
        if (a[0].id != a.back().id) ans = a[0].val - a.back().val;
        else ans = max(a[0].val - a[a.size()-2].val, a[1].val - a.back().val);
        cout << "Case #" << cs << ": " << ans << '\n';
    }
    return 0;
}

複雜度

O(N K + N log N)，N≤10000, K≤60 完全足夠。