# APCS實作題2019年6月第3題：互補團隊

> 日期：2024年8月29日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=e288)

## 題目

### 問題描述

每一個字元代表一名角色，由於這個遊戲的角色包括教師只有38位，所以他們用'A' \~ 'Z'和'a' \~ 'l'來表示第 1 到第 38 位角色。但是由於他們太喜歡這些角色了，所以每個字母可以出現在字串中很多次，例如 "AAAAAA" 和 "A" 其實是同一組 CP。

最近他們找到了新的消遣，他們觀察出一種叫做CP互補的特殊現象，只要兩個CP之間沒有重複的角色且兩個CP的角色集合包含全部角色，我們就說CP之間互補。現在他們開始討論他們喜歡的CP，且他們想要知道這些CP中有那些是互補的，於是他們拜託你寫個程式幫他們數。
<br />

### 輸入說明

單筆輸入
第一行有兩個數字 $m, n$ ，分別代表這次他們這次只討論前 $m$ 個角色和CP數量。
接著有 $n$ 行，每行有一個字串代表一組 CP，字串長度在 1 ~ 1000 之間。

配分
- 5%：$m = 2,~ n \leq 1000$
- 25%：$m \leq 26,~ n \leq 10000$
- 75%：$m \leq 26,~ n \leq 100000$
- 100%：$m \leq 38,~ n \leq 500000$
<br />

### 輸出說明

輸出互補CP的對數
<br />

### 範例輸入

3 4
ABB
AB
C
CC

### 範例輸出

4

<br />

## Python 程式碼

將字元轉成2進位數字，使用位元運算。第5筆測資開始超時。

from collections import defaultdict

def convert(c):  # 將字元 c 轉成編號，A 為 0，Z 為 25，a 為 26
    return ord(c)-ord('A') if c<='Z' else ord(c)-ord('a')+26 

m, n = map(int, input().split())  # 讀取角色數量 m，組數 n

table = defaultdict(int)  # 字串對應的數量
for _ in range(n):  # 讀取 n 筆資料
    s = input()  # 輸入字串
    tmp = 0  # 暫存編號
    for c in s: tmp |= 1<<abs(convert(c))  # 用 or 運算及 convert 將字串轉成編號
    table[tmp] += 1  # 字串對應的數量加 1

ans = 0  # 答案預設為 0
for sn, num in table.items():  # 由 table 依序取出字串編號及數量
    tmp = ((1<<m)-1)^(sn)  # 先産生 m 個 1，再用 XOR 運算找出 sn 的補數
    if tmp in table: ans += num*table[tmp]  # 如果 table 之中有 tmp，ans 加上 sn 及其補數數量乘積

print(ans//2)  # 答案要除以2

<br /><br />

## C++ 程式碼

將字元轉成2進位數字，使用位元運算。其中第19、24行的 1 要用 (LL) 轉型成 long long，否則會得到錯的數值。費時最久約為 0.4 s，使用記憶體最多約為 27.9 MB，通過測試。

#include <iostream>
#include <string>
#include <unordered_map>
typedef long long LL;
using namespace std;

LL convert(char c) {  // 將字元 c 轉成編號，A 為 0，Z 為 25，a 為 26
    return c<='Z' ? c-'A' : c-'a'+26;
} 

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;  // 讀取角色數量 m，組數 n
    unordered_map<LL, LL> table;  // 字串對應的數量
    string s;
    for(int i=0; i<n; i++) {  // 讀取 n 筆資料
        cin >> s;  // 輸入字串
        LL tmp = 0;  // 暫存編號
        for(char c : s) tmp |= (LL)1<<(convert(c));  // 用 or 運算及 convert 將字串轉成編號
        table[tmp]++;  // 字串對應的數量加 1
    }
    LL ans = 0;  // 答案預設為 0
    for(auto it=table.begin(); it!=table.end(); it++) {  // 由 table 依序取出字串編號及數量
        LL tmp = (((LL)1<<m)-1)^(it->first);  // 先産生 m 個 1，再用 XOR 運算找出 sn 的補數
        if (table.find(tmp) != table.end()) ans += (it->second)*table[tmp];  // 如果 table 之中有 tmp，ans 加上 sn 及其補數數量乘積
    }
    cout << ans/2 << "\n";  // 答案要除以2
    return 0;
}

<br />

修改一點寫法。費時最久約為 0.4 s，使用記憶體最多約為 27.9 MB，通過測試。

#include <iostream>
#include <string>
#include <unordered_map>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL m, n; cin >> m >> n;
    LL comp = ((LL)1 << m) - 1;
    unordered_map<LL, LL> teams;
    string s;
    for(int i=0; i<n; i++) {
        cin >> s;
        LL code = 0;
        for(char c : s) {
            if (c <= 'Z') code |= (LL)1 << (c - 'A');
            else code |= (LL)1 << (c - 'a' + 26);
        }
        teams[code]++;
    }
    LL ans = 0;
    for(auto it = teams.begin(); it != teams.end(); it++) {
        LL target = comp^(*it).first;
        if (teams.find(target) != teams.end()) ans += (*it).second * teams[target];
    }
    cout << ans/2 << "\n";
    return 0;
}

<br /><br />

## 參考資料

吳邦一教授的 APCS 解題影片〈[PyAp45 Python APCS 題解：互補團隊(APCS201906_3), AP325 Q-2-7., 中一中 TCFSH CIRC 編號d016.](https://youtu.be/5XSydGMi2HA?si=LxI0Y-Mn4yN2oZK1)〉

---

###### tags:`APCS`、`Python`、`C++`