題目分析：
首先這題有很多的坑點，我在寫完之后依舊還有第10個測驗點沒有通過，而且代碼寫的不優美比較冗長勿噴，本篇博客用于記錄寫這道題的一些注意點
1.關于兩個不同進制的數比大小一般采用將兩個數都轉化為10進制之后比較大小（下面統稱已知進制數為N1，未知進制數為N2）
2.雖然兩個數都只有10位，且每一位上的數字是從‘0’~‘z’，分別代表0~35，但是這并不意味值這題的進制范圍就是2~36，radix完全有可能很大很大到long long，寫‘0’~‘z’只是為了讓結果計算出來相對小一些，并且迷惑一下
3.由于進制radix有可能很大，故要采用二分查找的方式進行進制的選擇判斷，否則會超時
4.同時在對每一個二分查詢出來的radix進行嘗試計算出相應未知進制數N2的10進制表示的程序中有可能溢位long long的范圍（會變成負數），需要注意
5.對于已知進制數N1在求出它的10進制表示的時候也有可能溢位long long（這一點比較奇怪，因為如果連已知進制的數N1的10進制表示都是不可記錄下來的那如何再去求出N2的10進制二者進行比較呢）
6.對于二分查找N2的進制的時候，N2的下界為N2中數字的最大值+1（例如：10020的最大數字為2，故最低的進制為3進制），而N2的上界則為N1的10進制表示+1（這是一個卡點，這里給出推理的程序）
如果N2的位數超過1位（2位以及以上時），這時候只要1次方位上的數大于等于1，則如果N2的進制為N1的10進制表示+1，則N2永遠都大于N1，再大就沒有必要了
1 #include<iostream> 2 #include<string> 3 using namespace std; 4 5 string n1, n2; 6 int tag; 7 long long radix; 8 int len1, len2; 9 int a[15]; 10 int b[15]; 11 long long Min, Max; 12 int judge; 13 14 void init_ab(){ 15 len1 = n1.size(); 16 len2 = n2.size(); 17 int cnt = 0; 18 for(int i = len1-1; i >= 0; i--){ 19 if(n1[i] >= '0' && n1[i] <= '9'){ 20 a[cnt++] = n1[i] - '0'; 21 }else{ 22 a[cnt++] = n1[i] - 'a' + 10; 23 } 24 } 25 //因為未知進制數一定存在b中，所以可以順便求一下未知進制數的進制下界 26 Min = 0; 27 cnt = 0; 28 for(int i = len2-1; i >= 0; i--){ 29 if(n2[i] >= '0' && n2[i] <= '9'){ 30 b[cnt] = n2[i] - '0'; 31 if(b[cnt] > Min) Min = b[cnt]; 32 cnt++; 33 }else{ 34 b[cnt] = n2[i] - 'a' + 10; 35 if(b[cnt] > Min) Min = b[cnt]; 36 cnt++; 37 } 38 } 39 //Min為未知進制數的所有位中最大數+1 40 Min++; 41 } 42 43 void binary_search(){ 44 //首先需要注意的是 Min和Max的大小要保證Min小于等于Max 45 if(Min > Max){ 46 long long t = Min; 47 Min = Max; 48 Max = t; 49 } 50 long long left = Min; 51 long long right = Max; 52 int flag; 53 while(left <= right){ 54 long long mid = (left + right) / 2; 55 //計算以mid為進制的未知進制數的10進制表示是否和已知進制的10進制相等 56 long long ans = 0; 57 long long base; 58 for(int i = 0; i < len2; i++){ 59 if(i == 0){ 60 base = 1; 61 ans += base * b[i]; 62 }else{ 63 base *= mid; 64 if(base < 0){ 65 flag = 1; 66 break; 67 } 68 ans += base * b[i]; 69 } 70 //判斷溢位或者已經大于已知進制數的10進制表示 71 if(ans > Max - 1 || ans < 0){ 72 flag = 1; 73 break; 74 } 75 } 76 if(ans < Max - 1) flag = -1; 77 if(ans == Max - 1) flag = 0; 78 if(flag == 0){ 79 cout<<mid<<endl; 80 break; 81 }else if(flag == -1){ 82 left = mid + 1; 83 }else right = mid - 1; 84 } 85 if(left > right) cout<<"Impossible"<<endl; 86 } 87 88 void cal_Max(){ 89 long long base; 90 //這里設定Max為已知進制數的十進制表示 + 1,且默認不會超過longlong范圍，否則題目就太復雜了 91 Max = 0; 92 for(int i = 0; i < len1; i++){ 93 if(i == 0){ 94 base = 1; 95 Max += base * a[i]; 96 }else{ 97 base *= radix; 98 Max += base * a[i]; 99 } 100 if(Max < 0){ //已知進制的數已經溢位 除非n1 n2相等 否則直接impossible？ 101 judge = 1; 102 if(n1 == n2) cout<<radix<<endl; 103 else cout<<"Impossible"<<endl; 104 break; 105 } 106 } 107 Max++; 108 } 109 110 int main(){ 111 while(cin>>n1>>n2>>tag>>radix){ 112 judge = 0; 113 if(tag == 2){ //始終將n1用于存放已知進制的數 114 string t = n1; 115 n1 = n2; 116 n2 = t; 117 } 118 //將n1 和 n2兩個數的每一位存盤到a b陣列之中 119 init_ab(); 120 //求出未知進制數的進制上界 121 cal_Max(); 122 if(judge == 0){ 123 //二分查找在上界和下界之間 計算時可能由于進制太大而溢位需要處理 124 binary_search(); 125 } 126 } 127 return 0; 128 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139970.html
標籤：其他
上一篇：選擇排序
下一篇：牛客練習賽53 A-E