【PAT甲级题解记录】1010 Radix (25 分)

前言

Problem：1010 Radix (25 分)

Tags： 二分 进制转换 上限溢出

Difficulty：剧情模式 想流点汗 想流点血 死而无憾

Address：1010 Radix (25 分)

问题描述

问题转化过来就是给你俩个数，其中一个数确定进制，确定另一个数的进制，要求是能使俩数相等的最小进制。

解题思路

1. 基础思路就是先把确定进制的数转化为10进制数 $temp$，然后找另一个数的进制使其转化为10进制后相等。
2. 由于题目中说的是“ A digit is less than its radix and is chosen from the set { 0-9, a-z } ”，有可能会让人误以为最大不会超过36，但这句话只规定了输入而已所以不能直接遍历2-36。（这是第一个坑点）
3. 答案最小是未确定数的最大数位+1，最大不会超过 $temp$（这里要注意不能直接去 $temp$，因为 $temp$ 可能小于最大数位+1，思考后可以发现最大值取俩者中大值即可，这是第二个坑点）。
4. 既然范围那么大，而且范围内各个数在题目中的意义具有单调性，我们选择二分查找答案，即进制，但是在判断是否为答案的过程中可能会溢出（开ll也无济于事，这是第三个坑点），所以二分时不能简单的判断大小还要判断是否是溢出后的结果，这道题可以简单的判断是否出现负数就能过。
5. 问题是像zzzzzzzzzz 10 1 36这样的输入怎么办，题目合理性存疑，不过也可能是我脑子抽了，记住这些坑吧。

参考代码

/** @Author: Retr0.Wu * @Date: 2022-02-15 15:48:41 * @Last Modified by: Retr0.Wu* @Last Modified time: 2022-02-15 22:03:26*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll toDecimal(string num, ll radix)
{ll ans = 0;for (int i = 0; i < num.size(); i++){if (isalpha(num[i])){ans = ans * radix + num[i] - 'a' + 10;if (num[i] - 'a' + 10 >= radix){return -1;}}else if (isdigit(num[i])){ans = ans * radix + num[i] - '0';if (num[i] - '0' >= radix){return -1;}}}return ans;
}
int main()
{string N1, N2;int tag, radix;cin >> N1 >> N2;cin >> tag >> radix;if (tag == 2){swap(N1, N2);}ll temp = toDecimal(N1, radix); // 已知数的十位数表示//cout<<"temp:"<<temp<<endl;int ansR = 0;int maxx = 0;for (int i = 0; i < N2.size(); i++){maxx = max(maxx, isdigit(N2[i]) ? N2[i] - '0' : N2[i] - 'a' + 10);}// 所求数的进制至少比这个数中最大的那位数多一ll l = maxx + 1;// 所求数的进制至多是已知数的十位数表示，多了就没有意义了，而我们需要的是最小的答案// 但是如果已知数比他的最大位+1还小，那么唯一的可能是 N2=temp，所以此时还是需要尝试下l是不是可以ll r = max(temp, l);while (l <= r){ll mid = (l + r) >> 1;ll nowDecimal = toDecimal(N2, mid);if (nowDecimal == temp){ansR = mid;break;}else if (nowDecimal > temp || nowDecimal < 0){r = mid - 1;}else{l = mid + 1;}}cout << (ansR ? to_string(ansR) : "Impossible") << endl;return 0;
}

总结

1. 要对二分敏感，二分是非常常用且效率极高的算法。

2. 对于一些简单二分，可以调用STL 的 函数 ，总结如下：

   // 1. binary_search:bool std::__1::binary_search<int *, int>(int *__first, int *__last, const int &__value_)
   // 返回查找value是否出现的布尔值// 2. lower_bound:int *std::__1::lower_bound<int *, int>(int *__first, int *__last, const int &__value_)  
   // 返回在前闭后开范围内找到的第一个大于等于value的数的位置，找不到返回范围末尾位置（即实际闭区间的下一个位置）// 3. upper_bound:int *std::__1::upper_bound<int *, int>(int *__first, int *__last, const int &__value_)
   // 返回在前闭后开范围内找到的第一个大于value数的位置，找不到返回范围末尾位置（即实际闭区间的下一个位置）// example：a[8]= {4,10,11,30,69,70,96,100};binary_search(a,a+8,4);    // 查找成功，返回1binary_search(a,a+8,40);   // 查找失败，返回0lower_bound(a,a+8,10)-a;   // 返回1lower_bound(a,a+8,101)-a;  // 找不到返回last位置8upper_bound(a,a+8,10)-a;   // 返回2upper_bound(a,a+8,101)-a;  // 找不到返回last位置8
   

3. 注意运算过程中的数值溢出。