c460 - 3. 軍隊部署

🔗 前往 ZeroJudge 原題

題目描述

題目描述了亞歷山大將軍需要從三個種族（人類、骷髏族、哥布林族）中各選擇一個兵種，以組成一個部隊。部隊需要同時涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。給定每個兵種的種族和特性，要求計算有多少種可能的部隊組合可以滿足所有條件。

解題思路

這題的核心在於枚舉所有可能的組合，並檢查每個組合是否滿足條件。由於種族和特性可以用二進位表示，因此可以使用位運算來簡化判斷。 程式碼使用三個陣列 a[0], a[1], a[2] 分別儲存每個種族中，具有不同特性組合的兵種數量。例如，a[0][i] 儲存人類中，特性組合為 i 的兵種數量。 然後，程式碼使用三重迴圈枚舉所有可能的組合，其中 i, j, k 分別代表人類、骷髏族和哥布林族選擇的特性組合。 如果 (i | j | k) == 7，則表示該組合涵蓋了所有三種特性（對空攻擊、範圍攻擊、遠距攻擊）。 程式碼計算滿足條件的組合數量，並將結果儲存在 ans 變數中。

複雜度分析

• 時間複雜度: O(8 * 8 * 8) = O(512)。由於特性只有三種，因此特性組合的數量最多為 2^3 = 8。三重迴圈遍歷所有可能的特性組合。
• 空間複雜度: O(1)。程式碼使用的額外空間是固定的，不隨輸入大小變化。

程式碼

#include <iostream>
using namespace std;
long long a[3][8],n,x,y,z,v,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> v >> x >> y >> z;
		a[v-1][x+y*2+z*4]++;
	}
	for(int i=0;i<8;++i){
		if(a[0][i]==0)continue;
		for(int j=0;j<8;++j){
			if(a[1][j]==0)continue;
			for(int k=0;k<8;++k){
				if(a[2][k]==0)continue;
				if((i|j|k)==7){
					ans+=a[0][i]*a[1][j]*a[2][k];
				}
			}
		}
	}
	cout << ans;
}