美文网首页PAT
B1010 Radix(二分)

B1010 Radix(二分)

作者: Tsukinousag | 来源:发表于2020-01-14 23:09 被阅读0次

    B1010 Radix (25分)

    • Each case occupies a line which contains 4 positive integers:
      不用考虑为0的情况

    • Here N1 and N2 each has no more than 10 digits.
      十位int会超,所以使用long long,但是long long在进行进制转换时还是会超,题中没有给出转换进制大小,所以要进行越界判断(第一处)

    • A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35.
      基数的范围为2~352~∞?,和35没半毛钱关系

    最小基数:A digit is less than its radix
    所以是最大位数+1

    最大基数:N2是一位数或两位数,一位数时,要满足上述最小基数的情况,两位数要满足不能超过N1的十进制数。

    • For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true.
      搜索采用二分法,要在上界进行越界判断(第二处)
    • If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
      这题来说二分查找结果唯一的吧(・∀・(・∀・(・∀・*)
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <string.h>
    #include <cmath>
    #include <math.h>
    #include <vector>
    #include <queue>
    #include <map>
    #include <set>
    #include <stack>
    using namespace std;
    typedef long long ll;
    const int MAX=10001;
    const int INF=0x3f3f3f3f;
    ll mp[MAX];
    void init()
    {
        for(char c='0';c<='9';c++)
        mp[c]=c-'0';
        for(char c='a';c<='z';c++)
        mp[c]=c-'a'+10;
    }
    ll getnum(string s,int radix)
    {
        ll ans=0;
        for(int i=0;i<s.length();i++)
        {
            ans=ans*radix+mp[s[i]];
            if(ans<0)
                return -1;
        }
        return ans;
    }
    ll getlow(string s)
    {
        ll maxnum=0;
        for(int i=0;i<s.length();i++)
        {
            if(maxnum<mp[s[i]])
                maxnum=mp[s[i]];
        }
        return maxnum+1;
    }
    ll binary(ll low,ll high,string s,ll number)//ll number 开始为int 测试点10
    {
        while(low<=high)
        {
            ll mid=(low+high)/2;
            ll result=getnum(s,mid);
            if(result==number)
                return mid;
            else if(result>number||result==-1)
                 high=mid-1;
            else if(result<number)
                 low=mid+1;
        }
        return -1;
    }
    int main()
    {
        string n1,n2;
        int tag,radix;
        cin>>n1>>n2;
        scanf("%d%d",&tag,&radix);
        init();
        if(tag==2)
        swap(n1,n2);
        ll num1=getnum(n1,radix);
        ll low=getlow(n2);//最小基数
        ll high=max(num1,low);//最大基数//测试点0
        ll ans=binary(low,high,n2,num1);
        if(ans!=-1)
            printf("%lld\n",ans);
        else
            printf("Impossible\n");
        return 0;
    }
    
    

    相关文章

      网友评论

        本文标题:B1010 Radix(二分)

        本文链接:https://www.haomeiwen.com/subject/yajzactx.html