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';
}