題目連結: https://zerojudge.tw/ShowProblem?problemid=c460
# 內容
亞歷山大將軍準備派遣一支精銳部隊前往攻打鄰國，他麾下有三個種族；每個種族各有不同兵種。
為了平衡部隊的組成份子，亞歷山大會從三個種族各選擇一個兵種。此外，他還會考慮這個部隊是否能涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。舉例來說，亞歷山大將軍麾下的三個種族各有三個兵種如下：
亞歷山大可以選擇法師、骷髏兵團和勇士這個組合，因為這個組合涵蓋了三個種族和三個特性；但他不能選擇弓箭手、骷髏兵團和投矛手這個組合，因為這個組合未能涵蓋「範圍攻擊」這個特性；他也不能選擇弓箭手、炸彈兵和炸彈塔這個組合，因為這個組合未能涵蓋「哥布林」這個種族。
亞歷山大為了向國王解釋，他想要告訴國王總共有多少種可能的組合，請你幫幫他。
# 解題思路
可以記錄每種排列組合的數量。每種排列組合可以用 2 進位觀點，ai 權值 4、ri 權值 2、di 權值 1，將 3 種特性表示成 1 個特性值。
對 3 種族的特性值窮舉，如果 3 個特性值位元運算為 7，數量相乘
-> 此作法稱作為位元壓縮喔～～
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
int army[4][8]; | |
int main(){ | |
int n; | |
while(cin>>n){ | |
memset(army,0,sizeof(army)); | |
for(int i=0,type,ai,ri,di;i<n;i++){ | |
cin>>type>>ai>>ri>>di; | |
army[type][ai*4+ri*2+di]++; | |
} | |
ll ans = 0; | |
for(int i=0;i<8;i++) | |
for(int j=0;j<8;j++) | |
for(int k=0;k<8;k++) | |
if((i|j|k)==7) | |
ans+=army[1][i]*army[2][j]*army[3][k]; | |
cout<<ans<<endl; | |
} | |
} |
