这题拿个20分左右还是比较简单地,拿满分花了很久,代码很丑。
关键要考虑二分和溢出问题,还是贴一下代码。
#include<stdio.h> #include<string.h> #include<stdlib.h> long long rest; //判断sum和tmp小于0考虑了溢出情况 long long RETDEC(char str[],long long radix){ long long i,j=0; long long sum=0; for(i=strlen(str)-1;i>=0;i--){ if('0'<=str[i]&&str[i]<='9'){ long long tmp=1,k=0; while(k<j){ tmp=tmp*radix; if(tmp<0) return -1; k++; } sum=sum+(str[i]-'0')*tmp; if(sum<0) return -1; } if('a'<=str[i]&&str[i]<='z'){ long long tmp=1,k=0; while(k<j){ tmp=tmp*radix; if(tmp<0) return -1; k++; } sum=sum+(str[i]-'a'+10)*tmp; if(sum<0) return -1; } j++; } return sum; } int RETBIG(char str[]){ int maxx=0,i; for(i=strlen(str)-1;i>=0;i--){ if('0'<=str[i]&&str[i]<='9'){ if((str[i]-'0')>maxx) maxx=str[i]-'0'; } if('a'<=str[i]&&str[i]<='z'){ if((str[i]-'a'+10)>maxx) maxx=str[i]-'a'+10; } } return maxx+1; } void binary(long long ans,char str[],long long start,long long end){ if(start>end) return; long long middle=(start+end)/2; if(RETDEC(str,middle)<0||RETDEC(str,middle)>ans) binary(ans,str,start,middle-1); else if(RETDEC(str,middle)<ans) binary(ans,str,middle+1,end); else{ rest=middle; } } int main(){ int tag,radix; long long i,ans; char N1[12],N2[12]; scanf("%s %s %d %d",N1,N2,&tag,&radix); if(tag==1){ ans=RETDEC(N1,radix); rest=-1; int lower=RETBIG(N2); binary(ans,N2,lower,ans+1); } else{ ans=RETDEC(N2,radix); rest=-1; int lower=RETBIG(N1); binary(ans,N1,lower,ans+1); } if(rest==-1) printf("Impossible\n"); else printf("%lld\n",rest); system("pause"); return 0; }