---
# System prepended metadata

title: 演算法課程題解 - 位元運算
tags: [SCIST 演算法 題解]

---

# 演算法課程題解 - 位元運算

# TOJ 244
## 題目
https://toj.tfcis.org/oj/pro/244/

輸入第一行有一個正整數 $N$ ，接下來有長度 $N$ 的字串，請將所有小寫轉成大寫，大寫轉成小寫

## 想法 By Koios
過去曾經在條件判斷的課程中寫過這題，不過現在嘗試用位元運算的角度來解
觀察一下 ASCII Table，會發現到 `a` 以及 `A` 之間剛好差了 $32$
並且將其對應到的數字轉換成二進位後會發現到它們只在**第五個 bit**是不同的
也就是說我們要做大小寫轉換，只需要反轉第五個 bit 即可

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, x = (1<<5);
string s;
int main(){
	cin>>t;
	cin>>s;
	for(int i=0 ; i<t ; i++){
		cout<<(char)((int)s[i]^x);
	}
	cout<<"\n";
	return 0;
}
```

# UVa 10469
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10469

有個人在學如何用位元運算進行 32-bit 正整數的加法，但是他搞砸了
現在他設計出來的程式不能進位，請你嘗試設計出跟他一樣的加法器

## 想法 By Koios
我們可以考慮兩種情況
1. 原本需要進位
2. 原本不需要進位

如果說原本就需要進位，那就表示在二進位底下兩個 bit 都是 $1$，既然不進位，那這個位置最後會留下 $0$，而下一位不會 $+1$
反之，如果原本就不需要進位的話，那就直接相加即可

也就是說，考慮兩個 bit 的情況，整理如下表

|     | 1   | 0   |
| --- | --- | --- |
| 1   | 0   | 1   |
| 0   | 1   | 0   |

發現到這跟 **xor** 就是一樣的道理

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m;
int main(){
	while(cin>>n>>m){
		cout<<(n^m)<<"\n";
	}
	return 0;
}
```

# UVa 11195
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11195

經典 N 皇后問題
給定一個 $N \times N$ 的西洋棋棋盤，棋盤上可能有障礙物，障礙物可以抵擋攻擊
現在要在這個棋盤上放上 $N$ 個皇后，並且彼此都不會攻擊到對方，請問有多少種解法

## 想法 By Koios
想法跟過去 DFS 解 8 皇后問題是一樣的
對於每個可以放皇后的格子嘗試去放，然後看看能不能放滿整個盤面
不同的是，我們不需要每次都往三個方向(左斜/右斜/直)掃過去檢查，而是改用位元運算的想法

:::info
不考慮橫向是因為在 DFS 的過程當中我們就只會取每一列中其中一個下去枚舉，所以橫向必定不會互相攻擊
:::

以左斜向來看，我們可以用一個數字 $m$ 相對應的 bit 去記錄該點是否會被攻擊到
如果可以被攻擊的話，那麼枚舉下一列的時候會被攻擊到的點就會是 $m$ 全部 bit 左移後的位置

:::info
舉例來說，如果當前是 $4 \times 4$ 的棋盤，並且在第一列可以被左斜向攻擊到的有第 $3$ 行

當前 $m$ 以二進位表示為 $0010$

在枚舉到第二列的時候可以攻擊的點會左移，也就是變成 $0100$
:::

類似地，右斜向則是每次都會向右移一個 bit

至於直向也一樣用一個數字相對應的 bit 紀錄可否被攻擊，只是枚舉下一列時並不需要改變

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, ans, Case=1;
char arr[20][20];

// depth 表示當前枚舉的列數
void DFS(int depth, int Lslash, int Rslash, int straight){
	if(depth == n){
		ans++;
		return;
	}
	// 對於每一行去判斷
	// 1. 該點是否沒障礙物
	// 2. 左斜向攻擊是否會攻擊到
	// 3. 右斜向攻擊是否會攻擊到
	// 4. 直向攻擊是否會攻擊到
	for(int i=0 ; i<n ; i++){
		if(arr[depth][i] == '.' && ((Lslash & (1<<i)) == 0) && ((Rslash & (1<<i)) == 0) && ((straight & (1<<i)) == 0)){
			// 記得先把自己加進去，然後再左移右移
			DFS(depth+1, (Lslash | (1<<i))<<1, (Rslash | (1<<i))>>1, (straight | (1<<i)));
		}
	}
}

