PAT A1010 Radix [二分]

题目描述

链接
n1 n2 tag radix 当tag=1时,radix进制的n1的十进制值=ans进制的n2的十进制值,求解这个ans进制是多少。

分析

  • 本质就是求解方程!用二分查找求解方程的根trans(a,radix)==sum
  • 先要用longlong类型应该不难看出来。
  • 试答案的时候不能顺序搜索,要用二分搜索。
  • 二分的边界要想对,最小的应该是数中最小的那个数+1,比如:123a,那么这个数最小的进制数为11(因为数中有a)。最大的边界应该为基准数的十进制值(例如:基准数的十进制为为1000000,另一个数为10,那么它可以是1000000进制的,也满足条件)。
  • 如果算的进制数太大时,可能会爆longlong,那么在计算中还要注意对溢出的判断(tmp<0)
#include<bits/stdc++.h>
using namespace std;

string a,b;
int tag,radix;

long long trans(string a, long long radix){  //单增函数
    int len = a.size();
    long long sum = 0;
    for(int i=0;i<len;i++){
        if(a[i]>='0' && a[i] <='9')
            sum = sum * radix + a[i]-'0';
        else sum = sum * radix + a[i]-'a' + 10;
    }
    return sum;
}

long long findmin(string a){
    int len = a.size(), maxnum = 0;
    for(int i=0;i<len;i++){
        if(a[maxnum] < a[i]) maxnum = i;
    }
    if(a[maxnum]>='0' && a[maxnum] <= '9') return a[maxnum]-'0' + 1;
    return a[maxnum]-'a' + 10 + 1;
}

long long binarysort(string a, long long x){
    long long l = findmin(a);
    long long r = max(l, x);
    while(l<=r){
        long long mid = (l+r)>>1;
        long long tmp = trans(a,mid);
        if(tmp == x) return mid;
        else if(tmp > x || tmp < 0) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}



void solve(){
    long long sum, res;
    if(tag == 1){
        sum = trans(a, radix);
        res = binarysort(b, sum);
    }else{
        sum = trans(b, radix);
        res = binarysort(a, sum);
    }
    if(res == -1) cout<<"Impossible"<<endl;
    else cout<<res<<endl;

}

int main(){
    cin>>a>>b>>tag>>radix;
    solve();
}
上一篇:WF2017 Secret Chamber at Mount Rushmore (邻接矩阵)


下一篇:小白学Python——用 百度翻译API 实现 翻译功能