1.字典 # 基礎數據類型 # bool int float str list tuple dict set # list dict set 可變數據類型 # bool int float str tuple 不可變數據類型 # 1.字典 dict # dict_data={key: value, ...
二進位是計算技術中廣泛採用的一種數制。二進位數據是用0和1兩個數位來表示的數。利用二進位的特點，可以用於枚舉一個集合中各元素的所有組合情況。
例如，設某集合M中有3個元素A、B和C，即M={A，B，C}。可以用3位二進位數來枚舉3個元素的各種組合情況（也可以稱為子集），每一位二進位數字對應一個元素，1表示選中，0表示不選。
二進位數 001，表示選中A元素，B和C元素不選擇，即子集為 { A }；
二進位數 010，表示選中B元素，A和C元素不選擇，即子集為 { B }；
二進位數 011，表示選中A和B元素，C元素不選擇，即子集為 { A，B }；
二進位數 100，表示選中C元素，A和B元素不選擇，即子集為 { C }；
二進位數 101，表示選中A和C元素，B元素不選擇，即子集為 { A，C }；
二進位數 110，表示選中B和C元素，A元素不選擇，即子集為 { B，C }；
二進位數 111，表示選中A、B和C這3個元素均選中，即子集為 { A，B，C }；
當然，二進位數000表示3個元素均不選擇，就是子集是空集。
這樣，用迴圈 for (int i = 0; i < (1 << n); i++) 就可以遍歷每一個子集，即遍歷各種組合情況。其中 (1 << n)表示 2n ，2n-1就對應n為二進位數，各位上的數字均為1。
然後，可以利用二進位的位運算，來判斷二進位數的某一位上是0還是1。
二進位位運算的左移運算 a << b就表示把a轉為二進位後左移b位（即在後面添b個0）。
這樣， 1<<0=1(0) ; 1<<1=2 (10); 1<<2=4 (100); 1<<3=8 (1000);
……
因此，要判斷一個二進位數x的第k位上是0還是1，只需計算 x & (1<<K)，若計算出來的值為0，則x的第k位為0；若計算出來的值非0，則x的第k位為0。
這樣，再利用迴圈
For (int j = 0; j < n; j++)
if (i & (1 << j)) { … }
就可以對每一個子集中所選取的具體元素進行處理。
編寫如下的示常式序。
#include <stdio.h> int main() { char s[6]="ABCDE"; int n; scanf("%d",&n); int i,j; for (i=0; i<(1<<n); i++) // 枚舉從0～2^n-1中組合情況 { printf("[ "); for (j = 0; j < n; j++) // 遍歷二進位的每一位 { if (i & (1 << j)) // 判斷二進位第j位是否為1，若為1，表示元素選中 { printf("%c ",s[j]); // 如果第j個元素選中，則輸出 } } printf("]\n"); } return 0; }
該程式運行後，輸入3，可以輸出A、B、C這3個元素的8中組合情況。運行結果如下所示。
下麵通過一些實例來看二進位枚舉的應用方法。
【例1】最接近的和
問題描述
給出兩個整數n（n≤20）和b，然後給出n個整數h1、h2、…、hn。問如何在這n個整數裡面選擇若幹個數使得它們的和在滿足大於等於b的情況下最小，並輸出這個和與b的差。
輸入
第1行：2個用空格隔開的整數：N和B。
第2…N+1行：第i+1行是1個整數：Hi。
輸出
輸出1個非負整數，即滿足大於等於b的情況下的最小和值與b的差。
輸入樣例
5 16
3
1
3
5
6
輸出樣例
1
（1）編程思路。
直接套用上面的二進位枚舉的模板對h1、h2、…、hn這n個元素的各種組合情況進行處理。只是在具體處理時，將每次挑選中的元素累加起來。當和值大於等於b時，記錄最小的和值即可。
（2）源程式。
#include <stdio.h> int main() { int n,b; scanf("%d%d",&n,&b); int i,j,h[21]; for (i=0;i<n;i++) scanf("%d",&h[i]); int ans=0x3f3f3f3f; for (i=0; i<(1<<n); i++) // 枚舉從0～2^n-1中組合情況 { int sum=0; for (j = 0; j < n; j++) // 遍歷二進位的每一位 { if (i & (1 << j)) // 判斷二進位第j位是否為1，若為1，表示元素選中 { sum+=h[j]; // 如果第j個元素選中，則加上它 } } if (sum>=b) { if (sum<ans) ans=sum; } } printf("%d\n",ans-b); return 0; }
將上面的源程式提交給 洛谷題庫 P2677 [USACO07DEC]Bookshelf 2 B（https://www.luogu.com.cn/problem/P2677），可以Accepted。
【例2】權利指數
問題描述
在選舉問題中，總共有n個小團體，每個小團體擁有一定數量的選票數。如果其中m個小團體的票數和超過總票數的一半，則此組合為“獲勝聯盟”。n個團體可形成若幹個獲勝聯盟。一個小團體要成為一個“關鍵加入者”的條件是：在其所在的獲勝聯盟中，如果缺少了這個小團體的加入，則此聯盟不能成為獲勝聯盟。一個小團體的權利指數是指：一個小團體在所有獲勝聯盟中成為“關鍵加入者”的次數。請你計算每個小團體的權利指數。
輸入
輸入數據的第一行為一個正整數T，表示有T組測試數據。每一組測試數據的第一行為一個正整數n（0<n<=20）。第二行有n個正整數，分別表示1到n號小團體的票數。
輸出
對每組測試數據，在同一個行按順序輸出1到n號小團體的權利指數。
輸入樣例
2
1
10
7
5 7 4 8 6 7 5
輸出樣例
1
16 22 16 24 20 22 16
（1）編程思路。
同樣直接套用上面的二進位枚舉的模板對n個小團體的各種組合情況進行處理。若某個團體組合的得票數超過了總票數的一半，則依次對該組合中的每個小團隊進行判斷，若去掉了某個小團體後，得票數小於總票數的一半，則去掉的小團體就是關鍵加入者，進行計數。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int t; scanf("%d", &t); while (t--) { int a[21],key[21], ans[21]; memset(ans, 0, sizeof(ans)); int n,total = 0; scanf("%d", &n); int i; for (i = 0; i < n; i++) { scanf("%d", &a[i]); total += a[i]; } total /= 2; for (i = 1; i < 1 << n; i++) // 二進位枚舉各團體組合 { int j, k = 0, sum = 0; for (j = 0; j < n; j++) // 遍歷二進位的每一位 { if (i & (1 << j)) // 判斷二進位第j位是否為1 { key[k++] = j; sum += a[j]; } } if (sum > total) // 如果團體的票數超過總票數的一半 { for (j = 0; j < k; j++) if (sum - a[key[j]] <= total) // 編號為key[j]的元素為 關鍵加入者 ans[key[j]]++; } } printf("%d", ans[0]); for (i = 1; i < n; i++) printf(" %d", ans[i]); printf("\n"); } return 0; }
將上面的源程式提交給 HDU題庫 HDU 1557 權利指數（http://acm.hdu.edu.cn/showproblem.php?pid=1557），可以Accepted。
【例3】目標和習慣
問題描述
小明有很多習慣，比如看電影、聽音樂、玩電腦游戲和足球等等。此外，他還有很多目標，因為不是每個習慣都有助於實現他的目標，他陷入了在目標和習慣之間做出選擇的困境。
現在，我們將一個習慣對每個目標的影響定義為向量，向量的元素是整數，例如。向量（100,90，-10,80）表示它對目標1有100分的影響，對目標2有90分的影響、對目標3有-10分的影響和對目標4有80分的影響（正表示良好效果，負表示不良效果），每個目標的給定要求表示為整數。請幫助小明實現他的目標，並儘可能多地保持他的習慣。
輸入
有多種情況，讀取數據直到EOF。（不超過10例）
第1行：小明的目標數N（0<N<=20）
第2行：每個目標的要求（0<w<=1000）
第3行：小明的習慣數M（0<M<=16）
第4-M+4行：每行包含N個整數，第i個整數表示對第i個目標的影響（-1000<=data<=1000）。
輸出
對於每種情況：輸出是一行，其中包含：
小明可以保持的最大習慣數，其次是：
小明可以保持的習慣的排序列表（從最小到最大）。如果有一組以上的習慣可以滿足要求，請選擇習慣數最少的一組。
如果無法實現小明的目標，請輸出0。
輸入樣例
4
100 200 300 400
3
100 100 400 500
100 -10 50 300
100 100 -50 -50
輸出樣例
2 1 3
（1）編程思路。
採用二進位枚舉對m個習慣的全部組合情況進行處理。對每種習慣組合，將組合中的各習慣對目標的影響累加到數組g中。若數組g中每個目標均可實現，則是一種滿足要求的習慣組合。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int goal[21]; int f[17][21],g[21]; int n; while (scanf("%d",&n)!=EOF) { int ans1=-1,ans2; int i,j,k; for (i=0;i<n;i++) scanf("%d",&goal[i]); int m; scanf("%d",&m); for (i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&f[i][j]); for (i=0;i<(1<<m);i++) // 對所有m個習慣的組合進行枚舉 { for (k=0;k<n;k++) g[k]=0; // 各目標的達到值初始化為0 int num=0; // 當前組合中的習慣個數 for (j=0;j<m;j++) if (i&(1<<j)) // 若組合中有第j個習慣 { num++; for (k=0;k<n;k++) // 第j個習慣對每個目標k的影響 g[k]+=f[j][k]; } for (k=0;k<n;k++) if (g[k]<goal[k]) break; // 第k個目標不能實現 if (k==n) // 當前習慣組合中，所有目標可達成 { if (num>ans1) { ans1=num; ans2=i; } } } if (ans1==-1) printf("0\n"); else { printf("%d",ans1); for (i=0;i<n;i++) if (ans2&(1<<i)) printf(" %d",i+1); printf("\n"); } } return 0; }
將上面的源程式提交給 HDU題庫 HDU 4152 ZZY’s Dilemma（http://acm.hdu.edu.cn/showproblem.php?pid=4152），可以Accepted。
【例4】調查問卷
問題描述
度度熊為了完成畢業論文，需要收集一些數據來支撐他的論據，於是設計了一份包含 m 個問題的調查問卷，每個問題只有 'A' 和 'B' 兩種選項。
將問卷散髮出去之後，度度熊收到了 n 份互不相同的問卷，在整理結果的時候，他發現可以只保留其中的一部分問題，使得這 n 份問卷仍然是互不相同的。這裡認為兩張問卷是不同的，當且僅當存在至少一個被保留的問題在這兩份問卷中的回答不同。
現在度度熊想知道，存在多少個問題集合，使得這 n 份問卷在只保留這個集合的問題之後至少有 k 對問卷是不同的。
輸入
第一行包含一個整數 T，表示有 T 組測試數據。
接下來依次描述 T 組測試數據。對於每組測試數據：
第一行包含三個整數 n，m 和 k，含義同題目描述。
接下來 n 行，每行包含一個長度為 m 的只包含 'A' 和 'B' 的字元串，表示這份問卷對每個問題的回答。
保證 1≤T≤100，1≤n≤103，1≤m≤10，1≤k≤106，給定的 n 份問卷互不相同。
輸出
對於每組測試數據，輸出一行信息 "Case #x: y"（不含引號），其中 x 表示這是第 x 組測試數據，y 表示滿足條件的問題集合的個數，行末不要有多餘空格。
輸入樣例
2
2 2 1
AA
BB
2 2 2
AA
BB
輸出樣例
Case #1: 3
Case #2: 0
（1）編程思路。
先把每張問卷對10個問題回答的A、B字元串轉換成二進位數保存在數組a中，轉換時，A轉換為1，B轉換為0。
採用二進位枚舉的方法依次枚舉每個可能的子集（選擇部分問題的情況，下麵將枚舉到的某個二進位數i稱為當前狀態），與每張問卷的這個子集情況（當前狀態i）下的答案匹配。具體做法是：將當前狀態i與每張試卷的答案（也已轉換為了二進位數並保存在數據元素a[j]中）進行與運算，即now=i & a[j]，並將cnt[now]加1。顯然，若問卷j和問卷k的答案相同，則a[j]與a[k]的值一定相同，這樣now的值也相同，cnt[now]的值會加上2。
當匹配到第j張問卷時，第j張問卷與前面的j-1張問卷在當前選擇狀態i下一定有cnt[i&a[j]]張（包括第j張）的答案相同，也就是有j- cnt[i&a[j]]張的答案存在不同，將它累加到和值sum上。當某個當前狀態i與每張問卷匹配完成後，如果和值sum大於或等於k，這種當前狀態 i 就是符合題意的一種子集選擇。遍歷所有可能的子集，就得到最終的答案。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int t,iCase=0; scanf("%d",&t); while (t--) { int n, m, k; scanf("%d%d%d",&n,&m,&k); int a[1001]; int i,j; for (i=1; i<=n; i++) { char s[15]; scanf("%s",s); int num=0; for (j=0; s[j]!='\0'; j++) // 第i張問卷對10個問題回答的A、B字元串轉換成二進位數保存在數組a[i] { if (s[j]=='A') num=num*2+1; else num=num*2; } a[i] = num; } int ans = 0; for (i=1; i<(1<<m); i++) // 對m個問題的全部組合情況進行枚舉 { int cnt[1050]; memset(cnt, 0, sizeof(cnt)); int sum = 0; for (j=1; j<=n; j++) { int now = i & a[j]; cnt[now]++; sum += j-cnt[now]; } if(sum>=k) ans++; } printf("Case #%d: %d\n",++iCase,ans); } return 0; }
將上面的源程式提交給 HDU題庫 HDU 6344 調查問卷（http://acm.hdu.edu.cn/showproblem.php?pid=6344），可以Accepted。
【例5】連續求餘
問題描述
有一個整數a和n個整數b1，…，bn。在按任意順序從b1、…、bn中選擇一些數字後，例如c1、…、cr，我們希望確保a mod c1 mod c2 mod…mod cr=0（即，a將成為每次除以ci的餘數，最後，我們希望a變為0）。請確定r的最小值。如果無法實現目標，請輸出−1代替。
輸入
第一行包含一個整數T≤5，表示測試用例的數量。
對於每個測試用例，有兩行：
第一行包含兩個整數n和a（1≤n≤20,1≤a≤106)。
第二行包含n個整數b1，…，bn（1≤bi≤106）
輸出
每個測試用例輸出1行，該行中輸出所求得的最小的r值。
輸入樣例
2
2 9
2 7
2 9
6 7
輸出樣例
2
-1
（1）編程思路。
採用二進位枚舉的方法對b1、…、bn中的數的各種選擇組合進行處理。只是在本題處理時，需要先將數組b按從大到小的順序進行排列。因為，若先選擇一個小的數進行求餘，則後面較大的數的選擇毫無意義。
（2）源程式。
#include <stdio.h> int main() { int t; scanf("%d",&t); while (t--) { int n,a,b[25]={0}; scanf("%d%d",&n,&a); int i,j; for (i=0;i<n;i++) scanf("%d",&b[i]); for (i=0;i<n-1;i++) // 將數組b按從大到小的順序排列 for (j=0;j<n-1-i;j++) if (b[j]<b[j+1]) { int temp; temp=b[j]; b[j]=b[j+1]; b[j+1]=temp; } int ans=25; // 所以數全部選，不會超過20個數 for (i=0;i<(1<<n);++i) { int res=a,cnt=0; for (j=0;j<n;++j) { if(i>>j&1) { res=res%b[j]; cnt++; if(res==0)break; } } if (res==0) ans=(cnt<ans)?cnt:ans; } if(ans==25) printf("-1\n"); else printf("%d\n",ans); } return 0; }
將上面的源程式提交給 HDU題庫 HDU 5339 Untitled（http://acm.hdu.edu.cn/showproblem.php?pid=5339），可以Accepted。
在通過上面的5道例題的學習，掌握了二進位枚舉方法的應用的基礎上，可以刷一下HDU題庫中的下麵幾道題目，也均可採用二進位枚舉的方法來完成。
【練習1】HDU 1882 Strange Billboard （http://acm.hdu.edu.cn/showproblem.php?pid=1882）。
#include <stdio.h> #include <string.h> int main() { int r,c; while (scanf("%d%d",&r,&c)!=EOF) { if (r==0 && c==0) break; int i,j,k; char map[20][20],temp[20][20]; for (i=0;i<r;++i) scanf("%s",map[i]); if (r<c) // 若行數小於列數，則使矩陣轉置。 { memcpy(temp,map,sizeof(map)); for (i=0;i<r;++i) { for (j=0;j<c;++j) { map[j][i]=temp[i][j]; } } k=r; r=c; c=k; } int hash[20],key[20]; for(i=0;i<r;++i) // 將第i行數據以二進位形式保存在數組元素hash[i]中，‘X’符號位置1 { hash[i]=0; for (j=0;j<c;++j) { if (map[i][j]=='X') hash[i]=(hash[i]<<1)^1; else hash[i]=(hash[i]<<1); } } int ans=1000; // 按題意，最多256個方格，因此翻轉次數肯定不會超過1000 for (i=0; i<(1<<c); i++) // 對第0行的所有翻轉組合進行二進位枚舉 { int cnt=0; memcpy(key,hash,sizeof(hash)); // 將初始畫面情況數組hash暫存到key數組中 for (j=0;j<c;j++) // 處理第0行（首行） { if (i & (1<<(c-1-j))) { key[0]^=(1<<(c-1-j)); // 當前方塊翻轉 if (j-1>=0) // 當前方塊左邊（前一列）的方塊翻轉 key[0]^=(1<<(c-1-j+1)); if (j+1<c) // 當前方塊右邊（後一列）的方塊翻轉 key[0]^=(1<<(c-1-j-1)); if (1<r) // 當前方塊下方（下一行）的方塊翻轉 key[1]^=(1<<(c-1-j)); cnt++; // 翻轉次數加1 } } for (j=1;j<r;++j) // 上1行確定了，下一行只能根據上一行進行處理。依次處理後面的r-1行 { for (k=0;k<c;++k) // 對當前行的每列的方塊進行判斷，根據正上方的方塊狀態看是否需要翻轉 { if (key[j-1]&(1<<(c-1-k))) // 當前方塊正上方方塊為'X‘，需要翻轉當前方塊 { cnt++; key[j]^=(1<<(c-1-k)); // 當前方塊翻轉 if (k-1>=0) // 當前方塊左邊（前一列）的方塊翻轉 key[j]^=(1<<(c-1-k+1)); if (k+1<c) // 當前方塊右邊（後一列）的方塊翻轉 key[j]^=(1<<(c-1-k-1)); if (j-1>=0) // 當前方塊上方（上一行）的方塊翻轉 key[j-1]^=(1<<(c-1-k)); if (j+1<r) // 當前方塊下方（下一行）的方塊翻轉 key[j+1]^=(1<<(c-1-k)); } } } if (!key[r-1]) // 由於下一行必受上一行約束,則只要判斷最後行是否達到要求即可 { if (ans>cnt) ans=cnt; } } if (ans<1000) printf("You have to tap %ld tiles.\n",ans); else printf("Damaged billboard.\n"); } return 0; }參考源程式
【練習2】HDU 3118 Arbiter （http://acm.hdu.edu.cn/showproblem.php?pid=3118）。
#include <stdio.h> int main() { int t; scanf("%d",&t); while (t--) { int n,m; scanf("%d%d",&n,&m); int map[305][2]; int i,j; for (i=0;i<m;i++) { scanf("%d%d",&map[i][0],&map[i][1]); } int ans=0x3f3f3f3f; for (i=0;i<(1<<n);i++) { int cnt=0; for (j=0;j<m;j++) { if (((i>>map[j][0]) & 1)==((i>>map[j][1])&1)) cnt++; } if (cnt<ans) ans=cnt; } printf("%d\n",ans); } return 0; }參考源程式
【練習3】 HDU 4462 Scaring the Birds （http://acm.hdu.edu.cn/showproblem.php?pid=4462） 。
#include <stdio.h> #include <string.h> int abs(int x) { return x>0?x:-x; } int main() { int n; while (scanf("%d", &n) && n!=0) { int m; scanf("%d", &m); int i,j; int r[51],c[51],f[51]; for (i = 0; i < m; i++) scanf("%d%d", &r[i], &c[i]); for (i = 0; i < m; i++) scanf("%d", &f[i]);
