互補團隊 題解｜APCS 2019 年 6 月中高級 第 3 題

前置知識

這題的核心（怎麼把「能力集合」變成一個整數、互補集合又是哪個整數）下面會從頭講；要先會的是：

• 位元運算：要帶走的是「1LL << j 是只有第 \(j\) 個位元是 \(1\) 的數，| 把位元設成 \(1\)、& 檢查有沒有重疊、^ 把位元反過來」。
• map：NTUCPC Guide〈Set 與 Map〉——map<long long, long long> count 可以用「集合編號」當索引記「出現幾次」，索引多大都不用開陣列。吳邦一《AP325》第 2 章的例題 P-2-6 Two-Number problem（在 \(A\) 裡找 \(K - b\)）和本題結構一樣，習題 Q-2-7 就是本題（教材 PDF 第 66～68 頁；Python 版第 2 章）；「另一種做法」用的排序＋二分搜也在同一節。

簡潔題意

有 \(m\) 種能力，依序用 A 到 Z、再 a 到 l 表示。每支團隊用一個字串列出它有的能力（重複出現的字母只算一種）。兩支團隊的能力沒有交集而且聯集剛好是全部 \(m\) 種，就叫互補。求互補的無序配對有幾對；能力集合一樣的兩支團隊仍是不同團隊（\(1 \le m \le 38\)，\(1 \le n \le 500000\)，字串長度 \(1\) 到 \(1000\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(5\) 分）：\(m = 2\)、\(n \le 1000\)，各隊能力集合互異。
• 子題組 2（\(20\) 分）：\(m \le 26\)、\(n \le 10000\)，各隊能力集合互異。
• 子題組 3（\(50\) 分）：\(m \le 26\)、\(n \le 100000\)，各隊能力集合互異。
• 子題組 4（\(25\) 分）：無額外限制，允許相同的能力集合。

把能力集合變成一個整數

字串不好比：ABB 和 AB 是同一個集合、BA 也是。把集合編碼成整數就乾淨了——第 \(j\) 種能力對應第 \(j\) 個位元（A 是第 \(0\) 個、Z 是第 \(25\) 個、a 是第 \(26\) 個……l 是第 \(37\) 個），有這種能力就把那個位元設成 \(1\)：mask = mask | (1LL << j)。

重複的字母只是把同一個位元再設一次，自然只算一種；\(m\) 最大 \(38\)，\(2^{38}\) 超過 int，所以 mask 和 1LL 都要用 long long。「全部 \(m\) 種能力」就是 \(m\) 個位元全是 \(1\) 的數 full = (1LL << m) - 1。

有了整數，互補的條件翻譯成：(a & b) == 0（沒有重疊）而且 (a | b) == full（合起來全滿）。更進一步，跟 \(a\) 互補的集合其實只有一個：\(a\) 沒有的能力全拿、有的全不拿，也就是 full ^ a（把 \(m\) 個位元全部反過來）。範例的四支團隊見圖 1。

先拿下子題組 1、2：每一對都檢查

算好每支團隊的 mask 之後，把每一對團隊都拿出來檢查一次，條件成立就加一。

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

const int MAX_N = 500000;
long long mask[MAX_N];           // mask[i] = 第 i 支團隊的能力集合（第 j 個位元是 1 ＝ 有第 j 種能力）

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        mask[i] = 0;
        for (int p = 0; p < (int)s.size(); p++) {
            int j;                               // 這個字母是第幾種能力（從 0 數起）
            if (s[p] >= 'A' && s[p] <= 'Z') j = s[p] - 'A';
            else j = 26 + (s[p] - 'a');
            mask[i] = mask[i] | (1LL << j);      // 把第 j 個位元設成 1；重複的字母設第二次也還是 1
        }
    }
    long long full = (1LL << m) - 1;             // m 個位元全是 1 ＝ 全部 m 種能力
    long long answer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {        // 每一對只看一次（j 在 i 後面）
            if ((mask[i] & mask[j]) == 0 && (mask[i] | mask[j]) == full) answer++;
        }
    }
    cout << answer << endl;
    return 0;
}

