【1010】Radix (25分)

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

2.思路

（1）将已确定进制的数放在N1，将未确定进制的数字放在N2，以便后面进行统一计算。
（2）题目说给的数N1和N2可能有10个数位，最多为三十六进制，即最大的数为36^10（超过int最大范围），于是将N1转换为十进制，使用long long类型存储。
（3）使用二分法：
    对于一个确定的数字串，其进制越大，则该数字串转换为十进制的结果越大，所以可以二分N2的进制，将N2从该进制转换为十进制，令其与N1的十进制比较：如果大于N1的十进制，说明N2的当前进制太大——应往左子区间继续二分，小于同理，当二分结束时即可判断解是否存在。

3.代码

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      二分查找，进制转换，暴力会超时，确定好上下界
     
    
   

    

     

    
    

     

      LL inf=(1LL << 63)-1; 注意此处是把LL型的1左移63位
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef long long LL;
     
    
   

    

     

    
    

     

      LL Map[256];  //0~9 a~z 与0~35的对应
     
    
   

    

     

    
    

     

      LL inf=(1LL << 63)-1; //long的最大值2^63-1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void init(){
     
    
   

    

     

    
    

     
	for(char c='0';c<='9';c++){
     
    
   

    

     

    
    

     

      		Map[c]=c-'0';  //将0~9映射到Map的0~9
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(char c='a';c<='z';c++){
     
    
   

    

     

    
    

     

      		Map[c]=c-'a'+10; //将a~z映射到Map的10~35
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      LL convertNum10(char a[],LL radix,LL t){ //将a转化为十进制，t为上界
     
    
   

    

     

    
    

     

      	LL ans=0;
     
    
   

    

     

    
    

     
	int len=strlen(a);
     
    
   

    

     

    
    

     
	for(int i=0;i<len;i++){
     
    
   

    

     

    
    

     

      		ans=ans*radix+Map[a[i]]; //进制转换
     
    
   

    

     

    
    

     
		if(ans<0 || ans>t) return -1; //溢出或超过N1的十进制
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return ans;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int cmp(char N2[],LL radix, LL t){  //N2的十进制与t比较
     
    
   

    

     

    
    

     
	int len=strlen(N2); 
     
    
   

    

     

    
    

     

      	LL num=convertNum10(N2,radix,t); //将N2转换成十进制
     
    
   

    

     

    
    

     
	if(num<0)  return 1; //溢出，肯定是N2>t
     
    
   

    

     

    
    

     
	if(t>num)  return -1; //t更大则返回-1
     
    
   

    

     

    
    

     
	else if(t==num) return 0; //相等则返回0
     
    
   

    

     

    
    

     
	else return 1; //num更大，则返回1
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      LL binarySearch(char N2[],LL left ,LL right ,LL t){ //二分求解N2的进制
     
    
   

    

     

    
    

     

      	LL mid;
     
    
   

    

     

    
    

     
	while(left<=right){
     
    
   

    

     

    
    

     

      		mid=(left+right)/2;
     
    
   

    

     

    
    

     
		int flag=cmp(N2,mid,t); //判断N2转换成十进制后与t比较
     
    
   

    

     

    
    

     
		if(flag==0) return mid; //找到解，则返回mid
     
    
   

    

     

    
    

     
		else if(flag==-1) left=mid+1; //往右子区间继续查找
     
    
   

    

     

    
    

     
		else right=mid-1; //往左子区间继续查找
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return -1; //解不存在
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int findLargestDigit(char N2[]){ //求最大的数位
     
    
   

    

     

    
    

     
	int ans=-1,len=strlen(N2);
     
    
   

    

     

    
    

     
	for(int i=0;i<len;i++){
     
    
   

    

     

    
    

     
		if(Map[N2[i]]>ans){
     
    
   

    

     

    
    

     

      			ans=Map[N2[i]];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return ans+1; //最大的数位为ans，说明进制数的底线是ans+1
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      char N1[20],N2[20],temp[20];
     
    
   

    

     

    
    

     

      int tag,radix;
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	init();
     
    
   

    

     

    
    

     
	scanf("%s %s %d %d",N1,N2,&tag,&radix);
     
    
   

    

     

    
    

     
	if(tag==2){ //交换N1和N2
     
    
   

    

     

    
    

     
		strcpy(temp,N1);
     
    
   

    

     

    
    

     
		strcpy(N1,N2);
     
    
   

    

     

    
    

     
		strcpy(N2,temp);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	LL t=convertNum10(N1,radix,inf);  //将N1从radix进制转换成十进制
     
    
   

    

     

    
    

     

      	LL low=findLargestDigit(N2); //找到N2中数位最大的位加1，作为二分下界
     
    
   

    

     

    
    

     

      	LL high=max(low,t)+1; //上界，用更小的进制基数即可
     
    
   

    

     

    
    

     

      	LL ans=binarySearch(N2,low,high,t);  //二分
     
    
   

    

     

    
    

     
	if(ans==-1)  printf("Impossible\n");
     
    
   

    

     

    
    

     
	else printf("%lld\n",ans);
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

4.注意点

（1）使用遍历进制的暴力枚举会超时。
（2）变量尽量使用long long类型；
对未知进制的数在转换成十进制时判断是否溢出（只要在转换过程中某步小于0即为溢出）。
（3）当N1和N2的十进制相同时，输出N2的radix值。
（4）边界处理：N2进制的下界为所有数位中最大的那个加1，上界=max{下界，N2的十进制}+1—假设已知的是N1的进制。
——可以举栗子：N1=6（10进制），N2=110（求是多少进制时和N1的十进制相同），按照上面的上下界则是2~7，2=1+1,7=max{2,6}+1，上界相当于在N1的最大的数位的基础上加1（毕竟题目问的是满足条件的最小进制）。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103742598