c++ bitset 是個比較有用的東西
說的高深點這是：
C++語言的一個類庫，用來友善地管理一系列的bit位而不用程式員自己來寫代碼。
bitset除了可以通路指定下标的bit位以外，還可以把它們作為一個整數來進行某些統計。
說的簡單一點，這是：
一個可以用位運算的數組，也用于32位的壓縮。
是不是簡單易懂，
他的一般定義：
#include<bitset>
bitset<2000000>f;
就可以使用f:
f[i]=a; f=f<<a; 如此
接下來附兩道：
1302: 裝箱問題
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 278 解決: 185
[ 送出][ 狀态][ 讨論版]
題目描述
有一個箱子容量為v（正整數，0<=v<=20000),同時有n個物品（0<n<=30），每個物品有一個體積（正整數）。
要求從n個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。
輸入
箱子的容量v
物品數n
接下來n行，分别表示這n個物品的體積
輸出
箱子剩餘空間
樣例輸入
24 6 8 3 12 7 9 7
樣例輸出
提示
來源
DP—背包
[ 送出][ 狀态][ 讨論版]
這是一道水到不能再水的水題，先附普通版，
#include
#include
#include
#include
#include
#include
#include
using namespace std; typedef long long ll; typedef long double ld; typedef pair
pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof(a)) #define pb push_back #define mp make_pair #define fi first #define sc second #define pq priority_queue #define pqb priority_queue
, less
> #define pqs priority_queue
, greater
> #define vec vector ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a
>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; ll read(){ ll ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } //頭檔案 int f[20000]; int main() { int v=read(),n=read(); f[0]=1; rep(i,1,n) { int a=read(); per(x,v,a) f[x]=f[x]|f[x-a]; } per(i,v,0) if (f[i]) { cout<
再來bitset:
#include
#include
#include
#include
#include
#define LL long long #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=a;i>=b;i--) #define inf 1<<29 #define clr(i,c) memset(i,c,sizeof(i)) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #include
bitset<20000>f; int main() { f[0]=1; int v=read(); int n=read(); while (n--){ int x=read(); f=f|(f<
又來一題：
2096: bitset習題
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 29 解決: 21
[ 送出][ 狀态][ 讨論版]
題目描述
小呆開始研究集合論了，他提出了關于一個數集四個問題：
1. 子集的異或和的算術和。
2. 子集的異或和的異或和。
3. 子集的算術和的算術和。
4. 子集的算術和的異或和。
目前為止，小呆已經解決了前三個問題，還剩下最後一個問題還沒有解決，他決定把
這個問題交給你，未來的集訓隊隊員來實作。
輸入
第一行，一個整數 n。
第二行，n 個正整數，表示 a1, a2, …, an
輸出
一行，包含一個整數，表示所有子集和的異或和。
樣例輸入
21 3
樣例輸出
6【樣例解釋】6 = 1 ⊗ 3 ⊗ (1 + 3)【資料規模與約定】資料分為 A,B,C 三類。A 類資料 (20%) 保證：ai > 0，1 ≤ n ≤ 10。B 類資料 (40%) 保證：ai > 0，1 ≤ n ≤ 1000，∑ ai ≤ 10000。C 類資料 (40%) 保證：ai > 0，1 ≤ n ≤ 1000，∑ ai ≤ 2000000。另外，不保證集合中的數滿足互異性，即有可能出現 ai = aj 且 i ̸= j。
提示
來源
[ 送出][ 狀态][ 讨論版] 上代碼：
#include
#include
#include
#include
#include
#include
#include
using namespace std; typedef long long ll; typedef long double ld; typedef pair
pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof(a)) #define pb push_back #define mp make_pair #define fi first #define sc second #define pq priority_queue #define pqb priority_queue
, less
> #define pqs priority_queue
, greater
> #define vec vector ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a
>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; ll read(){ ll ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } int f[2000000],ans; int main() { f[0]=1; int n=read(); rep(i,1,n){ int a=read(); per(i,2000000,1) f[i]=f[i]^f[i-a]; } per(i,2000000,1) if (f[i]) ans^=i; cout<
#include
#include
#include
#include
#include
#define LL long long #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=a;i>=b;i--) #define inf 1<<29 #define clr(i,c) memset(i,c,sizeof(i)) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #include
bitset<2000000>f; int ans; int main() { f[0]=1; int n=read(); while (n--){ int x=read(); f=f^(f<