進位制專題

MT2186 二進制？不同！

難度：黃金 ?? 時間限制：1秒 ?? 占用內存：128M

題目描述

小碼哥是一個對數很敏感的人，即使給他很多個很像的數串，他都能找出沒有出現過的數串。
或許是有些無聊，小碼哥給你一個字符串數組 nums，里面包含 $n$ 個二進制字符串（長度都為 $n$ )，現請你找出不在數組中的二進制字符串。若有多解，返回對應十進制最小的一個。

格式

輸入格式：一行二進制字符串數組，字符串之間以空格分割；
輸出格式：一個不在數組中的二進制字符串。

樣例 1

輸入：01 10

輸出：00

備注

其中： $\le n \le 16$ ，nums中所有字符互不相同。

相關知識點：進位制

題解

本題要求找出尚未在輸入數據中出現的最小值（所有數據的最小取值為 0）。但是題目給出的數據為二進制字符串（合法的），因此為了找出最小未出現的數，我們需要先將所有輸入的二進制字符串轉換為十進制數，并將這些數存放進一個集合 nums 中。接下來，從 0 開始逐步向后枚舉整數，一旦存在某個數不在集合 nums 中，就說明這個數是尚未在輸入數據中出現的最小數。注意：我們還需對這個數進行格式轉換！即將這個數由十進制再轉換為二進制字符串（長度需要和輸入數據的長度一致）。

下面直接給出求解此題的完整代碼（已 AC）：

/*MT2186 二進制？不同！ 測試數據：001 100 000  
*/
#include<bits/stdc++.h> 
using namespace std;set<int> nums;// 該函數將（合法的）二進制數字串轉換為十進制數字 
int getDecFromBin(string str)
{int sum = 0, base = 1;for(int i=str.size()-1; i>=0; i--){sum += base*(str[i]-'0');base *= 2;}return sum;
} // 將一個十進制數轉換為指定長度的二進制字符串
string toBinary(int n, int len)
{string str = "";while(len--){if(n&1) str = "1"+str;else str = "0"+str;n >>= 1;}return str;
} int main( )
{// 輸入數據string str;while(cin>>str)nums.insert(getDecFromBin(str));// 記錄當前輸入二進制字符串的長度int binStrlen = str.length();// 尋找最小值，并在進行格式轉換后輸出 for(int i=0; ; i++){// 找到一個尚未在集合中出現的最小數值if(nums.find(i) == nums.end()){cout<<toBinary(i, binStrlen)<<endl;break;}}return 0;
}

MT2187 excel的煩惱

難度：鉆石 ?? 時間限制：2秒 ?? 占用內存：128M

題目描述

你用過 Excel 么?
在 excel 中，第一列被標為 A，第二列為 B，以此類推，第 26 列為 Z。接下來為由兩個字母構成的列號：第 27 列為 AA，第 28 列為 AB……在標為 ZZ 的列之后則由三個字母構成列號，如此類推。
行號為從 1 開始的整數。
單元格的坐標由列號和行號連接而成。比如，BC23 表示位于第 55 列 23 行的單元格。
有時也會采用被稱為 RXCY 的坐標系統，其中 X 與 Y 為整數，坐標 (X, Y) 直接描述了對應單元格的位置。比如，R23C55 即為前面所述的單元格。
小碼哥請你編寫一個程序，將所給的單元格坐標轉換為另一種坐標系統下面的形式。

格式

輸入格式：第一行一個整數 T(1≤T≤10^5) 表示將有 T 次詢問；
?????接下來 T 行，每行一個坐標。
輸出格式：輸出 T 行，每行一個被轉換的坐標。

樣例 1

輸入：3
???R12C3
???AE32
???BB11

輸出：C12
???R32C31
???R11C54

備注

每個坐標都是正確的。保證輸入輸出數據均在int范圍內。輸入輸出數據字母部分均為大寫。

相關知識點： 進位制

題解

這道題表面是在對兩種坐標形式進行轉換，但實際上也是在考察進制轉換。例如，對于 excel 形式的坐標，其列號 BC 對應在十進制中為 55（ $2×26^1+3×26^0=55$ ），所以題中將 BC23 解析為第 55 行第 23 列的單元格。因此，這里的進制轉換問題實際上是十進制與以 $A ? Z$ 表達的二十六進制數之間的互相轉換。

