立志用最少的代碼做最高效的表達

---

PAT甲級最優題解——>傳送門

---

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N?2, your task is to find the radix of one number while that of the other is given.

Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:
6 110 1 10
Sample Output 1:
2

Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible

---

解題過程

最初按照常規字符串轉進制的做法，敲出代碼， 考慮的進制的下限與上限，提交后發現測試點7超時。

于是嘗試著將進制循環范圍限制到1千萬，發現耗時340ms+，依然無法得出結果。

我推斷測試點7或許是一個上億進制的數。如果是這樣，按照常規遍歷方法根本沒法求。于是徹底放棄。轉向二分。

---

進制范圍的確定

進制的最小取值為：各個位數最大值+1 如123的最小進制一定大于3， abc的最小進制一定大于12

現在來討論進制的上限（max_radix）
　　那么現在在題目中，給出了兩個數，一個數記為a是已知進制的，另一個記為b未知，假設a=675,為10進制，b=1，未知進制
　　很顯然，b的最低進制min_radix是2
　　那么b的最高進制max_radix 是多少呢
　　我們的目的是讓a=b，b不可過小也不可過大
　　
　　假設 max_radix=1000
　　很顯然b = 1(1000) = 1000 > a = 675
　　所以，發現了嗎
　　想讓a=b，b的最大進制就是a的值,即675
　　因為我舉的例子比較特殊，如果b不為1，那么就很難直接得到b的精確的最高進制max_radix
　　但是 ，可以肯定的是，當b為1 的時候，max_radix是最大的（因為此時b最小）
　　因此，我們雖然不知道b=10,20,80,13671…時，對應的max_radix是多少，但是，他們一定比b=1對應的max_radix小
　　那么我們就可以用最大的max_radix作為進制的上限，在min_radix 到max_radix中二分查找
　　同時需要注意，max_radix>=min_radix
　　故有 max_radix = max(a,min_radix);

---

坑點：
計算過程中會出現數據溢出。
舉個極端例子：
一億進制的zzzzzzzzzz轉化為十進制。 即使用long long也無法保存。
那么應該怎么判斷呢？ 可以判斷計算結束后的值是否小于0，因為溢出后的值一定小于0

---

#include<bits/stdc++.h> using namespace std; using gg = long long; unordered_map<char, int>charToint; //0-9 a-z映射 gg trans(string s, gg radix) {gg result = 0;for(auto i : s)result = result*radix+charToint[i];return result; }gg findRadix(string n1, string n2, gg radix) { //查找符合要求的進制 gg right = trans(n1, radix), left = -1, tag = right; //left指示要查找的進制數的下限 for(auto i : n2) left = max(left, (gg)charToint[i]+1);while(left < right) {gg mid = left + (right - left)/2, k = trans(n2, mid);if(k < 0 || k >= tag) //k<0表示數據超過long long 存儲范圍right = mid;else if(k < tag)left = mid + 1; //如果min是對的，那么right等于min，下一次循環時，left=min，則right=min，結束循環 }if(trans(n2, left) != tag) //如果查找到的進制下兩數不等，返回-1 left = -1; return left; } int main() {ios::sync_with_stdio(false); string s1, s2;gg tag, radix;cin >> s1 >> s2 >> tag >> radix;for(int i = 0; i < 36; i++) //將0-9 a-z壓入charToint的map中 charToint.insert({i<10?i+'0':i-10+'a', i}); //insert賦值 radix=tag==1 ? findRadix(s1, s2, radix) : findRadix(s2, s1, radix);if(radix == -1) cout << "Impossible\n";else cout << radix << '\n'; return 0; }

耗時：

---

???????? ——惟正己可以化人，唯盡己可以服人。

總結

以上是生活随笔為你收集整理的【测试点分析】1010 Radix (25 分)_37行代码AC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。