引子

萬戶涕淚，一人冠冕，其心尚有“共和”二字存耶？既忘共和，即稱民賊。吾儕昔以大仁大義鑄此巨錯，又焉敢不犯難，誓死戮此民賊，以拯吾民。

今長江大河，萬里以內，武漢京津，扼要諸軍，皆已暗受旗幟，磨劍以待。一旦義旗起，呼聲動天地。當以秦隴一軍，出關北指；川楚一軍，規(guī)畫中原；閩粵旌旗橫海，合齊魯以搗京左。三軍既興，我將與諸君子扼揚子江口，定蘇浙，以樹東南之威。掣庭掃穴，共戮國賊，期可指日待焉。書曰：“民惟邦本，本固邦寧?！庇衷唬骸凹q有臣億萬，惟億萬心。予有臣三千，惟一心?！闭x所至，何堅不破？愿與愛國之豪俊共圖之！

bitset實際上是通過固定優(yōu)化，使得一個字節(jié)的八個比特能分別儲存 8 位的 0/1。對于一個 4 字節(jié)的 int 變量，在只存 0/1 的意義下，bitset 占用空間只是其\( [\frac{1}{32}]\)，計算一些信息時，所需時間也是其$[\frac 1{32}] $。一般來說可以將原時間復雜度為 \(O(Q)\)的程序，優(yōu)化為\(O( \frac Q w)\) ，其中為\(w\)為計算機位數。

基本操作

1. 初始構造

bitset<1000> bs;// a bitset with 1000 bits

bitset()//每一位都是 false。
bitset(unsigned long val)://設為 val 的二進制形式,bitset 二進制由低位至高位存儲
bitset(const string& str)://設為01串 str。

2. 運算符 總之就是支持各種位運算

operator []//訪問其特定的一位。

operator == !=//比較兩個 bitset 內容是否完全一樣。

operator & | ^ &= |= ^= ~//進行按位與/或/異或/取反操作。


//注意：bitset 只能與 bitset 進行位運算，若要和整型進行位運算，要先將整型轉換為 bitset。

operator << >> <<= >>=//進行二進制左移/右移。

3. 成員函數：這里只提幾個常用的，如有需要可以去\(OI-wiki\)上翻

count()//返回 true 的數量
size()//返回 bitset 的大小
any()// 若存在某一位是 true 則返回 true，否則返回 false
none()// 若所有位都是 false 則返回 true，否則返回 false
all()//若所有位都是 true 則返回 true，否則返回 false
set()//將整個 bitset 設置成 true
set(pos, val = true)//將某一位設置成 true/false
reset()// 將整個 bitset 設置成 false
reset(pos)//將某一位設置成 false相當于 set(pos, false)
flip()//翻轉每一位，相當于異或一個全是 [1] 的 bitset
flip(pos)// 翻轉某一位

P1356 數列的整除性

思路很好想，明顯可以用bitset優(yōu)化

POJ 2443 Set Operation

大概題意是給你n個集合,詢問是否存在一個集合同時存在x,y。
直接將\(bool\)改為\(bitset\)即可

簡單瞎搞題

emmm，很簡單的柿子，我們發(fā)現空間達到了\(1e8\)，原題只給了\(32M\)，很自然想到用bitset來優(yōu)化

f[0].flip(0);
for(int i=1;i<=n;i++) {
   l=read(),r=read();
   for(int j=l;j<=r;j++) f[i]|=(f[i-1]<<(j*j));
}

Backpack(2022“杭電杯”)

柿子很好想 \(f_{i,j,k}|=f_{i-1,j \oplus w,k-v}\)

復雜度不對？ \(bitset!\)

int p=1;f[0][0][0]=1;
for(int i=1;i<=n;i++) {
    for(int j=0;j<1024;j++)
      f[p][j]=f[p^1][j^w[i]]<<v[i]|f[p^1][j];
	p^=1;
}
int sum=0;
for(int i=0;i<1024;i++) 
    if(f[n&1][i][m]) sum=i;

[ABC258G] Triangle

根號分治，沒啥好說的

P5670 異或秘籍

只關心\(m\)個二進制位，那么是不是高位就沒有意義了？

考慮取模，維護各個數字是否存在，想想bitse注意上的數是否存在

加上一個數k，實際就相當于\(t[p]=(t[p]<<k)|(t[p]>>1024-k)\)，注意不能只維護小于\(2^m\)的數，因為關注的是二進制位，所以保留多少要與值域有關

線段樹維護即可，碼有點長，不放

CF633G

和上面的思路一樣，維護每個數字是否出現即可，當然還有一個抽象思路，這里不再敘述

這道題非常的好，順便把樹剖給大家復習了

P3674 小清新人渣的本愿

插個眼先