题目链接
解题思路
1、用一个数组rads表示'0'~'9','a'~'z'对应从0~35每个值。
2、根据tag和radix将s1转为十进制的数n1。
3、然后选择任意一个进制将s2转为n2，并和n1比较。因为进制基数越大，s2对应的数就越大，所以可以使用二分法来找出令n2=n1的基数radix。二分法需要先确定上界和下界。下界好理解，就是找出s2中最大的字符即可，上界就是n1+1，因为是为了找一个进制使n2==n1，进制基数恰好等于n1时，比如n2为’10’。
注意
1、一开始有一个误区，就是误以为n2也是在2~36进制，因为前面说数字都是0~z表示的。但是如果这样的话，就很难使n2等于n1了，因为n1在36进制时会是一个很大的数。题目给的任务就是要找一个进制使n2等于n1，这个进制基数有可能超过int范围，所以使用long long。
2、还要注意在二分法找n2的进制基数时，将s2转为十进制数，由于基数特别大，很有可能溢出long long，所以要考虑溢出的情况，溢出了就一定大于n1，所以要将进制基数减小，也就是要在mid左边继续找。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=130;
ll n1, n2;
string s1, s2;
int rads[maxn];
ll changeTodecimal(string s, ll r) {
int len = s.length();
ll ans=0;
for (int i = 0; i < len; i++) {
ans=ans*r+rads[s[i]];
}
return ans;
}
ll binaSearch(string s){
char ch=*max_element(s.begin(),s.end());
ll l=rads[ch]+1,r=max(l,n1)+1,mid;
while(l<=r){
mid=(l+r)/2;
n2=changeTodecimal(s,mid);
if(n2==n1) return mid;
else if(n2<0||n2>n1){
r=mid-1;
} else{
l=mid+1;
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
for(int i=0;i<=9;i++) rads[i+'0']=i;
for(int i='a';i<='z';i++) rads[i]=i-'a'+10;
int tag, radix;
ll res;
cin >> s1 >> s2 >> tag >> radix;
if (tag == 1) n1 = changeTodecimal(s1, radix);
else if (tag == 2) {
n1 = changeTodecimal(s2, radix);
s2=s1;
}
res=binaSearch(s2);
if(res==-1) cout<<"Impossible";
else cout<<res;
return 0;
}
|