#include<stdio.h> #include<string> #include<cmath> #include<iostream> using namespace std; int main() { string a,b; int tag,radix; int anum,bnum; //freopen("1010-in.txt","r",stdin); //freopen("1010-out.txt","w",stdout); while(cin>>a>>b>>tag>>radix) { anum=bnum=0; string temp; if(tag==1) { int index=0; for(int j=a.length()-1;j>=0;j--) { anum+=(a[j]>='a'?a[j]-'a'+10:a[j]-'0')*pow(radix*1.0,index); index++; } temp=b; }else { int index=0; for(int j=b.length()-1;j>=0;j--) { anum+=(b[j]>='a'?b[j]-'a'+10:b[j]-'0')*pow(radix*1.0,index); index++; } temp=a; } //printf("anum=%d ",anum); char max=0; //get max num; for(int i=0;i<temp.length();i++) { if(temp[i]>max) max=temp[i]; } int maxNum=(max>='a'?max-'a'+10:max-'0'); bool flag=false; int ind; //printf("maxNum=%d ",maxNum); long long maxRadix=0xffffffff; maxRadix=maxRadix>>1; for(ind=maxNum+1;ind<=maxRadix;ind++) { bnum=0; int index=0; for(int j=temp.length()-1;j>=0;j--) { bnum+=(temp[j]>='a'?temp[j]-'a'+10:temp[j]-'0')*pow(ind*1.0,index); index++; } if(bnum>anum) break; //printf("%d ",bnum); if(anum==bnum) { flag=true; break; } } if(flag) { printf("%d ",ind==1?ind+1:ind); } else { printf("Impossible "); } } }
这道题目误以为基数最大就是36，只拿到19分，但是网上一查才知道基数可以很大很大,可以达到long long类型。如果用上面代码只能得到23分。用long long int是八位。网上说用二分查找，待做。。。。
这道题目觉得很坑，吃完饭再回来写写注意点
#include<stdio.h> #include<string> #include<cmath> #include<iostream> using namespace std; int main() { string a,b; int tag,radix; long long anum,bnum; freopen("1010-in.txt","r",stdin); freopen("1010-out.txt","w",stdout); while(cin>>a>>b>>tag>>radix) { anum=bnum=0; string temp; if(tag==1) { int index=0; for(int j=a.length()-1;j>=0;j--) { anum+=(a[j]>='a'?a[j]-'a'+10:a[j]-'0')*pow(radix*1.0,index); index++; } temp=b; }else { int index=0; for(int j=b.length()-1;j>=0;j--) { anum+=(b[j]>='a'?b[j]-'a'+10:b[j]-'0')*pow(radix*1.0,index); index++; } temp=a; } //printf("anum=%d ",anum); char max='0'; //get max num; //printf("%s ",temp.c_str()); for(int i=0;i<temp.length();i++) { if(temp[i]>=max) max=temp[i]; } int maxNum=(max>='a'?max-'a'+10:max-'0'); bool flag=false; //printf("maxNum=%d ",maxNum); long long int maxRadix=0xffffffff; //for(ind=maxNum+1;ind<=maxRadix;ind++) long long ind=maxNum+1; long long begin=maxNum+1; //long long end=anum+1; long long end=anum>maxNum?anum+1:maxNum+1; //printf("%ld ",e); printf("%s %s ",a.c_str(),b.c_str()); if(a==b) { if(a.length()==1) printf("%d ",maxNum+1==1?2:maxNum+1); else printf("%d ",radix); continue; } while(true) { //printf("%lld ",e); ##long long类型用lld才能正常输出，否则有问题，ld是long int ind=(begin+end)/2; //printf("%lld ",e); printf("begin=%lld,%lld,ind=%lld ",begin,end,ind); bnum=0; int index=0; for(int j=temp.length()-1;j>=0;j--) { bnum+=(temp[j]>='a'?temp[j]-'a'+10:temp[j]-'0')*pow(ind*1.0,index); index++; if(bnum>anum)//这边需要提前判断出来，提前出来，否则可能溢出long long break; } if(anum==bnum) { flag=true; break; } if(begin>=end)//二分法循环是while(left<=right) break; if(bnum>anum) { end=ind-1; } else if(bnum<anum) { begin=ind+1; } } if(flag) { printf("%ld ",ind==1?ind+1:ind); } else { printf("Impossible "); } } }
这道题目刚开始从2迭代到INT.max只有两个数据没有过，估计是超时的，这道题目很奇怪，超时不报超时，而是报WA，这个有点坑爹。
网上找了一下，发现说迭代可能过不了，需要用二分查找来解决这个问题。二分查找的确是个很高效的算法的算法。暴力循环的时候需要可以考虑是否可以采用二分来解决。
while(left<=right)
{
mid=(left+right)/2
if(data[mid]>num)
right=mid-1
else if(data[mid]<num)
left=mid+1
else
return mid;
}
}
这道题目二分查找来寻找adejx；这道题目另外一个坑就是你求出来的数在十进制数的会有超过long long的情况，这个时候也是报WA错误，而不是溢出，runtimeerror之类的。
另外小case，两个数目相等的时候的特判，另外aa aa 1 12==>12和a a 1 15==>11
(A65 a97 0 48)