PAT A1010 二分进制结合重点题

电玩女神 2022-03-08 16:46 173阅读 0赞

![clipboard.png][]  
这道题而可以说是比较难的一道题，如果采用常规遍历，会出现时长或者溢出的问题；  
示例中给出的思路很值得借鉴；  
个人通过该示例有以下几个不同理解：  
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;
    }

[clipboard.png]: /images/20220308/50f0febe642d4a5d9d00d79b21bc300a.png