PTA甲级考试真题练习10——1010 Radix
程序员文章站
2022-06-07 13:06:17
...
题目
生词生句
- 6 is a decimal number and 110 is a binary number
6是十进制数,110是二进制数
思路
得分容易,满分难,坑多,基本思路:将给定的源操作数按照指定的进制转换成十进制,然后在找出一个进制使目标操作数转化成十进制后与源操作数相等
坑点
1. 进制的上下限不是随便取的,下限应该是目标操作数中的最大位+1,如果小于这个数是没有意义的,上限应该是源操作数转换成十进制后的数,因为如果大于这个数也没意义,因为个位数最大是36,再大就成10,其中的1转换成十进制已经超过源操作数的大小了。
2. 转换成十进制后会溢出成负数,所以设为long long,但是long long 依然会有溢出的情况,溢出后为负,所以为负的时候进制不符合要求,应该找更小的进制。
3. 如果暴力循环的话会导致超时,所以使用二分法,但是注意题目中说到多个进制满足的时候输出最小的进制,所以应该先对前36个进制进行暴力**(个位最大为36),然后再使用二分法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
#define nmax 100
long long changeRadix(string num, int radix)
{
int k = 0;
long long sum = 0;
for (int i = num.length() - 1; i >= 0; --i)
{
if (num[i] >= '0' && num[i] <= '9')
sum += (int)(num[i] - '0') * pow(radix, k);
else if (num[i] >= 'a' && num[i] <= 'z')
sum += ((int)(num[i] - 'a') + 10) * pow(radix, k);
++k;
}
return sum;
}
int main()
{
string tagnum, srcnum;
int tag, radix;
cin >> srcnum >> tagnum >> tag >> radix;
if (tag == 2)
swap(tagnum, srcnum);
//将源数转换为10进制
long long srcnum_ch = changeRadix(srcnum, radix);
//选出目的操作数的最小数确定最小进制
int minRadix = 0;
for (int i = 0; i < tagnum.length(); ++i)
{
if (tagnum[i] >= '0' && tagnum[i] <= '9')
{
minRadix = max(minRadix, (int)(tagnum[i] - '0'));
}
else if (tagnum[i] >= 'a' && tagnum[i] <= 'z')
{
minRadix = max(minRadix, (int)(tagnum[i] - 'a') + 10);
}
}
minRadix += 1;
//遍历进制,看看哪个进制转换十进制数后相等
for (int i = minRadix; i <= 36; ++i)
{
long long tagnum_ch = changeRadix(tagnum,i);
if (tagnum_ch == srcnum_ch)
{
cout << i;
return 0;
}
}
long long low = 37, high = srcnum_ch+1,mid;
while (low <= high)
{
mid = (low + high) / 2;
long long tagnum_ch = changeRadix(tagnum,mid);
if (tagnum_ch == srcnum_ch)
{
cout << mid;
return 0;
}
if (tagnum_ch < srcnum_ch || srcnum_ch<0)
low = mid + 1;
else
high = mid - 1;
}
cout << "Impossible";
return 0;
}
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting