PAT A1010 二分进制结合重点题

这道题而可以说是比较难的一道题，如果采用常规遍历，会出现时长或者溢出的问题；

示例中给出的思路很值得借鉴；

个人通过该示例有以下几个不同理解：

1.有时候两个不同进制的数对比，我们可以进行进制，转化十进制来进行比较；

2.对于有些枚举或者寻找问题，为了不进行枚举遍历，我们应该第一时间想到二分查找；

对于第一点，这个在题目中有所体现，我们都是将其转化为相应的十进制下，然后进行比较，看是否相同；

在这个途中，有个难点：对于未知进制数，我们应该如何推断，一定要注意溢出问题；

在本题目中，并没有对进制有限定，如果按照常规进制计算，就会发生int或这longlong溢出，这一点要注意；

而对于未知进制数，我们就可以让二分派上用场；

本题目的根本就是进制枚举，所以我们可以规定进制的上界和下界，从而通过二分来寻找一个进制，使得通过改进之转换的数和给定的数相同，来达到最终的结果；

那么问题又来了，上界和下界如何确定？

下界好说，下界就可以取整个数字序列中最大的数，加一就是下界。例如对于一个位15，最起码应该是16进制；

而对于上界，比较难以理解，上界取另一个数字在十进制下的值，加一就是上界；

举个例子说明一下，假如另一个数字十进制下是156，如果当前给出的值是1，那么多少进制可以让其和156相等，答案就是156进制，由于在二分查找下，我们输入的序列大原本序列1位，所以还需要+1；

详细代码如下所示：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL inf=(1LL<<63)-1;
char n1[20],n2[20],temp[20];
int m[256];

void init(){
    for(char c='0';c<='9';c++){
        m[c]=c-'0';
    }
    for(char c='a';c<='z';c++){
        m[c]=c-'a'+10;
    }
}

LL convert2num10(char a[],LL radix,LL t){
    LL ans=0;
    int len=strlen(a);
    for(int i=0;i<len;i++){
        ans=ans*radix+m[a[i]];
        if(ans<0||ans>t)
            //ans<0为大到溢出的情况
            return -1;
    }
    return ans;
}
int findLargestDigit(char N2[]){
    int ans=-1;
    int len=strlen(N2);
    for(int i=0;i<len;i++){
        if(m[N2[i]]>ans){
            ans=m[N2[i]];
        }
    }
    return ans+1;
}

int cmp(char n2[],LL radix,LL t){
    int len=strlen(n2);
    LL num=convert2num10(n2,radix,t);
    if(num<0)
        return 1;
    if(t==num)
        return 0;
    else if(t>num)
        return -1;
    else
        return 1;
}

LL binarySearch(char n2[],LL left,LL right,LL t){
    LL mid;
    while(left<=right){
        mid=(left+right)/2;
        int flag=cmp(n2,mid,t);
        if(flag==0)
            return mid;
        else if(flag==-1)
            left=mid+1;
        else
            right=mid-1;
    }
    return -1;
}

int main(){
    init();
    int tag,radix;
    scanf("%s%s%d%d",n1,n2,&tag,&radix);
    if(tag==2){
        strcpy(temp,n1);
        strcpy(n1,n2);
        strcpy(n2,temp);
    }
    LL t=convert2num10(n1,radix,inf);
    //将N1从radix进制转化为10进制；
    LL low=findLargestDigit(n2);
    //low是序列中最大的数，也就是可以比较的最小进制，例如110，则合法的进制最小都未进制
    LL high=max(low,t)+1;
    //high是上界
    LL ans=binarySearch(n2,low,high,t);
    if(ans==-1)
        printf("Impossible\n");
    else
        printf("%lld\n",ans);
    system("pause");
    return 0;
}