PAT甲级1010【Radix】二分搜索

之前想暴力过的结果第7个测试点过不去。。其实我一直没想明白最大进制为啥可以大于36，明明表示的时候是到z(35)。。一直WA。。后来看了其他大神的题解才知道用二分做。left=n2中的最大值+1。right=n1的十进制值+1。

由于java的各种慢，以下代码也只能在Pat最快的那台评测机（据姥姥说是1/6的概率）下AC。。TAT

补充：2018.8.9更新，博主二刷这题同样是暴力WA在第7个点。。。（大半年过去了还是这么菜QAQ）据我猜测，第7个点的数据很可能就是诸如进制很大（有可能超过long long，但是自身位数很少）这样就可以构成一个超大的数，比如11在0x7fffffff下就可以变得很大。所以这里总结一下坑点：

1.进制可能超过long long

2.最小进制应该至少比这个数的最大数位大1

3.最大进制应该是最小进制数和另一个数的更大者

4.用二分解题

C++代码：

#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll s2l(string str, ll radix){ ll res = 0; for(int i = 0; i<str.length(); i++){ int tem = str[i]<'a' ? str[i]-'0' : str[i]-'a'+10; res = res*radix + tem; } return res; } void solve(string n1, string n2, int radix){ ll num = s2l(n1, radix); ll left = 0, right, res = num+2; for(int i = 0; i<n2.length(); i++) left = max(left, (ll)n2[i]); left = (left >= 'a' ? left - 'a'+10 : left-'0') + 1; right = max(left, num); while(left <= right){ ll mid = (left+right)/2; ll num2 = s2l(n2, mid); if(num2 > num || num2 < 0) right = mid-1; else if(num2 < num) left = mid+1; else { res = min(res, mid); break; } } if(res == num+2) printf("Impossible\n"); else printf("%ld\n", res); } int main(){ // freopen("aa.txt", "r", stdin); string n1, n2; int radix, tag; cin >> n1 >> n2 >> tag >> radix; tag == 1 ? solve(n1, n2, radix) : solve(n2, n1, radix); return 0; }

Java代码：

import java.util.Scanner; public class Main { static long total; static long left, right; public static void main(String[] args) { Scanner in = new Scanner(System.in); String n1 = in.next(); String n2 = in.next(); int tag = in.nextInt(); int radix = in.nextInt(); if(tag == 2){ String tem = n1; n1 = n2; n2 = tem; } convert(n1, radix); for(int i = 0; i<n2.length(); i++){ if(n2.charAt(i)>left) left = n2.charAt(i); } if(left>='a') left -= 'a'+10; else left -= '0'; left++; right=total+1; binarySolve(n2); } private static void binarySolve(String ss) { long res = total+2; while(left<=right){ long i =(left+right)/2; long sum = 0; for(int j = 0; j<ss.length(); j++){ char ch = ss.charAt(j); int basic = 0; if(ch>='0' && ch<='9') basic=ch-'0'; else basic=ch-'a'+10; sum = sum*i+basic; } if(sum == total) { res= Math.min(res, i); right--; } else if(sum > total || sum < 0){ right = i-1; } else left = i+1; } if(res == total+2) System.out.println("Impossible"); else System.out.println(res); } private static void convert(String s1, int radix) { for(int i = 0; i<s1.length(); i++){ int basic = 0; if(s1.charAt(i)>='0' && s1.charAt(i)<='9') basic = s1.charAt(i)-'0'; else basic = s1.charAt(i)-'a'+10; total = total*radix+basic; } } }