算法分析
二分
- 1、统一化,
N1 N2 tag radix
,4
个变量中,默认N1
是已知的radix
进制数,N2
是未知的进制数,通过交换实现 -
2、在给定的进制范围内,找出符合要求的最小进制数,因此可以用二分找到该进制,需要确保上下界的范围
上界l
:未知进制N2
中最大的数字+1
,最小是2
下界r
:N1
在radix
中转化成10
进制的值 -
3、通过二分判断,若在
mid
进制下N2
比target
大,则往左边区域取,比target
小,则往右边区域取,直到只剩下一个数l
(结果)为止,若将N2
变成l
进制,且ten(N2,l) != target
,则表示最接近的转换进制l
也不符合条件,返回Impossible
,否则返回l
时间复杂度 O(logn)
n = 10^11,36进制模式
参考文献
pat
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
int get(char c)
{
if(c >= '0' && c <= '9') return c - '0';
return c - 'a' + 10;
}
//转化为十进制
LL ten (string a,LL radix)
{
LL ans = 0;
double t = 1;
for(int i = a.size() - 1;i >= 0;i --)
{
if((double)ans + get(a[i]) * t > 1e18) return 1e18;
ans = ans + get(a[i]) * t;
t *= radix;
}
return ans;
}
int main()
{
string a,b;
int op,radix;
cin >> a >> b >> op >> radix;
//默认a的进制是radix
if(op == 2) swap(a,b);
LL l = 2;
for(auto c : b) l = max(l,(LL)get(c) + 1);
LL target = ten(a,radix);
LL r = target;
while(l < r)
{
LL mid = l + r >> 1;
if(ten(b,mid) >= target) r = mid;
else l = mid + 1;
}
if(ten(b,l) != target) cout << "Impossible" ;
else cout << l ;
cout << endl;
return 0;
}
请问ten函数中的t变量为什么是double类型?
以及为什么越界之后就可以取为1e18呢?
同问
1、两个数相乘得到的数用
long long
可能存不下2、越界说明这个数很大,返回一个很大的数即可,不需要再计算下去,这个数一定会满足
>= target
已回复
好滴,谢谢!
谢谢大佬
小呆呆不是喜欢用java写吗?怎么换成C++了?
java在pat官网会超时哈哈