# 演算法課程題解 - 位元運算
# 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 演算法 題解`
Sign in with Wallet
Connect another wallet