字母轉成編號用的是字元和整數的關係。配對數是 \(n(n - 1) / 2\)：\(n = 10000\) 時 \(5 \times 10^7\) 次一瞬間，\(n = 100000\) 時 \(5 \times 10^9\) 次本站實測 \(3.3\) 秒（時限 \(2\) 秒），\(n = 500000\) 時 \(30\) 秒跑不完。子題組 1、2 的 \(25\) 分穩穩到手。

從 25 分到 100 分：用 map 數「前面出現過幾支互補的」

跟 \(a\) 互補的集合只有 full ^ a 一個，所以不必逐對檢查：依序處理每支團隊，問「前面已經出現過幾支能力集合剛好是 full ^ mask 的團隊」，有幾支就多幾對；然後把自己登記進去，給後面的團隊配。每一對剛好在後面那支被處理時數到一次，不會重複也不會漏。

「某個集合出現過幾次」用 map<long long, long long> count 記，集合編號當索引、不用管它有多大；查不到的索引值是 \(0\)，剛好就是「沒出現過」。

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

int main() {
    int m, n;
    cin >> m >> n;
    long long full = (1LL << m) - 1;             // m 個位元全是 1 ＝ 全部 m 種能力
    map<long long, long long> count;             // count[x] = 目前為止能力集合是 x 的團隊有幾支
    long long answer = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        long long mask = 0;                      // 這支團隊的能力集合
        for (int p = 0; p < (int)s.size(); p++) {
            int j;                               // 這個字母是第幾種能力（從 0 數起）
            if (s[p] >= 'A' && s[p] <= 'Z') j = s[p] - 'A';
            else j = 26 + (s[p] - 'a');
            mask = mask | (1LL << j);            // 把第 j 個位元設成 1；重複的字母設第二次也還是 1
        }
        answer += count[full ^ mask];            // 前面有幾支團隊剛好是它的互補，就多幾對
        count[mask]++;                           // 自己登記進去，給後面的團隊配
    }
    cout << answer << endl;
    return 0;
}

幾個細節：

• 一支團隊不會跟自己配：\(m \ge 1\) 時 full ^ mask 一定不等於 mask，而且登記是在查完之後才做。
• 相同的能力集合（子題組 4）不用特別處理：count 記的是「幾支」，兩支 {A, B} 和兩支 {C} 就是 \(2 \times 2 = 4\) 對。
• 答案要 long long：\(250000\) 支配 \(250000\) 支就是 \(6.25 \times 10^{10}\) 對，超過 int（估算方法見語法書 2.9）。
• 每支團隊一次查、一次登記，\(O(n \log n)\)；輸入最大約 \(10\) MB，本站實測 \(0.37\) 秒。

測過再交：範例沒有重複集合、沒有小寫字母

範例 \(m = 3\)、四支團隊剛好兩兩成對，但沒蓋到：互補集合不存在、同一個集合出現好幾次要相乘、\(m\) 超過 \(26\) 出現小寫字母（驗 long long 位元）、以及答案超過 int 的大測資。

六筆都親眼看過正確，這題就穩了。

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

const int MAX_N = 500000;
long long mask[MAX_N];

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        mask[i] = 0;
        for (int p = 0; p < (int)s.size(); p++) {
            int j;
            if (s[p] >= 'A' && s[p] <= 'Z') j = s[p] - 'A';
            else j = 26 + (s[p] - 'a');
            mask[i] = mask[i] | (1LL << j);
        }
    }
    sort(mask, mask + n);                        // 排好序，同樣的集合會排在一起
    long long full = (1LL << m) - 1;
    long long answer = 0;
    for (int i = 0; i < n; i++) {
        long long want = full ^ mask[i];         // 它的互補集合
        // [第一個 >= want 的位置, 第一個 > want 的位置) 這一段全部都是 want
        answer += upper_bound(mask, mask + n, want) - lower_bound(mask, mask + n, want);
    }
    cout << answer / 2 << endl;                  // 每一對從兩邊各數了一次
    return 0;
}