关于算法-数据结构:PAT甲级1010-Radix

此题难度较大，自己写了3次，在不借助外在帮忙的状况下最好问题才21分，对于第一次尝试的同学，能够临时放弃。

题目粗心:

输出四个整数N1、N2、tag、radix。其中tag–1示意N1为radix进制数，tag–2示意N2为radix进制数。范畴:N1和N2均不超过10个数位，且每个数位均为0-9或a~z，其中0~9示意数字0~9、a~z示意数字10-35.
求N1和N2中未知进制的那个数是否存在，并满足某个进制时和另一个数在十进制下相等的条件。若存在，则输入满足条件的最小进制:否则，输入Impossible.

算法思路：

此题的难点次要有2个，一个是N2进制数的范畴的确定，一个是在该范畴中搜寻的办法。咱们在这里假如将曾经晓得的进制数设定为N1，而后如果tag等于2，就让N1和N2进行替换

对于N2进制的范畴确定如下：

第一：对于其下界很显著为其数字中呈现的最大数字加1，比方123456789，这个数字起码是10进制的，因为呈现了9

第二：对于其上界的确定比拟没有那么让人容易想到，首先咱们晓得对于1位数字，其进制数和其转化为10进制数的大小没有任何关系所以其上界就是下界，其次，对于位数大于1的数字，想要求出最大的进制数，并且要转化为10进制数后和N1的十进制数相等，就必须得保障该数字最小，天然就能够发现位数大于2位的最小数字就是10，而想要该数字转化为10进制数后和N1的十进制数相等，那么N2的进制数必须为N1的10进制数，综上所述，N2进制数的上界为下界和N1的10进制数的最大值。

对于在下界和上界之间搜寻N2进制的办法:

咱们晓得当一个数字的进制数被固定的时候,其十进制数会随着该数字的增大而增大,当其数字固定的时候,其十进制数会随着进制数的增大而增大.那么咱们为了在N2的下界和上界中搜寻出一个数字作为N2的进制数，使其转化为10进制数后和N1的十进制数相等,能够应用二分搜寻的办法查找该进制数.具体做法为咱们取得其区间中值mid,而后将N2转化为10进制数，如果该数字和N1的十进制数相等，输入mid并且返回，如果小于N1的十进制数，阐明以后的进制数较小，向右子区间搜寻，否则像左子区间搜寻。退出循环后阐明没有搜寻到符合条件的进制数，输入Impossible

留神点：

1、将N2转化为10进制数的时候有可能会溢出，必须得判断在进行区间的划分，然而N1不会溢出能够不必判断，测试点6,8,12,13,15,16考查N2溢出问题
2、有人可能会间接将区间设置为[0,2^63-1],然而理论测试后果是测试点0，1，11，18会谬误得21分(也算是个不错的分数了)，如果下界设置为1更加会出错只能失去14分，自己也不晓得为什么。
3、题目所说的多个进制数中输入最小的进制数，个人感觉这个条件是没有用的，因为满足不存在数字肯定，进制数不同还能失去十进制数雷同的。
4、暴力搜寻会超时，此题基本上找到上下界，就能拿到20分左右。

提交后果：

AC代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

// radix进制数num转化为10进制数
long long toDecimal(string num, long long radix){
    if(num=="0"){
        return 0;
    }
    long long result = 0;
    long long expo = 1;
    for (int i = num.size()-1; i>=0 ; --i) {
        if(num[i]>='0'&&num[i]<='9'){
            result += (num[i]-'0')*expo;
        } else if(num[i]>='a'&&num[i]<='z'){
            result += (num[i]-'a'+10)*expo;
        }
        expo *= radix;
    }
    return result;
}


// 获取N2的最小进制数，为其呈现的最大数字加1
long long getInfRadixOfN2(string N2){
    int radix = -1;
    for (int i = 0; i < N2.size(); ++i) {
        int temp;
        if(N2[i]>='0'&&N2[i]<='9'){
            temp = N2[i]-'0';
        } else if(N2[i]>='a'&&N2[i]<='z'){
            temp = N2[i]-'a'+10;
        }
        if(temp>radix){
            radix = temp;
        }
    }
    return radix+1;
}

int main(){
    string N1,N2;
    cin>>N1>>N2;
    int tag,radix;
    // 这里保障radix为N1的，查找N2的进制数使其最靠近N1
    scanf("%d %d",&tag,&radix);
    if(tag==2){
        // radix为N2的就替换N1和N2
        swap(N1,N2);
    }
    long long decimalOfN1 = toDecimal(N1,radix);
    long long decimalOfN2;
    long long left=getInfRadixOfN2(N2);// 测试点0,6,19考查,left写成7测试点0和19会正确
    long long right=max(left,decimalOfN1);
    long long mid;
    while (left<=right){
        mid = left + (right-left)/2;
        decimalOfN2 = toDecimal(N2,mid);
        if(decimalOfN1==decimalOfN2){
            printf("%lld",mid);
            return 0;
        } else if(decimalOfN2<decimalOfN1&&decimalOfN2>0){// 测试点6,8,12,13,15,16考查N2溢出问题
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    printf("Impossible");
    return 0;
}