e288 - 互補CP

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定一組 CP (由角色字元組成) 中，互補 CP 的數量。互補 CP 的定義是：兩個 CP 沒有重複的角色，且兩個 CP 的角色集合包含全部角色。輸入包含角色數量 m 和 CP 數量 n，以及 n 個 CP 字串。

解題思路

這題的核心思想是利用位元運算來表示每個 CP 包含的角色集合。由於角色數量最多為 38，可以使用一個長整數 (long long) 的每一位來表示一個角色是否存在於 CP 中。例如，如果 CP 包含角色 'A' 和 'C'，那麼對應的位元表示為 101 (假設 'A' 對應第 0 位，'B' 對應第 1 位，以此類推)。

對於每個 CP，計算其位元表示 tmp2。然後，計算所有角色的位元表示 re，即 2^m - 1。互補 CP 的位元表示 tmp2^re，表示 tmp2 不包含的角色。

使用一個 map (哈希表) ans 來儲存每個 CP 的位元表示及其出現次數。對於每個 CP，檢查 map 中是否存在其互補 CP 的位元表示。如果存在，則將互補 CP 的出現次數加到總和 sum 中。最後，更新 map 中當前 CP 的出現次數。

複雜度分析

• 時間複雜度: O(n * k)，其中 n 是 CP 的數量，k 是 CP 字串的平均長度。計算每個 CP 的位元表示需要 O(k) 的時間，查找和更新 map 需要 O(log n) 的時間，但平均情況下可以視為 O(1)。
• 空間複雜度: O(n)，因為 map 最多儲存 n 個不同的 CP 位元表示。

程式碼

#include <iostream>
#include <string.h>
#include <map>
using namespace std;
int m,n;
long long int sum,re,tmp2;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> m >> n;
	char b[1005];
	for(int i=0;i<m;++i){
		re*=2;
		++re;
	}
	map <long long,int> ans;
	map <long long,int> :: iterator iter;
	while(n--){
		cin >> b;
		int bl = strlen(b);
		tmp2=0;
		for(int i=0;i<bl;++i){
			if(b[i]<='Z')
				tmp2 |= (1LL << (b[i] - 'A'));
			else
				tmp2 |= (1LL << (b[i] - 'a' +26));			
		} 
		if ((iter = ans.find(tmp2^re)) != ans.end())
			sum += iter->second;
		++ans[tmp2];
	}
	cout << sum;
}