PAT A1010 Radix

题目链接

题目大意
有两个数，一个数已知进制，而另一个数进制还不知道，问：在另一个数的进制是多少的情况下，这两个数会相等。

思路

1. 这里先指定s1、s2分别保存的是已知进制数和未知进制数，N1保存s1转换成十进制的数，N2保存s2按一定进制radix转换为十进制的数，用二分法枚举进制radix，下面会补充进制的上界、下界如何取值
2. 比较N1、N2
   如果N2>N1, 说明radix过大，令right=mid-1;
   如果N2<N1，说明radix过小，令left=mid+1;
   如果N2=N1, 结束查找，输出mid。

注意事项

1. 二分查找radix的下界、上界取值
   看到题目说给出的两个数中的数字字符是0-9,a-z，我还以为进制的范围就是在[2,35] 之间，这个题目真的很误导人。事实是，这个条件和这两个数的进制并无关联。

   接着就是，进制的下界，应该取s2中值最大的字符值记为v，再+1；

   上界，应该是在N1和v中取这两个数中的较大值，再+1。可能这里一下子没反应过来，解释一下，设想N1=127，那么s2的位数为1位时，需要的进制最大，那么s2的进制至少需要是127+1或更大，才能使其在只有一位数的情况下等于十进制数127。
   因为题目中要求的是：满足条件的最小进制，所以只需要N1+1便可。
   虽然题目中说两个数的字符只能在0-9和a-z中，但是，应该要想到，进制很大的情况下，就不能仅仅用这36个字符表示了，还会用到表示更大数值的字符，只是题目中给出的数据中不会有这些字符而已，题目中确定数字的字符，只是让我们在进行进制转换时，明确都有哪些字符，这些字符对应什么数值，而不会出现的字符就不需要考虑罢了。

2. 题目中给出的两个数的位数为10，如果进制很大，那么在转换为十进制时，可能会超出int的范围，所以需要用long long 类型保存进制转换后的数据。除此之外，要注意二分的left、right（即进制的下界和上界），要记得定义为long long，我就是因为在二分查找传递left、right时，习惯写成int，有三个测试用例没通过，找了差不多1小时才发现错误。

3. 第2点中说到，数据在转换为十进制时会发生数据溢出，刚开始我会想，如果s1和s2在转换为十进制时都发生溢出，那该怎么处理，因为没法判断两个都溢出的数的大小。 看了《算法笔记上机训练实战指南》之后才发现，测试用例中s1转换成十进制时是不会发生溢出现象的，然而题目中并没有确定这一点，这题目真的很迷。所以，只需要考虑s2转换成十进制可能会发生溢出的情况。

我的代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
typedef long long LL;
using namespace std;

LL map[256];

void init() {
	char c;
	for( c='0'; c<='9'; c++) {
		map[c]=c-'0';
	}
	for( c='a'; c<='z'; c++) {
		map[c]=c-'a'+10;
	}
}

/*反转字符串*/
void reverse(char *s) {
	int len=strlen(s);
	char c;
	for(int i=0; i<len/2; i++) {
		c=s[i];
		s[i]=s[len-1-i];
		s[len-1-i]=c;
	}
}

/*转为十进制*/
LL trans2decimal(char *s,int r) {
	LL rs=0,num;
	char s2[12];

	strcpy(s2,s);
	reverse(s2);
	for(int i=0; i<strlen(s2); i++) {
		num=map[s2[i]];
		rs+=num*(pow(r,i));
		if(rs<0) return -1;
	}
	return rs;
}


/*找出字符数组中字符的最大值*/
int getMaxVauleChar(char *s) {
	int v,max=-1;
	for(int i=0; i<strlen(s); i++) {
		v=map[s[i]];
		if(v>max) {
			max=v;
		}
	}
	return max;
}

//二分查找进制
void binarySearch(LL left,LL right,char *s,LL num) {
	LL mid;
	LL v;
	while(left<=right) {
		mid=(left+right)/2;
		v=trans2decimal(s,mid);	//将未知进制数当做mid进制，转换为十进制
		if(v<0||v>num) { //进制过大或s2转十进制发生溢出 
			right=mid-1;
		} else if(v<num) {//进制过小
			left=mid+1;
		} else {
			break;
		}
	}
	if(left<=right) {
		printf("%d",mid);
	} else {
		printf("Impossible");
	}
}

int main() {
	init();

	char s1[12],s2[12],s[12];//s用于保存未知进制数
	LL num;
	int tag,r;

	scanf("%s%s%d%d",s1,s2,&tag,&r);

	//用num保存已知进制数的十进制
	if(tag==1) {
		num=trans2decimal(s1,r);
		strcpy(s,s2);
	} else if(tag==2) {
		num=trans2decimal(s2,r);
		strcpy(s,s1);
	}

	LL v=getMaxVauleChar(s);	//获取未知进制数中字符的最大值
	LL left=v+1;
	LL right=max(v,num)+1;
	binarySearch(left,right,s,num);

	return 0;
}

如有问题，希望能热心提出，以便我能发现错误，给予纠正。