A1010 Radix(进制转换+二分)

题目描述

给定字符串N1,N2和整数tag,radix,tag=1，代表N1为radix进制数，tag=2代表N2为radix进制数，求N1和N2中那个未知进制数是否存在，若存在求出满足条件的最小进制。

本题代码参考算法笔记，具体函数功能在注释中已表明，要注意的是：
1.暴力枚举会超时
2.书中默认题目中的数转换为十进制时不会超过long long
3.注意代码中进制上界和下界的求取

本题步骤较多，比较容易做错

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
char N1[20],N2[20],temp[20];
int Map[256];//映射表0~9,a~z
LL inf=(1LL<<63)-1;//这里为算法笔记中默认那个数转换为10进制后不超过long long，所以设置了一个上限值防止溢出
int tag,radix;
void init()//将0~9,a~z映射到0~35
{
for(char i='0';i<='9';i++)
Map[i]=i-'0';
for(char i='a';i<='z';i++)
Map[i]=i-'a'+10;
}
LL convertNum10(char a[],LL radix,LL t)//将a转换为10进制，t为上界
{
int len=strlen(a);
LL ans=0;
for(int i=0;i<len;i++)
{
ans=ans*radix+Map[a[i]];
if(ans<0||ans>t) return -1;
}
return ans;
}
int cmp(char N2[],LL radix,LL t)//N2的十进制与t比较
{
LL num=convertNum10(N2,radix,t);
if(num<0) return 1;//溢出，N2大于t
if(num>t) return 1;
else if(num==t) return 0;
else return -1;
}
LL binarySearch(char N2[],LL left,LL right,LL t)//二分求解N2的进制
{
LL mid;
while(left<=right)
{
mid=(left+right)/2;
LL flag=cmp(N2,mid,t);
if(flag==-1) left=mid+1;//进制越大，将其转换为十进制的结果更大
else if(flag==1) right=mid-1;
else return mid;
}
return -1;
}
int findLastDigit(char N2[])//求最大的数位
{
int len=strlen(N2);
int ans=-1;
for(int i=0;i<len;i++)
{
ans=max(ans,Map[N2[i]]);
}
return ans+1;//最大数位为ans，故ans+1为数位底线
}
int main()
{
init();
scanf("%s%s%d%d",N1,N2,&tag,&radix);
if(tag==2)//N1放置确定进制的数
{
strcpy(temp,N2);
strcpy(N2,N1);
strcpy(N1,temp);
}
LL t=convertNum10(N1,radix,inf);
LL low=findLastDigit(N2);
LL high=max(low,t)+1;//eg.t=30，那么N2最多30进制，此时在N2为1的时候十进制为30，若更大，则一定大于30
LL ans=binarySearch(N2,low,high,t);
if(ans==-1) printf("Impossiblen");
else printf("%lldn",ans);
return 0;
}

最后

以上就是想人陪酸奶为你收集整理的A1010 Radix(进制转换+二分)的全部内容，希望文章能够帮你解决A1010 Radix(进制转换+二分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。