在撰寫程式解決某些問題時，可以靈活地使用進位制數，例如像二進制列舉就是靈活使用二進制數，下面再講述一些例題，
1、二進制的應用
【例1】至少一位數字相同
問題描述
給定N個正整數A1，A2，...，AN，求有多少整數對(i,j)，滿足以下條件：
1≤i<j≤N，Ai和Aj至少有一位數字是相同的（不一定要在相同的數位），
輸入
輸入的第一行包含一個正整數N，
接下來N行，每行包含一個正整數Ai，
輸出
輸出一行一個整數，表示滿足條件的整數對的數目，
輸入樣例
4
32
51
123
282
輸出樣例
4
（1）編程思路，
以樣例為例說明，共有4組整數對滿足條件，（32，123）、（32，282）、（51，123）和（123，282），
顯然，若采用二重回圈兩兩組合來判斷每組數中是否至少有一位數字是相同的，在資料量較大的情況下，不是一個可取的方法，
實際上要判斷兩個整數是否至少有一位數字是相同的，我們是不在乎兩個數的每一個數位是什么、哪幾個位上的數字相同，只用關心0~9這9個數字中是否有某個數字在兩個數中都出現過，若都出現過，則兩個數至少有一位數字是相同的，
由于十進制中只有0~9共10個數碼，因此可以用一個10位的二進制數來表示一個十進制整數X的型別，這個二進制數的第k（0≤k≤9）位為1表示整數X中含有數字k，若數字k在整數X中沒出現，則對應二進制數的第k位為0，
用陣列a來保存各型別整數的個數，顯然任何一個正整數的型別一定在 [0,1023]之間，即陣列a最多有1024個元素，初始時，陣列a的元素值全部置為0，
還是以樣例中的4個數為例，
整數32中含有2、3這兩個數字，對應二進制數為0000001100，數的型別號為12，a[12]加1，a[12]=1，
整數51中含有1、5這兩個數字，對應二進制數為0000100010，數的型別號為34，a[34]加1，a[34]=1，
整數123中含有1、2、3這3個數字，對應二進制數為0000001110，數的型別號為14，a[14]加1，a[14]=1，
整數282中含有2、8這兩個數字，對應二進制數為0100000100，數的型別號為260，a[260]加1，a[260]=1，
這樣處理后，再求N個正整數中滿足要求的整數對的數量ans（初值為0）就很方便了，分兩種情況處理，
1）兩個整數的型別相同，則同型別中任意取兩個數就滿足要求，用回圈對a[0]~a[1023]中各a[i]值進行遍歷，若 a[i]!=0，則 ans=ans+a[i]*(a[i]-1)/2，
2）兩個整數的型別不同，設一個型別為i，一個型別為j （設i<j），若 i & j的值不為0，則i和j對應的二進制數一定在某個位上都是1，也就是存在相同的數字（某個位都為1），這樣，a[i]和a[j]中各取1個數就滿足要求， ans=ans+a[i]*a[j]，
（2）源程式，
#include <stdio.h> int main() { int n; scanf("%d",&n); int i,j; long long a[1024]={0}; int min=1024,max=0; for (i=1;i<=n;i++) { long long x; scanf("%lld",&x); int h[10]; // 記錄0~9每個數字在x中是否出現 for (j=0;j<10;j++) h[j]=0; while(x) { h[x%10]=1; // 數字x%10出現了，h[x%10]記為1 x/=10; } int num=0; for (j=0;j<10;j++) { num=num*2+h[j]; // 將h[0]~h[9]中保存資料作為二進制數轉換為十進制數num } a[num]++; // num這種數增加1個 if (num>max) max=num; if (num<min) min=num; } long long ans=0; for (i=min;i<=max;i++) // 同一種數內兩兩組合 ans+=a[i]*(a[i]-1)/2; for (i=min;i<max;i++) // 不同種類的數兩兩組合 { for (j=i+1;j<=max;j++) if (i & j) ans+=a[i]*a[j]; } printf("%lld\n",ans); return 0; }
將上面的源程式提交給洛谷題庫 P7617 [COCI2011-2012#2] KOMPI?I （https://www.luogu.com.cn/problem/P7617），可以Accepted，
【例2】異或和
問題描述
給定一個長度為N的序列A1，A2，...，AN，求序列元素兩兩異或的總和，
例如，某序列中有3個數，A1=7，A2=3，A3=5，
則有 A1 ⊕ A2 = 4，A1 ⊕ A3 = 2，A2 ⊕ A3 = 6，
4 + 2 + 6 = 12，因此序列元素兩兩異或的總和為12，
輸入
輸入的第一行包含一個正整數N（1≤N≤106），
接下來N行每行包含一個正整數Ai（1≤Ai≤106），
輸出
輸出一行一個整數，表示兩兩異或后的總和，
輸入樣例
3
7
3
5
輸出樣例
12
（1）編程思路，
若通過二重回圈對序列中的資料進行兩兩組合求異或和，在資料量大的情況下肯定是超時的，
首先，我們考慮一個數轉成二進制后每個位的操作，每個位上的資料只能是0或1，其異或運算規則是： 0和1 異或得1 ， 1和1 或者 0和 0 異或得0 ，怎么求多個0 和1 的兩兩異或和呢？
舉個例子： 0，1，0 三個數兩兩異或和應該是：0 異或 1 加上 0 異或0 再加上 1 異或 0，和值sum=1+0+1=2 ，從中可以發現，每個 0 和一個 1 進行異或，和sum 就要加 1 ，也就是說每一個 0 都會使 sum 加上 1 的個數（因為 0 要和 1 的個數個 1 異或），設在n個0、1序列中有x 個1 ，則有 n-x個0，這樣兩兩異或的和值sum 就等于 0 的個數乘 1 的個數，也就是 sum=(n?x)*x ，
現在要對N個正整數序列求兩兩異或和，具體做法是：
將原序列中的每個元素都轉換為二進制，并用一個陣列 a 記錄序列中全部元素各二進制數中每一位1 的個數，最后用一個回圈，將二進制每一位的兩兩異或和都算出來，累加到和值sum中，
n 個數中第i 位上每一對 0 和 1 都能造成 2i 的貢獻，在n個數中，已求出各二進制數第i位上有a[i]個 1，有 n-a[i]個 0，而每個 0都和a[i]個 1 都能造成2i的貢獻，所以
sum=sum+a[i]*(n?a[i])*2i ，
以樣例為例說明，7 對應二進制數為 111，因此，a[0]=a[0]+1，a[1]=a[1]+1，a[2]=a[2]+1，由此，a[0]=1，a[1]=1，a[2]=1，
3 對應二進制數為 11，因此，a[0]=a[0]+1，a[1]=a[1]+1，由此，a[0]=2，a[1]=2，a[2]=1，
5 對應二進制數為 101，因此，a[0]=a[0]+1，a[2]=a[2]+1，由此，a[0]=3，a[1]=2，a[2]=2，
為此，在異或和的和值sum中， 第0位貢獻 3*0*1=0，第1位貢獻 2*(3-2)*2=4，第2位貢獻 2*(3-2)*4=8，因此，和值sum=0+4+8=12，
（2）源程式，
#include <stdio.h> int main() { int n; scanf("%d",&n); int i,a[25]={0},len=0; for (i=1;i<=n;i++) { int x; scanf("%d",&x); int k=0; while(x) // 將x轉為二進制 { a[k]=a[k]+x%2; // 如果第k位是1，則a[k]加1 x/=2; k++; } if (len<k) len=k; // 各數對應二進制數的最長位數 } long long ans=0; for (i=0;i<len;i++) ans+=1ll*a[i]*(n-a[i])*(1<<i); printf("%lld\n",ans); return 0; }
2、三進制的應用
【例3】天平稱重
問題描述
給你一臺天平，一件貨物重m公斤，然后給你一些重1，3，9，27，…，3^k的砝碼，當然，不同權重的砝碼數量只有一個，
現在把貨物放在天平的左邊，然后你應該在天平的兩邊放一些砝碼，使天平平衡，
輸入
整數m表示貨物的重量（0≤ m≤ 100 000 000)
輸出
您應該輸出兩行，
在第一行中，第一個整數N1是放在天平左邊的砝碼的數量，然后N1個整數（按升序），表示放在左邊的各砝碼的重量，每個數用一個空格隔開，
在第二行中，請使用與第一行相同的方式輸出N2，即右側放置的砝碼數，然后，按照升序排列的N2個整數表示放在右邊的各砝碼的重量，
輸入樣例
42
30
輸出樣例
3 3 9 27
1 81
0
2 3 27
（1）編程思路，
可以看出砝碼重量1、3、9、27、…正好是一個三進制數各位上的權值，因此應考慮三進制數的應用，
稱重時砝碼可以放在左盤（物體盤），也可以放在右盤（砝碼盤），若砝碼只放在右盤，則 物體質量=砝碼盤砝碼質量；若右盤和左盤中都放置了砝碼，則 物體質量=右盤砝碼質量-左盤砝碼質量，這樣，由于可以把砝碼加在天平的左盤中，因此，放在左盤中的砝碼不是要加在稱出的質量上面，而是要從中減去的數，例如，5=9-3-1、6=9-3、7=9+1-3等等，
為了達到這個目的，設所用的三進制數碼不是通常的0、1、2，而是-1、0、1，即2可以寫成3-1，將其轉化成-1這個數字，為了描述簡便，把-1寫成i，以后只要在三進制中碰到2這個數字，就把它改寫成1i（即3-1=2），例如，三進制中的22102這個數，可以用下面的方法改寫成10i11i，
22102 = 20000 + 2000 + 100 + 2 = 1i0000 + 1i000 +100 + 1i
= 1i0000 + 1i000 +11i = 1i0000 + 1i11i = 10i11i
來看幾個實際克數的稱重情況，
例如，為了稱出14克，先將14化成普通三進制112，再進行改寫，112=100+10+1i=100+2i=100+20+i = 100 +1i0 +i =100 +1ii = 2ii =1iii，這就是說，把27這塊砝碼放進右盤，而把9、3、1三塊砝碼放進左盤中，就可以稱出14克出來（27-9-3-1=14），
再看怎樣稱出26克來，26化成普通三進制222，進行改寫，222=1i00+1i0+1i=1i00+10i=100i，這就是說，把27這塊砝碼放進右盤，而把1這塊砝碼放進左盤中，就可以稱出26克出來（27-1=26），
因此，本題的處理辦法是：
先將輸入的十進制數n轉換為3進制數，轉換后得到的各位三進制數字保存在陣列a中，然后對陣列a中的值從低位向高位進行校正，校正方法為：
若 a[i]的值為2，則變為 -1， 同時 a[i+1]加1（相當于向前1位進位）；
若 a[i]的值為3，則變為 0， 同時向前1位進位，即 a[i+1] 加1；
若 a[i]的值 為0 或 1 時保持不變，
之后將a[i]值為1所對應的重為3i的砝碼放在右盤中，a[i]值為-1 所對應的重為3i的砝碼放在左盤中，就是問題的答案，
（2）源程式，
#include <stdio.h> int main() { int table[21]; // table[i]保存3的i次方的值 table[0]=1; int i; for (i = 1; i < 20; i++) // 預先求得3的1次方~3的19次方值保存到陣列table中 table[i]=table[i-1]*3; int n; while (scanf("%d", &n)!=EOF) { int len = 0; int a[21]; while (n!=0) // 將n轉換為3進制數，并將各位數字保存到陣列a中，a[0]保存最低位數字 { a[len++] = n % 3; n = n / 3; } a[len]=0; // 最高位的前面先補個0 int lcnt=0,rcnt=0; // 分別保存放在天平左端和天平右端的砝碼個數 for (i=0;i<len;i++) // 從低位到高位對3進制數進行校正 { if (a[i]==1) rcnt++; if (a[i]==2) { a[i]=-1; a[i+1]++; lcnt++; } if (a[i]==3) { a[i]=0; a[i+1]++; } } if (a[len]!=0) { rcnt++; len++; } printf("%d",lcnt); for (i=0;i<len;i++) if (a[i]==-1) printf(" %d",table[i]); printf("\n"); printf("%d",rcnt); for (i=0;i<len;i++) if (a[i]==1) printf(" %d",table[i]); printf("\n"); } return 0; }
將上面的源程式提交給 HDU 3029 Scales （http://acm.hdu.edu.cn/showproblem.php?pid=3029），可以Accepted，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539588.html
標籤：C