这题看起来不难,实际上并不是一道简单的进制转换问题,有几点需要注意。
- 没有给最大的radix,第一次提交我最大radix设置到了100,只有第7个测试点错误,其余全部正确,于是我把radix设置到了10000,还是只有第七个测试点错误,设置到了1000000,这时有测试点TLE了。。。
- 根据1可知,最大的radix可能很大,所以“暴力”导致超时,这时考虑二分查找。
- 还是因为radix可能很大,这时“应该”考虑到long long int会溢出,这点把我卡住了,于是参考了柳婼的代码,只添加了一句溢出判断,竟然全部AC!感谢柳神🙏。再次感叹:柳神的代码写的真的是精炼,在下佩服。
// runtime: 4ms // space: 368K // https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536 #include <iostream> #include <algorithm> #include <cctype> using namespace std; int CharToInt(char x) { if (x >= 'a' && x <= 'z') return x - 'a' + 10; else return x - '0'; } // 转化为十进制 long long int ToDecimal(string s, long long int radix) { long long int num = 0; int len = s.size(); for (int i = 0; i < len; ++i) { int digit = CharToInt(s[i]); if (digit == 0) continue; long long int tmp = digit; for (int j = 0; j < len - i - 1; ++j) { tmp *= radix; } num += tmp; } return num; } // 二分法找radix,提升效率。 long long int Compare(string s, long long int target) { char it = *max_element(s.begin(), s.end()); long long low = (isdigit(it) ? it - '0' : it - 'a' + 10) + 1; long long int mid = low; long long int high = target + 1; while (low <= high) { long long int result = ToDecimal(s, mid); if (result == target) { return mid; } else if (result < 0 || result > target) { // result < 0 意味着溢出,柳婼NB!!!重要代码 high = mid - 1; } else { low = mid + 1; } mid = (low + high) / 2; } return -1; } int main() { string N[2]; int tag; long long int radix; cin >> N[0] >> N[1] >> tag >> radix; long long int target; target = ToDecimal(N[tag - 1], radix); long long int answer = Compare(N[2 - tag], target); if (answer != -1) { cout << answer << endl; } else { cout << "Impossible" << endl; } return 0; }