對于本題，由于輸入數據并沒有說明其具體是哪一種形式的坐標表達，因此我們需要做的第一件事是識別坐標格式。觀察兩種形式的坐標不難發現，excel 形式的坐標是 “字母+數字”，而 RXCY 形式的坐標是 “字母+數字+字母+數字”，這兩種形式的本質區別在于：RXCY 的格式中，會在數字的后面出現字母；而 excel 形式下，數字后面不可能出現字母。因此可以根據這一本質區別進行格式識別，并在后續進行格式轉換。

當完成了對輸入坐標字符串的格式檢測后，便能分別進行格式轉換了。具體的轉換過程并不難（詳細細節可看這之后的例題：MT2189 三進制計算機1、MT2190 三進制計算機2），下面直接給出求解本題的完整代碼（已 AC）：

/*MT2187 excel的煩惱 
*/
#include<bits/stdc++.h> 
using namespace std;string str;
int T;
char apt[] = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";// 檢測當前的坐標字符串屬于那種格式：
// 0 EXCEL 格式 
// 1 RXCY  格式
bool getFormat(string str)
{bool flag = 0;int strlen = str.length();for(int i=0; i<strlen; i++) {// 數字出現標記 if(isdigit(str[i]))flag = true;// 檢測是否為 RXCY 模式if(flag && str[i]=='C')return true;}return false;
} // 格式轉換 
void transform(string str)
{// 格式識別bool mode =  getFormat(str);// 格式轉換 int row = 0, col = 0, len = str.length();if(mode){ // mode 1：RXCY 轉 ECXCEL 格式 // 定位 R 與 C 所在位置 int R = str.find("R"), C = str.find("C");// 取出行號和列號 for(int i=R+1; i<C; i++) row = row*10+str[i]-'0';for(int i=C+1; i<len; i++)col = col*10+str[i]-'0';// 將十進制數轉換為以 A-Z 表達的二十六進制數 int tmp;string ans;while(col > 0){tmp = col%26;if(tmp == 0){tmp = 26;col -= 26;}ans += apt[tmp];col /= 26;} reverse(ans.begin(), ans.end());// 格式化輸出 cout<<ans<<row<<endl;}else{	// mode 0：ECXCEL 轉 RXCY 格式 // 將二十六進制數轉換為十進制數 for(int i=0; i<len; i++)if(!isdigit(str[i]))col = col*26+str[i]-'A'+1;elserow = row*10+str[i]-'0';// 格式化輸出 cout<<"R"<<row<<"C"<<col<<endl;}
}int main( )
{// 輸入數據cin>>T;for(int i=1; i<=T; i++){cin>>str;// 將當前的坐標表達式轉換為另一種格式 transform(str);}return 0;
}

MT2188 單條件和

難度：黃金 ?? 時間限制：1秒 ?? 占用內存：128M

題目描述

“單條件” 是數理邏輯中的5種常用連接詞之一，記作 “→”。它是二元運算。相當于 “如果…那么…. ”、“因為……所以……”、“只要…就.….” 等。也可稱為 “蘊涵”。“p→q” 讀作 “如果p，那么q”，其中 p 稱為前件，q 稱為后件。

其真值表如下：

如 “異或和” 為 $a_1?a_2?…?a_n$ ，我們現在要求 “單條件和”，即 $a_1→a_2→?→a_n$ ，對 $a_1,a_2,…,a_n$ 做位意義上的單條件運算求和。
請按 unsigned int 類型進行運算。

格式

輸入格式：第一行一個整數 $n$ ，表示有 $n$ 個需要求單條件和的整數；
?????第二行輸入 $n$ 個需要求單條件和的整數。
輸出格式：輸出一個 unsigned int 型的整數。

樣例 1

輸入：10
???1 2 3 4 5 6 7 8 9 10

輸出：4294967290

備注

對于100%的數據： $1 \leq n \leq 5 e 6$ 。

相關知識點：位運算

題解

觀察題目給出的真值表不難發現：“p→q” 其實等價于執行位運算 “~p|q”（非 p 或 q）。在理解這一點后，我們便能直接寫出以下代碼：

/*MT2188 單條件和 用 scanf 接受輸入才能得滿分 
*/
#include<bits/stdc++.h> 
using namespace std;int main( )
{// 輸入數據int n;unsigned ans, tmp;cin>>n>>ans;// 執行運算for(int i=1; i<n; i++) {scanf("%u",&tmp);ans = ~ans | tmp;}// 輸出 cout<<ans<<endl; return 0;
}

MT2189 三進制計算機1

難度：黃金 ?? 時間限制：1秒 ?? 占用內存：128M

題目描述

三進制計算機，是以三進法數字系統為基礎而發展的計算機。在光子計算機研究領域也有涉及。
三進制代碼的一個特點是對稱，即相反數的一致性，因此它和二進制代碼不同，不存在無符號數的概念。這樣，三進制計算機的架構也要簡單、穩定、經濟得多。其指令系統也更便于閱讀，而且非常高效。
在一般情況下，命題不一定為真或假，還可能為未知。在三進制邏輯學中，符號 1 代表真；符號 -1 代表假；符號 0 代表未知。這種邏輯表達方式更符合計算機在人工智能方面的發展趨勢，它為計算機的模糊運算和自主學習提供了可能。
在本題中，請你將輸入的對稱三進制數轉換為對應的十進制數。對稱三進制數不是用 0/1/2 表示，比較特殊，是用 1/0/-1 表示，故名對稱。本題中 -1 用符號 - 表示，而 1 和 0 直接表示即可。

格式

輸入格式：第一輸入一個整數 $n$ ，表示數據組數；
?????接下來 $n$ 行，每行輸入一個對稱三進制整數。
輸出格式：對于第 2~n+1 行輸入的每一個對稱三進制整數，分別輸出其十進制形式。

樣例 1

輸入：8
???-0
???-1
???-
???0
???1
???1-
???10
???1–

輸出：-3
???-2
???-1
???0
???1
???2
???3
???5

備注

樣例中 $\times 1，5=9-3-1$ 。
對于100%的數據： $1 \leq n \leq 1 e 6$ ，輸入的對稱三進制數對應的整數在 int 類型范圍內
。

相關知識點：平衡三進制

題解

這道題實際上考察的是進制轉換，即平衡三進制轉換為十進制數。

首先我們要知道，任意 $k$ 進制數（設為 $A_k=a_1 a_2?a_n$ ）轉換為十進制都遵循下式：

$n=\sum_{i=1}^na_i k^{n-i}$

其中， $a_i$ 表示該 $k$ 進制數在第 $i$ 位上的取數， $n$ 表示其長度。

例如，二進制數 1010 轉換為十進制數為：

$n=a_1 k^{4-1}+a_2 k^{4-2}+a_3 k^{4-3}+a_4 k^{4-4}=1×2^3+0×2^2+1×2^1+0×2^0=10$

十六進制數 AE86 轉換為十進制數為：

$n=a_1 k^{4-1}+a_2 k^{4-2}+a_3 k^{4-3}+a_4 k^{4-4}=10×16^3+14×16^2+8×16^1+6×16^0=44678$

同樣地，三進制數也滿足該式。但是本題比較特殊，因為平衡三進制數中的 2 會用 -1 來表示，但這并不影響通式給出的計算方法。例如，對于題目給出的平衡三進制數：1--，其轉換過程如下：

$n=a_1 k^{3-1}+a_2 k^{3-2}+a_3 k^{3-3}=1×3^2+(-1)×3^1+(-1)×3^0=9-3-1=5$

根據這樣的思路，可寫出求解本題的完整代碼：

下面給出基于以上思路寫出的完整代碼（已 AC）：

/*MT2189 三進制計算機1  輸出轉換結果時不能用 endl ，否則會超時 
*/
#include<bits/stdc++.h> 
using namespace std;const int N = 105;
int w[N], n, ans, len;
char s[N];int main( )
{// 取消cin與stdin的同步（加速文件讀取速度） ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// 輸入數據cin>>n; // 構建乘位 w[0] = 1;for(int i=1; i<=100; i++)w[i] = w[i-1]*3;// 進制轉換與輸出 while(n--){cin>>s;ans = 0;len = strlen(s);// 進制轉換 for(int i=len-1; i>=0; i--){if(s[i] == '1') ans += w[len-1-i];if(s[i] == '-') ans -= w[len-1-i];}// 輸出轉換結果cout<<ans<<"\n";}return 0;
}

此外，對本題而言還需要特別注意兩點：

必須取消 cin 與 stdin 的同步以加速文件讀取速度，否則會超時（原理請見：C++中輸入和輸出的一些問題）；
輸出換行時必須用 “\n” 替代 “endl”，否則會超時。

當然，你也可以用 C 的方式進行數據輸入輸出（即用scanf和printf替代cin和cout），這樣就不必擔心上面的這些問題。

MT2190 三進制計算機2

難度：鉆石 ?? 時間限制：1秒 ?? 占用內存：128M

題目描述

三進制計算機，是以三進法數字系統為基礎而發展的計算機。在光子計算機研究領域也有涉及。
三進制代碼的一個特點是對稱，即相反數的一致性，因此它和二進制代碼不同，不存在無符號數的概念。這樣，三進制計算機的架構也要簡單、穩定、經濟得多。其指令系統也更便于閱讀，而且非常高效。
在一般情況下，命題不一定為真或假，還可能為未知。在三進制邏輯學中，符號 1 代表真；符號 -1 代表假；符號 0 代表未知。這種邏輯表達方式更符合計算機在人工智能方面的發展趨勢，它為計算機的模糊運算和自主學習提供了可能。
在本題中，請你將輸入的對稱三進制數轉換為對應的十進制數。對稱三進制數不是用 0/1/2 表示，比較特殊，是用 1/0/-1 表示，故名對稱。本題中 -1 用符號 - 表示，而 1 和 0 直接表示即可。

格式

輸入格式：第一輸入一個整數 $n$ ，表示數據組數；
?????接下來 $n$ 行，每行輸入一個十進制整數。
輸出格式：對于第 2~n+1 行輸入的每一個十進制整數，分別輸出其對稱三進制形式。

樣例 1

輸入：8
???-3
???-2
???-1
???0
???1
???2
???3
???5

輸出：-3
???-0
???-1
???-
???0
???1
???1-
???10
???1–

備注

樣例中 $\times 1，5=9-3-1$ 。
對于100%的數據： $1 \leq n \leq 1 e 6$ ，輸入的對稱三進制數對應的整數在 int 類型范圍內
。

相關知識點：平衡三進制

題解

這道題與前一題的要求剛好相反，即要求將輸入的每個十進制數轉換為對稱三進制數并輸出。
首先我們要知道，任意十進制數 $n$ 轉換為 $k$ 進制都遵循一個過程：

當前位取數為：n%k；
為繼續向后取數（即得到更高位的數），更新數 $n=\frac{n}{k}$ 。
若 n = 0 ，則轉換結束。

例如，將十進制數 10 轉換為二進制數的過程如下：

第1位： $n\%2 = 10\%2 = 0$ ，更新 $n=\frac{n}{2}=\frac{10}{2}=5$ ；
第2位： $n\%2 = 5\%2 = 1$ ，更新 $n=\frac{n}{2}=\frac{5}{2}=2$ ；
第3位： $n\%2 = 2\%2 = 0$ ，更新 $n=\frac{n}{2}=\frac{2}{2}=1$ ；
第4位： $n\%2 = 1\%2 = 1$ ，更新 $n=\frac{n}{2}=\frac{1}{2}=0$ ，轉換結束。

于是得到十進制數 10 對應的二進制數為 1010。

同樣地，將十進制數轉換為三進制數也遵循該算法，例如，將十進制數 11 轉換為三進制數的過程如下：

第1位： $n\%3 = 11\%3 = 2$ ，更新 $n=\frac{n}{3}=\frac{11}{3}=3$ ；
第2位： $n\%3 = 3\%3 = 0$ ，更新 $n=\frac{n}{3}=\frac{3}{3}=1$ ；
第3位： $n\%3 = 1\%3 = 1$ ，更新 $n=\frac{n}{3}=\frac{1}{3}=0$ ，轉換結束。

于是得到十進制數 11 對應的三進制數為 102。

而本題要求轉換的 “平衡三進制” 中，所有的 “2” 都要求用 “-1” 來替代。這一替換實際上相當于將指定位上的值減少了 1（從這個數的整體來看，實際上減少了 $1×k^p$ ），為了保證這個數在整體上的值不變，就必須向前一位借位，即將這個位前的那個值加 1。例如，由十進制數 11 得到的三進制數為 102，我們從該數的低位向高位掃描：首先，末尾存在一個 “2”，于是將這個數替換為 “-”，并將較高位的 “0” 替換為 “1”（即得到 11-）；接繼續向后掃描，發現整個序列中的數均合法，于是得到由十進制數 11 轉換的平衡三進制數為 11-。我們可以進行驗證：

$n=a_1 k^{3-1}+a_2 k^{3-2}+a_3 k^{3-3}=1×3^2+1×3^1+(-1)×3^0=9+3-1=11$

考慮一種情況，三進制數 122。當將末位的 “2” 借位后，中間位的 “2” 將變成數字 “3”，即此時為 13-；對中間位而言，“3” 已經達到了這個進制下的最大值，因此要進位，于是此時該數將變為 20-；繼續向高位掃描，發現最高位為 “2”，因此需要將其轉換為 “-”，并向較高位借位，故最終得到 1-0-。我們可以進行驗算：

$122：n=1×3^2+2×3^1+2×3^0=9+6+2=17$
$1-0-：n=1×3^3+(-1)×3^2+0×3^1+(-1)×3^0=17$

可以看出，他們最終轉換為十進制均為 17。

最后還需要注意一點：平衡三進制的負數與正數之間的轉換關系。實際上，題目也給出了他們之間關系的一些提示：“三進制代碼的一個特點是對稱，即相反數的一致性”。對于平衡三進制的數而言，它的相反數與其本身的關系如下：所有非 0 數據互相相反。例如，平衡三進制數 1-01，它對應的負數則為 -10-：

$1-01：n=1×3^3+(-1)×3^2+0×3^1+1×3^0=27-9+0+1=19$
$10-：n=(-1)×3^3+1×3^2+0×3^1+(-1)×3^0=-27+9+0-1=-19$

根據上面的分析，可以將求解本題的思路整理如下：

將輸入的十進制數轉換為對應的三進制數（為便于處理，這一階段將統一使用該數的正數）；
將三進制數轉換為平衡三進制數，轉換規則如下（假設當前的三進制數字符串為num）：
- 若 num[i] = 2，則令 num[i] = -, num[i+1]++（數字串的索引大小與數的低位到高位對應）；
- 若 num[i] = 3，則令 num[i] = 0, num[i+1]++。
根據輸入十進制數的正負性，對得到的平衡三進制數進行相應處理。

下面給出基于以上思路得到的完整代碼（已 AC）：

/*MT2190 三進制計算機2  思路：先將數從十進制轉換至正常的三進制，然后再轉換為平衡三進制 
*/
#include<bits/stdc++.h> 
using namespace std;const int N = 55;
int num[N], n, x, flag, cnt;int main( )
{// 取消cin與stdin的同步（加速文件讀取速度） ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// 輸入數據cin>>n; while(n--){cin>>x;memset(num, 0, sizeof(num));flag = 1, cnt = 0;// 程序將統一處理正數，因此定義標記來記錄原始輸入數據的正負性 if(x<0){flag = -1;x = -x;}if(x == 0){cout<<x<<"\n";continue;} // 將十進制數轉換為三進制數 while(x){num[cnt++] = x%3;x /= 3;}// 將三進制數轉換為平衡三進制數 for(int i=0; i<cnt; i++){if(num[i] == 2){// 借位 num[i] = -1;num[i+1]++;}else if(num[i] == 3){// 進位 num[i] = 0;num[i+1]++; }}// 判斷原始三進制數轉換為平衡三進制數后是否出現了位增情況 if(num[cnt]) cnt++;// 如果原始輸入的十進制數為負數，則需要對已經算出的平衡三進制數進行反號 if(flag == -1) for(int i=cnt-1; i>=0; i--)num[i] = -num[i];// 輸出轉換后的平衡三進制數，需要進行格式控制：所有的-1都輸出- for(int i=cnt-1; i>=0; i--)if(num[i] == -1) cout<<"-";else cout<<num[i];cout<<"\n";}return 0;
}