題目鏈接：點擊查看

題目大意：給出兩個數(shù)n1和n2，再給出其中一個數(shù)的進(jìn)制，問另一個數(shù)能否選擇一個進(jìn)制，使得兩個數(shù)的值相等

題目分析：首先這個題目一開始會錯意了，因為題中的表示只給出了0~9以及a~z，所以我就想當(dāng)然的以為最多只能到36進(jìn)制，其實不然，模擬了一發(fā)交了上去發(fā)現(xiàn)WA了一半，就去網(wǎng)上搜題解，因為感覺自己模擬的沒有什么問題，就知道了，原來進(jìn)制只有下限，下限就是此數(shù)字的最大的數(shù)字+1，但沒有上限，于是我回去把代碼中的上限36進(jìn)制改成了70進(jìn)制，因為70的十次方還沒有爆longlong，又交了一發(fā)，這一次幾乎所有的樣例都過了，只有一個除外，沒辦法，只能再想辦法，網(wǎng)上說因為這個單獨的樣例實際上是會爆掉longlong的，但卻又不是很大，那么該怎么辦呢？于是就運用到了有符號數(shù)的一個機制，也就是正數(shù)的最大值+1得到的是負(fù)數(shù)的最小值，這樣一來就可以二分了，因為枚舉的話時間復(fù)雜度頂不住。。二分一下進(jìn)制，然后每次都判斷一下，若在當(dāng)前進(jìn)制下得到了一個負(fù)數(shù)，說明爆longlong了，將其歸為偏大的情況即可，然后就是上下限的設(shè)置問題了，下限的話上面已經(jīng)說過了，就來說說上限該如何選取，因為當(dāng)前的數(shù)的進(jìn)制肯定不可能大于目標(biāo)數(shù)字，所以上限設(shè)為目標(biāo)數(shù)字和下限取一個最大值（可能存在目標(biāo)數(shù)字比下限小的情況），我也試過設(shè)為inf，但又有另一個樣例過不去，不得不說這個數(shù)據(jù)卡的真神奇，如果只是我獨立來做的話最多只能拿到24分，拿到25分還是有點困難的

24分和25分的代碼都掛一下吧：

25：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;LL cal(string s,LL radix) {LL ans=0;for(int i=0;i<s.size();i++){ans*=radix;if(isdigit(s[i]))ans+=s[i]-'0';elseans+=s[i]-'a'+10;}return ans; }LL find_radix(string s,string ss,LL radix) {LL target=cal(s,radix);char ch=*max_element(ss.begin(),ss.end());LL l;if(isdigit(ch))l=ch-'0'+1;elsel=ch-'a'+10+1;LL r=max(target,l);LL ans=-1;while(l<=r){LL mid=l+r>>1;LL temp=cal(ss,mid);if(temp<0||temp>target)r=mid-1;else if(temp<target)l=mid+1;else{ans=mid;break;}}return ans; } int main() { // freopen("input.txt","r",stdin);string n1,n2;int tag,radix;cin>>n1>>n2>>tag>>radix;LL ans=tag==1?find_radix(n1,n2,radix):find_radix(n2,n1,radix);if(ans==-1)printf("Impossible\n");elseprintf("%lld\n",ans);return 0; }

24：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;int main() { // freopen("input.txt","r",stdin);string n1,n2;int tag,radix;cin>>n1>>n2>>tag>>radix;if(tag==1){LL ans=0;for(int i=0;i<n1.size();i++){ans*=radix;if(isdigit(n1[i]))ans+=n1[i]-'0';elseans+=n1[i]-'a'+10;}int mmax=-1;for(int i=0;i<n2.size();i++){if(isdigit(n2[i]))mmax=max(n2[i]-'0',mmax);elsemmax=max(n2[i]-'a'+10,mmax);}for(int i=mmax+1;i<=75;i++){LL ans2=0;for(int j=0;j<n2.size();j++){ans2*=i;if(isdigit(n2[j]))ans2+=n2[j]-'0';elseans2+=n2[j]-'a'+10;}if(ans2==ans)return 0*printf("%d\n",i);}printf("Impossible\n");}else{LL ans=0;for(int i=0;i<n2.size();i++){ans*=radix;if(isdigit(n2[i]))ans+=n2[i]-'0';elseans+=n2[i]-'a'+10;}int mmax=-1;for(int i=0;i<n1.size();i++){if(isdigit(n1[i]))mmax=max(n1[i]-'0',mmax);elsemmax=max(n1[i]-'a'+10,mmax);}for(int i=mmax+1;i<=75;i++){LL ans2=0;for(int j=0;j<n1.size();j++){ans2*=i;if(isdigit(n1[j]))ans2+=n1[j]-'0';elseans2+=n1[j]-'a'+10;}if(ans2==ans)return 0*printf("%d\n",i);}printf("Impossible\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的PAT (Advanced Level) 1010 Radix(二分+模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。