二進制是計算技術中廣泛采用的一種數制，二進制資料是用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]); int ans = 100; for (i = 0; i < (1 << m); i++) // 二進制列舉各位置放置稻草人的組合情況 { int num = 0; // 放稻草人的個數 int a[10],vis[51][51]; memset(vis, 0, sizeof(vis)); for (j = 0; j < m; j++) if (i&(1 << j)) a[num++] = j; // 保存所放稻草人的編號 int flag = 1; int x,y,z; for (x = 1; x <= n; x++) // 放置了num個稻草人后，看稻田所有位置是否全部覆寫 { for (y = 1; y <= n; y++) { for (z = 0; z < m; z++) if (r[z] == x && c[z] == y) vis[x][y] = 1; if (vis[x][y]) continue; for (z = 0; z < num; z++) { if (abs(x - r[a[z]]) + abs(y - c[a[z]]) <= f[a[z]]) { vis[x][y] = 1; break; } } if (vis[x][y] == 0) // 當前位置(x,y)不能覆寫 flag = 0; if (!flag) break; } if (!flag) break; } if (flag) if (ans>num) ans=num; } if (ans == 100) printf("-1\n"); else printf("%d\n", ans); } return 0; }參考源程式
【練習4】HDU 5616 Jam's balance（http://acm.hdu.edu.cn/showproblem.php?pid=5616），
#include <stdio.h> #include <string.h> int main() { int t; scanf("%d",&t); while (t--) { int vis[2005]; memset(vis,0,sizeof(vis)); int n; scanf("%d",&n); int i,j,a[21]; for (i=0; i<n; i++) scanf("%d",&a[i]); for (i=0; i<(1<<n); i++) // 二進制有n位，列舉二進制數 { int sum=0; // 當前砝碼組合可稱出的總重量 for (j=0; j<n; j++) { if (i&(1<<j)) sum+=a[j]; } vis[sum]=1; for (j=0; j<n; j++) // 將每個砝碼放在天平另一邊 { if (sum-a[j]>=0) vis[sum-a[j]]=1; } } int m,x; scanf("%d",&m); while (m--) { scanf("%d",&x); if (vis[x]) printf("YES\n"); else printf("NO\n"); } } return 0; }參考源程式
【練習5】HDU 6435 Problem J. CSGO （http://acm.hdu.edu.cn/showproblem.php?pid=6435），
#include <stdio.h> int main() { int t; scanf("%d",&t); while (t--) { int n,m,K; scanf("%d%d%d",&n,&m,&K); long long mw[35],sw[35]; // K最大為5,2^5=32，性能組合情況不超過32種 int i,j,k; for (i=0;i<32;i++) mw[i] = sw[i] = -1e16; // 為求最大值，主、副武器的每種性能組合情況均預置一個很小的數 int s,x[6]; long long ret; for (i=0;i<n;i++) // 依次處理每個主武器 { scanf("%d",&s); for (j=0;j<K;j++) scanf("%d",&x[j]); for (j=0;j<(1<<K);j++) // 對當前主武器的性能組合進行二進制列舉 { ret = s; for (k=0;k<K;k++) ret += x[k]*((1&(j>>k))?1:-1); if (mw[j]<ret) mw[j]=ret; } } for (i=0;i<m;i++) // 依次處理每個副武器 { scanf("%d",&s); for (j=0;j<K;j++) scanf("%d",&x[j]); for (j=0;j<(1<<K);j++) // 對當前副武器的性能組合進行二進制列舉 { ret = s; for (k=0;k<K;k++) ret += x[k]*((1&(j>>k))?1:-1); if (sw[j]<ret) sw[j]=ret; } } long long ans = 0; for (i=0;i<(1<<K);i++) { ret=mw[i]+sw[(1<<K)-1-i]; // 主、副武器二進制位要求互補 if (ans<ret) ans=ret; } printf("%lld\n",ans); } return 0; }參考源程式
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538363.html
標籤：其他
上一篇：python中的字典和集合