PAT A1010 二分進位制結合重點題
這道題而可以說是比較難的一道題,如果採用常規遍歷,會出現時長或者溢位的問題;
示例中給出的思路很值得借鑑;
個人通過該示例有以下幾個不同理解:
1.有時候兩個不同進位制的數對比,我們可以進行進位制,轉化十進位制來進行比較;
2.對於有些列舉或者尋找問題,為了不進行列舉遍歷,我們應該第一時間想到二分查詢;
對於第一點,這個在題目中有所體現,我們都是將其轉化為相應的十進位制下,然後進行比較,看是否相同;
在這個途中,有個難點:對於未知進位制數,我們應該如何推斷,一定要注意溢位問題;
在本題目中,並沒有對進位制有限定,如果按照常規進位制計算,就會發生int或這longlong溢位,這一點要注意;
而對於未知進位制數,我們就可以讓二分派上用場;
本題目的根本就是進位制列舉,所以我們可以規定進位制的上界和下界,從而通過二分來尋找一個進位制,使得通過改進之轉換的數和給定的數相同,來達到最終的結果;
那麼問題又來了,上界和下界如何確定?
下界好說,下界就可以取整個數字序列中最大的數,加一就是下界。例如對於一個位15,最起碼應該是16進位制;
而對於上界,比較難以理解,上界取另一個數字在十進位制下的值,加一就是上界;
舉個例子說明一下,假如另一個數字十進位制下是156,如果當前給出的值是1,那麼多少進位制可以讓其和156相等,答案就是156進位制,由於在二分查詢下,我們輸入的序列大原本序列1位,所以還需要+1;
詳細程式碼如下所示:
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; LL inf=(1LL<<63)-1; char n1[20],n2[20],temp[20]; int m[256]; void init(){ for(char c='0';c<='9';c++){ m[c]=c-'0'; } for(char c='a';c<='z';c++){ m[c]=c-'a'+10; } } LL convert2num10(char a[],LL radix,LL t){ LL ans=0; int len=strlen(a); for(int i=0;i<len;i++){ ans=ans*radix+m[a[i]]; if(ans<0||ans>t) //ans<0為大到溢位的情況 return -1; } return ans; } int findLargestDigit(char N2[]){ int ans=-1; int len=strlen(N2); for(int i=0;i<len;i++){ if(m[N2[i]]>ans){ ans=m[N2[i]]; } } return ans+1; } int cmp(char n2[],LL radix,LL t){ int len=strlen(n2); LL num=convert2num10(n2,radix,t); if(num<0) return 1; if(t==num) return 0; else if(t>num) return -1; else return 1; } LL binarySearch(char n2[],LL left,LL right,LL t){ LL mid; while(left<=right){ mid=(left+right)/2; int flag=cmp(n2,mid,t); if(flag==0) return mid; else if(flag==-1) left=mid+1; else right=mid-1; } return -1; } int main(){ init(); int tag,radix; scanf("%s%s%d%d",n1,n2,&tag,&radix); if(tag==2){ strcpy(temp,n1); strcpy(n1,n2); strcpy(n2,temp); } LL t=convert2num10(n1,radix,inf); //將N1從radix進位制轉化為10進位制; LL low=findLargestDigit(n2); //low是序列中最大的數,也就是可以比較的最小進位制,例如110,則合法的進位制最小都未進位制 LL high=max(low,t)+1; //high是上界 LL ans=binarySearch(n2,low,high,t); if(ans==-1) printf("Impossible\n"); else printf("%lld\n",ans); system("pause"); return 0; }