互補團隊

題解

此題需要的先知條件是，程式中二進位就跟開關一樣，$1$為open，$0$為close，現在這題我們就需要用到這個觀念。

題目有提到到$m$為大寫A到Z，那我們可以模擬一件事情二進位1 1 1 1就像是D C B A一樣，如果這個A是已存在的，其他不存在就是0 0 0 1，以此類推

我們對於每個輸入的team進行位元運算，最後存入teams的是每個team缺的人，再進行還原算並且查找每個在這個team之後的team所有團隊所缺的人(這樣可以避免重複運算)

AC Code

python(因為zj測資壓太死所以會TLE，但是同樣邏輯C++是可以的)

from sys import stdin
m,n=map(int,stdin.readline().strip().split())
teams=[]
tt=(1<<m)-1
total=0
for _ in range(n):
    x=stdin.readline().strip()
    team=0
    for i in x:
        team |= (1<<(ord(i)-ord("A")))
    teams.append(tt-team)
for i in range(n):
    target=tt-teams[i]
    for j in range(i+1,n):
        if target==teams[j]:
            total+=1
print(total)

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n,total=0;
    cin>>n>>m;
    int ff=(1<<m)-1;
    vector<int> teams;
    for(int i=0;i<n;i++){
        int t=0;
        string s;
        cin>>s;
        for(int j=0;j<s.size();j++){
            int a=1<<(int(s[j])-int('A'));
            t |= a;
        }
        teams.push_back(ff-t);
    }
    for(int i=0;i<n;i++){
        int target=ff-teams[i];
        for(int j=i+1;j<n;j++){
            if(target==teams[j]) total++;
        }
    }
    cout<<total<<endl;
}