int main(){
	while(cin>>n && n){
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<n ; j++){
				cin>>arr[i][j];
			}
		}
		ans=0;
		DFS(0, 0, 0, 0);
		cout<<"Case "<<Case++<<": "<<ans<<"\n";
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n^2)$
每筆測資 DFS 時間複雜度為 $O(n^n)$
每筆測資總時間複雜度為 $O(n^n)$

# TOJ 4
## 題目
https://toj.tfcis.org/oj/pro/4/

有 $N$ 個插頭以及電器，分別用長度 $L$ 的 $0/1$ 字串來表示，唯有電器以及插頭完全相同才能配對

現在你只有一種操作方式: 把插頭的某個位元反轉，請問最少需要多少操作才可以讓所有電器以及插頭配對
如果不可能則輸出 `IMPOSSIBLE`

## 想法 By Koios
如果說全部的電器都會對應到一個特定的插頭，那麼第一個電器一定會有一個對應的插頭
枚舉所有插座對應到第一個電器的情況，檢查是否所有的電器跟插座是否匹配

至於如何反轉可以這樣想
要讓插座 $m$ 配對上電器 $n$，那麼需要反轉的位元就是兩兩不相同的位元，可以用 xor 檢查出來，得到 $p = m \oplus n$
接下來要去反轉每個插座 $m_i$，則 $m_i^{'} = m_i \oplus p$

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n, l;
long long change, ans, res, apps[1005], plugs[1005], tmp[1005];
string s;

int main(){
    cin>>t;
    for(int Case=1 ; Case<=t ; Case++){
        cin>>n>>l;
        for(int i=0 ; i<n ; i++){
            cin>>s;
            // 將 0/1 字串轉成數字
            apps[i] = 0;
            for(int j=0 ; j<l ; j++){
                apps[i] |= ((long long)(s[j]-'0')<<j);
            }
        }
		
	// 先排序好，之後比較好判斷是否匹配
        sort(apps, apps+n);
		
        for(int i=0 ; i<n ; i++){
            cin>>s;
            // 將 0/1 字串轉成數字
            plugs[i] = 0;
            for(int j=0 ; j<l ; j++){
                plugs[i] |= ((long long)(s[j]-'0')<<j);
            }
        }
        
        ans = -1;
        for(int i=0 ; i<n ; i++){
            // 只看 apps[0] 以及 plugs[i]
            // 找出需要轉換的 bit
            change = apps[0] ^ plugs[i];
            // 將每個插座轉換後的結果儲存在新的陣列
            for(int j=0 ; j<n ; j++){
                tmp[j] = plugs[j] ^ change;
            }
            // 排序後檢查
            sort(tmp, tmp+n);
            bool found = true;
            for(int j=0 ; j<n ; j++){
                if(apps[j] != tmp[j]){
                    found = false;
                    break;
                }
            }
            
			// 匹配成功
            if(found){
                res = 0;
                while(change){
                    // 操作數等同 change 中 bit 為 1 的數量
                    // 以 lowbit 來找
                    res++;
                    change ^= (change & -change); // lowbit
                }
                if(ans == -1) ans = res;
                else ans = min(ans, res);
            }
        }
        if(ans == -1){
            cout<<"Case #"<<Case<<": IMPOSSIBLE\n";
        }
        else{
            cout<<"Case #"<<Case<<": "<<ans<<"\n";
        }
    }
    return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(NL)$
預先排序 app 的時間複雜度為 $O(NlogN)$
匹配過程重複 $N$ 次，每次切成新插座所需時間複雜度為 $O(N)$，排序時間複雜度為 $O(NlogN)$，檢查時間複雜度為 $O(N)$，計算操作數量時間複雜度為 $O(logL)$
匹配總時間複雜度為 $O(N^2 + N^2logN + NlogL)$
總時間複雜度為 $O(t(NL + N^2 + N^2logN + NlogL))$

---

:::info
TOJ 449 可以參考過去 BFS 這篇(https://hackmd.io/@SCIST/BFS#TOJ-449)，寫法就是位元運算
:::

---

# UVa 124
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?124

給你幾個不重複的小寫英文字母，告訴你某些字母之間的大小關係，把所有從小到大的排列列出來
如果沒有告知某個元素的大小關係，那可以任意擺放

## 想法 By Koios
之前有用 DFS 以及 拓樸排序 的方式寫過這題，現在用位元運算的角度來看

我們可以用數字的 bit 去紀錄字元 $a$ 是否小於字元 $b$
例如說 $b < a$ ，那麼就在記錄 $b$ 小於的數字 $m$ 中第 $0$ (`a`-`a` = 0) 個 bit 紀錄 $1$

接下來當我們透過 DFS 枚舉的過程時，把當前有用到的字元都記錄在一個數字的相對應 bit 上
要判斷某個字元能否放上去，就只需要判斷出現過的字元是否都符合小於的條件即可

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<sstream>
using namespace std;
string s;
int vars, var_num, Less[30];
char x, y, res[30];
bool out=false;

void DFS(int depth, int used){
	if(depth == var_num){
		for(int i=0 ; i<var_num ; i++){
			cout<<res[i];
		}
		cout<<"\n";
		return;
	}
	
	// 枚舉 26 個字母
	for(int i=0, now ; i<26 ; i++){
		now = (1<<i);
		// 判斷
		// 1. 是否為變數表中的變數
		// 2. 過去是否用過
		// 3. 用過的變數是否都小於當前變數
		if((vars & now) != 0 && (used & now) == 0 && (Less[i] & used) == 0){
			res[depth] = 'a'+i;
			// 記得要把自己加進 used
			DFS(depth+1, used|now);
		}
	}
}

int main(){
	while(getline(cin, s)){
		if(out) cout<<"\n";
		else out=true;
		
		vars = var_num = 0;
		// 先將每個人的 less 初始化為 0
		for(int i=0 ; i<30 ; i++){
			Less[i] = 0;
		}
		stringstream ss;
		ss<<s;
		while(ss>>x){
			// 紀錄該字元有出現
			vars |= (1<<(x-'a'));
			var_num++;
		}
		
		getline(cin, s);
		ss.str("");
		ss.clear();
		ss<<s;
		while(ss>>x>>y){
			// 紀錄 y < x
			Less[x-'a'] |= (1<<(y-'a'));
		}
		
		DFS(0, 0);
	}

	return 0;
}
```

---

:::info
UVa 321 可以參考過去 BFS 這篇 (https://hackmd.io/@SCIST/BFS#UVa-321)，寫法就是位元運算
:::

---

# UVa 10393
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10393

給定每個手指在鍵盤上可以輸入的字元
現在有一個人有幾個手指頭受傷沒辦法打特定的字，給一群字串，問所有字串中他可以打出來，並且長度最長的字串有多少個?分別是哪些?
輸出請以字典序大小由小到大輸出，並且每個字串都只能至多出現一次

## 想法 By Koios
我們可以用 bit 去分別記錄特定手指可以寫的字
輸入會告訴我們哪些手指不能用，那我們可以先把不能用的手指可以打得字以位元記錄下來，再反轉後就變成可以打的
實作上可以跟所有可行字元組成的數字 xor 來處理

到目前我們有了當前這個人可以打哪些字元這項資訊，那麼最後只需要判斷每個字是否可以被打出來，然後找出最長的長度即可

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string dict = "qazwsxedcrfvtgb yhnujmik,ol.p;/";
string fig[11] = {"", "qaz", "wsx", "edc", "rfvtgb", " ", " ", "yhnujm", "ik,", "ol.", "p;/"};
string s[1005];
int tbl[128], alltype[32];
int all=0, F, N, cantype, ans, len;
bool res[1005];

int str_to_num(string s){
	int ret = 0;
	for(int i=0 ; i<s.size() ; i++){
		ret |= (1<<tbl[s[i]]);
	}
	return ret;
}

int main(){
	// 預處理建表
	for(int i=0 ; i<dict.size() ; i++){
		tbl[dict[i]] = i;
	}
	for(int i=1 ; i<=10 ; i++){
		// alltype 表示該手指能寫的字元
		for(int j=0 ; j<fig[i].size() ; j++){
			alltype[i] |= (1<<tbl[fig[i][j]]);
		}
		// all 表示全部可以寫的字元
		all |= alltype[i];
	}
	
	while(cin>>F>>N){
		cantype = ans = len = 0;
		for(int i=0, f ; i<F ; i++){
			cin>>f;
			// 先找出不能打的字元
			cantype |= alltype[f];
		}
		// 接下來用 xor 轉換成可以打的字元
		cantype ^= all;
		
		for(int i=0 ; i<N ; i++){
			cin>>s[i];
		}
		
		// 輸出需要依照字母序排序
		sort(s, s+N);
		// 以 res 紀錄該字串是否可以被打出來
		for(int i=0, num, sz ; i<N ; i++){
			// 忽略已經出現過的字串
			if(i>0 && s[i] == s[i-1]){
				res[i] = false;
				continue;
			}
			num = str_to_num(s[i]);
			sz = s[i].length();
			
			// 可以被打出來的情況
			if((num & cantype) == num){
				res[i] = true;
				if(sz > len){
					len = sz;
					ans = 1;
				}
				else if(sz == len){
					ans++;
				}
			}
			else{
				res[i] = false;
			}
		}
		cout<<ans<<"\n";
		// 最後找出可以打的字串中長度是最長的字串
		for(int i=0 ; i<N ; i++){
			if(res[i] && s[i].length() == len){
				cout<<s[i]<<"\n";
			}
		}
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(N)$
每筆測資排序時間複雜度為 $O(NlogN)$
每筆測資找可以被打出來的字串所需時間複雜度為 $O(N)$
每筆測資找答案時間複雜度為 $O(N)$
每筆測資總時間複雜度為 $O(N + NlogN)$

# UVa 12571
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?12571

給定 $N$ 個數字 $x_1, x_2, \dots, x_N$，以及 $Q$ 筆詢問
每筆詢問會有一個數字 $a$，求 $a \& x_i$ 的最大值為多少

$$1 \leq N \leq 100000 \\
1 \leq Q \leq 30000 \\
0 \leq x_i \leq 10^9 \\
0 \leq a < 230
$$

## 想法1 By Koios
雖然說暴力地把每個數字都做 & 一次取最大值會太慢(沒錯，我在這題 TLE 了好幾次)
但是注意到 $a$ 的範圍都在 $230$ 以內，也就是說超過 $2^7$ 這個 bit 的部分都可以直接忽略掉
所以我們就只需要注意所有 $255 = 11111111_2$ 以內的部分即可

找出一開始 $N$ 個數字中所有在 $0$~$255$ 以內的部分記錄起來
接下來如果要詢問，我們只需要針對這 $256$ 個數字檢查是否有出現過，然後找出 & 後的最大值即可

如此一來我們就不需要掃過長度 $N$ 的序列，而只需要掃過長度 $256$ 的序列

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int T, N, Q;
bool used[256];
int main(){
	cin>>T;
	while(T--){
		for(int i=0 ; i<256 ; i++){
			used[i] = false;
		}
		cin>>N>>Q;
		for(int i=0, n ; i<N ; i++){
			cin>>n;
			// 只記錄 255 以內的部分
			used[(n&255)] = true;
		}
		for(int i=0, q, ans=0 ; i<Q ; i++, ans=0){
			cin>>q;
			for(int j=0 ; j<256 ; j++){
				if(used[j]){
					// 出現過就找最大值
					ans = max(ans, (q & j));
				}
			}
			cout<<ans<<"\n";
		}
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(N + Q)$
每筆測資找出 `used` 的時間複雜度為 $O(N)$
令 $M = 256$，每筆詢問時間複雜度為 $O(R)$
總時間複雜度為 $O(t(N + Q + QR))$

## 想法2 By Koios
如果我們直接把整個序列掃過去時間太慢，可能的因素是重複檢查相同的數字
也就是說，有些數字有出現的 bit 可能被其他數字完全覆蓋，那麼我們就只需要找那些盡量多 bit 的做一次 & 運算，其效果等同跟這群數字都做一次 &

舉範例的例子來說，輸入的 $N$ 個數字為 $1, 2, 3$，轉換成二進位後
$$
1 = 01_2 \\
2 = 10_2 \\
3 = 11_2
$$

很顯然的，與其跟三個數字都做一次 &，倒不如只跟 $3$ 做一次 &，因為 $3$ 包含了 $1, 2$ 的所有 bit
那麼我們只要想辦法留下這種會覆蓋掉別人的數字即可

那麼要怎麼篩選呢?
我們可以枚舉每個尚未被篩除的數字跟其他數字做 `|` 運算，如果 $a | b = a$，那就表示 $b$ 的所有 bit 都被包含在 $a$ 裡面

這裡有個優化的想法
那些會被篩掉的數字必定都是被比她還大的數字篩掉的，畢竟大的數字在更高位會出現 $1$
那麼，一開始就把數字排序好，必定可以保證由大到小篩選不會漏篩，而且每次都可以從最後一個篩除的數字往下繼續篩
如此一來就不需要每次都跟全部數字篩看看了

最後只需要把篩出來的數字跟詢問做 & 找最大值即可

> 實作部分用了後面教的內容，可以先忽略，或是嘗試不使用 vector

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int t, n, m, arr[100010];
vector<int> res;
int main(){
	cin>>t;
	while(t--){
		res.clear();
		cin>>n>>m;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		// 排序後來篩，可以明確知道下次要從哪個數字繼續篩，稍微加速所需時間
		// i 表示不篩除的數字編號; j 表示當前要篩選的數字編號
		sort(arr, arr+n);
		for(int i=n-1, j ; i>0 ; i=j){
			res.push_back(arr[i]);
			for(j=i-1 ; (arr[i] | arr[j]) == arr[i] ; j--){}
		}
		for(int i=0, q, ans ; i<m ; i++){
			cin>>q;
			ans=0;
			for(auto j: res){
				ans = max(ans, (q & j));
			}
			cout<<ans<<"\n";
		}
	}

	return 0;
}
```

:::info
複雜度我不太知道要怎麼估，但是至少在 UVa 上是比第一個想法快了 0.02 秒
:::

# UVa 12444
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?12444

給你兩個正整數 $C, D$，其中 $C = A\&B \quad D = A|B$
求兩個正整數 $A, B$ 符合以上條件，並且 $B-A$ 為最小， $A \leq B$
如果沒有任何數字符合以上條件則輸出 $-1$

## 想法
要找到兩個數字 $A, B$ 同時符合 $A\&B = C$ 和 $A|B = D$，那麼至少 $C$ 在二進為底下有 $1$ 的 bit 在 $D$ 上面也要有，所以如果不符合就保證無解

接下來要找到使得 $B-A$ 為最小，那麼我們可以這樣想
比較高位的 bit 必定會比所有比他低位的還大，例如說 $100_{(2)}$ 必定大於 $011_{(2)}$
所以我們只要把最高位的給 $B$，剩下的都給 $A$，那麼兩個一定會是最接近的，也符合 $A \leq B$ 的條件

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int T, C, D, A, B, tmp, highest;
int main(){
	cin>>T;
	while(T--){
		cin>>C>>D;
		// 先判斷不符合條件的
		if((C&D) != C){
			cout<<"-1\n";
		}
		else{
			A = B = C;
			// 透過 xor 可以找到哪些位置需要看
			tmp = C^D;
			// 最高位的要給 B，可以用 log 取整得到
			highest = log2(C^D);
			for(int i=0 ; i<=highest ; i++){
				if((tmp & (1<<i)) != 0){
					if(i == highest){
						B |= (1<<i);
					}
					else{
						A |= (1<<i);
					}
				}
			}
			cout<<A<<" "<<B<<"\n";
		}
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入以及輸出時間複雜度均為 $O(1)$
每筆測資找答案的時間複雜度為 $O(log_{2}{(C \oplus D)})$
總時間複雜度為 $O(T(log_{2}{(C \oplus D)}))$

# Kattis bard
## 題目
https://open.kattis.com/problems/bard

在某個小村莊當中有 $N$ 個村民，並且有一位村民是吟遊詩人
在這個村莊，每個晚上都會聚集一些村民來唱歌
如果晚上吟遊詩人有出現，那麼他會帶來一首新歌，並且當天所有參加的村民都只會唱那首歌，同時彼此都學會了那首新歌
如果當天晚上吟遊詩人沒有出現，那麼所有參加的村民們會將他們所會的歌都唱一遍，同時彼此都學會那些歌

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

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

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

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

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

如此一來就可以模擬出每晚晚會後的結果
在最後可以保證吟遊詩人會所有的歌(畢竟歌是他提供的)，所以接下來只需要判斷所有村民會的歌曲是否跟吟遊詩人相同即可

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

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

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

### 程式碼
```cpp=
//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)$



###### tags: `SCIST 演算法 題解`