Koios1143的筆記

Kattis - bard

發表於 更新於 分類於

Kattis bard

題目

https://open.kattis.com/problems/bard

在某個小村莊當中有 $N$ 個村民，並且有一位村民是吟遊詩人

在這個村莊，每個晚上都會聚集一些村民來唱歌

如果晚上吟遊詩人有出現，那麼他會帶來一首新歌，並且當天所有參加的村民都只會唱那首歌，同時彼此都學會了那首新歌

如果當天晚上吟遊詩人沒有出現，那麼所有參加的村民們會將他們所會的歌都唱一遍，同時彼此都學會那些歌

給定村民的數量 $N$，編號 $1$ 的村民為吟遊詩人

給你每天晚上參加晚會的村民編號，問最後一天有哪些村民(包含吟遊詩人)會唱全部的歌

想法

因為最多只會有 $50$ 場的晚會，$2^{50}$ 還在 long long 的範圍內，所以可以用位元運算來想

每個村民都有一個數字，數字的 bit 記錄該村民是否會唱某首歌

那麼當有吟遊詩人出現時，我們就將所有參加的村民在當天的 bit 上記錄 $1$

如果當天吟遊詩人沒有出現，那麼由於每個參加的村民之間會共享所有他們會的歌曲，所以我們可以透過 or 運算先求出所有人會的歌曲的聯集，最後每個村民會的歌都變成那個聯集結果

如此一來就可以模擬出每晚晚會後的結果

在最後可以保證吟遊詩人會所有的歌(畢竟歌是他提供的)，所以接下來只需要判斷所有村民會的歌曲是否跟吟遊詩人相同即可

Note

在實作時要特別小心位元運算的左右移，因為這裡用到的是 long long ，而位元運算預設都是採用 int，所以我們要將數字強制轉型為 long long

例如我們要得到 $2^{10}$ 以 long long 為其形態的結果，應該這麼做

1
1LL<<10

也就是說，我們希望得到怎樣的型態，則位元運算子左側之運算元須為該型態

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//By Koios1143
#include<iostream>
using namespace std;
int N, E, K, arr[105];
long long songs[105];
int main(){
	cin>>N>>E;
	for(int i=0 ; i<E ; i++){
		cin>>K;
		
		// 檢查是否有吟遊詩人出現
		bool bard=false;
		for(int j=0 ; j<K ; j++){
			cin>>arr[j];
			if(arr[j] == 1) bard=true;
		}
		
		if(bard){
			// 每個人當天的歌都會學會
			for(int j=0 ; j<K ; j++){
				songs[arr[j]] |= (1LL<<i);
			}
		}
		else{
			// 每個人當天都會學會所有參加者會的歌的聯集
			// 先找出聯集
			long long all_song = 0;
			for(int j=0 ; j<K ; j++){
				all_song |= songs[arr[j]];
			}
			// 全部賦予給參加的村民
			for(int j=0 ; j<K ; j++){
				songs[arr[j]] = all_song;
			}
		}
	}
	for(int i=1 ; i<=N ; i++){
		if(songs[i] == songs[1]){
			cout<<i<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(EN)$

每晚更新每個參加村民所會的歌曲，其時間複雜度為 $O(K)$

找出答案時間複雜度為 $O(N)$

總時間複雜度為 $O(E(N + K)+ N)$