【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e288
【解題想法】
- 假設角色只有A、B、C三個，用三個bits來紀錄每一組CP包含哪些角色。變數mask是一個有3個位元的二進位數，且每一個bit皆為 1（111），利用bitwise XOR運算，找出互補CP。
- 【例】ABB = 011 –> 011 ^ 111 = 100 (互補CP必須且只包含 C 一個角色)
- 【例】AB = 011 –> 011 ^ 111 = 100 (互補CP必須且只包含 C 一個角色)
- 【例】C = 100 –> 100 ^ 111 = 011 (互補CP必須且只包含 A、B 兩個角色)
- 【例】CC = 100 –> 100 ^ 111 = 011 (互補CP必須且只包含 A、B 兩個角色)
- 【註】題目中的角色最多有38個，變數mask需要的 ‘1’ 的個數可能多達38個位元，會超出int的範圍，所以要用1LL（64 bits）來產生。
- 【註】第25行有 bitwise operation。「<<」：左移運算子。「｜」：「位元 OR」運算。計算後，變數mask有 m 個 ‘1’。
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
int m, n, l, a[38], ans;
long long mask, tmp;
string s;
map <long long, int> mp;
int alpha2int(char c){
//字母轉換成數字
if (c <= 'Z') return c - 'A';
else return c - 'a' + 26;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> m >> n){
mp.clear();
ans = 0;
mask = 0;
for (int j = 0; j < m; j++){
mask |= (1LL << j);
}
for (int i = 0; i < n; i++){
memset(a, 0, sizeof(a));
cin >> s;
l = (int)s.size();
for (int j = 0; j < l; j++){
a[alpha2int(s[j])] = 1;
}
tmp = 0;
for (int j = 0; j < 38; j++){
if (a[j]) tmp |= (1LL << j);
}
if (mp.count(tmp ^ mask)) ans += mp[tmp ^ mask];
mp[tmp]++;
}
cout << ans << "\n";
}
}