從零開始的演算法競賽入門教學
0%

0-25 bitset

發表於

bool 陣列

1
bool arr[1000005];

bitset

bitset 是特別優化過的 bool 陣列，時間與空間均較 bool 陣列少，其中以時間的影響最為顯著。

bitset 的語法如下：

1
bitset<1000005> b;

特別的地方是，<> 內放的是大小。

語法

跟 bool 陣列一樣

1
2
b[5] = 0;
b[4] = 1;

有一些特別的函式

1
cout << b.count() << '\n';

.count() 回傳 bitset 中 1 的個數。

1
2
3
4
b.set();
cout << b[1] << '\n';
b.reset();
cout << b[1] << '\n';

.set() 將所有 bit 設為 1，.reset() 將所有 bit 設為 0。

比 bool 陣列快的地方

bitset 可以進行位元運算！

位元運算的速度極快，大約可視為正常的 1/32 倍。因此 bitset 能做到一些沒有其他方法能做到的神奇事情。

但… 這些事情超少的，我也只在比賽中看過一題，然而就是那一題，讓我進了二階。那題稍微有點難，可能放在這不太適合，就先放其他題目吧！

TOJ 126

這題的重點是，要如何知道一個數是不是合理的。

假設現在合理的分數是(-2, -1, 0, 1, 2)，有一題 2 分的題目，那麼在作答完這題後，可能的分數就是這題答對與這題答錯的聯集。

這題答對的話，可能的分數會變成(0, 1, 2, 3, 4)，答錯的話，可能的分數會變成(-4, -3, -2, -1, 0)，所以考慮答對跟答錯的情況，可能的分數是兩者的聯集，也就是(-4, -3, -2, -1, 0, 1, 2, 3, 4)。

假設把可不可能用 bitset 表示，bitset 中若第 i 項是 1，表示 i 是可能的分數，反之 0 是不可能，那麼，若原來的 bitset 是 b，答了一題分數為 2 的題目後，這個 bitset 就會變成 (b >> 2) | (b << 2)。

b >> 2 表示答錯的狀況，可能的分數右移兩格(-2, -1, 0, 1, 2) -> (-4, -3, -2, -1, 0)， b << 2 表示答對的狀況，可能的分數左移兩格(-2, -1, 0, 1, 2) -> (0, 1, 2, 3, 4)。| 將兩者聯集起來。這樣的話，本來需要 N 次的操作，在 bitset 的使用下，變成只需要 N / 32 次了！

在位元運算時，bitset也不用擔心會 RE，超過的部分都會自動捨去，沒有問題！(但是可能會WA就是了)

另外，這題其實是一題經典問題：背包(knapsack)問題的一種變形，有興趣的話可以針對這個主題進行學習。之後應該也會有一篇專門的文章來介紹我所知道的背包問題們。

bitset 的使用時機非常少，但無可替代。

練習

TOJ 126

Hackerrank Acyclic Graph

AC 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
// TOJ 126
// 因為index沒有負數，因此全部加上 10000 處理。
#include<bits/stdc++.h>
using namespace std;

int n, q, ans[20005];
bitset<20005> b;

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	b[10000] = 1; // b[0] = 1
	for(int i=1,x;i<=n;i++){
		cin >> x;
		b = (b >> x) | (b << x);
	}
	for(int i=20000,pre=i;i>=0;i--){
		if(b[i]) pre = i;
		ans[i] = pre;
	}
	for(int i=1,x;i<=q;i++){
		cin >> x;
		cout << ans[x+10000] - 10000 << '\n'; // cout << ans[x] << '\n';
	}
}

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
// Acyclic graph
// 建議先了解 dfs 與 vector 存圖 以及 DAG
// 先備知識有點多 可以跳過 之後再回來
#include <bits/stdc++.h>
using namespace std;

bitset<50005> b[50005], vis;
int n, m, in[50005];
vector<int> E[50005];

void dfs(int x){
    vis[x] = 1;
    b[x][x] = 1;
    for(auto i:E[x]){
        if(!vis[i]) dfs(i);
        b[x] |= b[i];
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i=1,a,b;i<=m;i++){
        cin >> a >> b;
        E[a].emplace_back(b);
        in[b]++;
    }
    for(int i=1;i<=n;i++){
        if(!in[i]) dfs(i);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(b[i].count()*2>=n) ans++;
    }
    cout << ans << '\n';
}