關(guān)于bitset
bitset 的用法
bitset 是一個存 0/1 的大小不可變的容器,它的空間效率和時間效率極其快,快 32 倍,所以會被用于一些暴力優(yōu)化成正解。
個人的理解,這個東西把一大堆壓到了一塊,相當于一個小分塊,所以才變快了,手寫一個也就是把一個 ull 當作 64 個位置存。
記一下這個玩意的用法吧。
聲明
聲明也就很簡單。
點擊查看代碼
bitset <MN> s;
別忘了這個是固定大小的。
訪問,修改
支持下標訪問
點擊查看代碼
s[0]=1;
cout<<s[114514]<<'\n';
這個東西也支持各種各樣的位運算。
點擊查看代碼
s<<=x;
s>>=x;
s&=s1;
s|=s1;
s^=s1;
這基本上就夠用了。
一些函數(shù)
這邊僅僅寫一些自認為有用的。
重置用 reset, 全都便成 0。
點擊查看代碼
s.reset();
大規(guī)模設(shè)置用set, 第一個參數(shù)是 pos, 第二個參數(shù)是 val;
如果什么都不傳默認把所有的位置都設(shè)為 1, 時間復(fù)雜度 \(O(\frac{n}{w})\)
點擊查看代碼
s.set();
s.set(1);
s.set(1,0);
any 如果存在1就返回 true;
點擊查看代碼
cout<<s.any();
none 如果都是 0 返回 true。
點擊查看代碼
cout<<s.none();
all 如果全部都是 1 則返回 true。
點擊查看代碼
cout<<s.all();
count 返回 1 的個數(shù)
點擊查看代碼
cout<<s.count();
flip 對每一位取反,如果加上 pos 就是這一位。
點擊查看代碼
s.flip();
s.flip(1);
_Find_first 會返回第一個 1 的位置,不存在返回大小。
點擊查看代碼
cout<<s._Find_first();
_Find_next 返回位置嚴格大于 pos 的第一個 1 的位置。
點擊查看代碼
cout<<s._Find_next(1);

浙公網(wǎng)安備 33010602011771號