题解 | 回文数-牛客假日团队赛9L题
L-回文数_牛客假日团队赛9
https://ac.nowcoder.com/acm/contest/1071/L
题目描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：
STEP2：
STEP3：
STEP4：
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个
进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”
输入描述:
两行，分别是N，M。
输出描述:
STEP=ans(ans表示答案)
示例1
输入
9
87
输出
STEP=6
解答
对于16进制的处理可以使用-'A'+10而不必一个个判断。这份代码里面使用的是字符串操作，可以不必这样做，应该会方便一些。进位的时候数组resize一下，扩大一位（我扩大了两位）。然后输出的Impossible!的叹号是半角的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
string KaitenKapatsu(int n, string ipt0);
bool isKaiten(string ipt);
void solve(int n, string ipt);
int main()
{
int n;
string ipt;
cin >> n >> ipt;
solve(n, ipt);
getchar(); getchar();
return 0;
}
string KaitenKapatsu(int n, string ipt0) {
for (int i = 0; i < ipt0.size(); i++) { //读入数据并转为char[]
if (ipt0[i] > 57) //十六进制的处理
ipt0[i] -= 7;
ipt0[i] -= '0';
}
string ipt = ipt0;
for (int i = 0; i < ipt0.size(); i++) //倒序
ipt[i] = ipt0[ipt0.size() - i - 1];
string ipt2 = ipt;
for (int i = 0; i < ipt.size(); i++) { //倒序相加
ipt2[i] += ipt0[i];
}
ipt2.resize(ipt2.size() + 2);
for (int i = 0; i < ipt2.size() - 1; i++) { //进位
ipt2[i + 1] += ipt2[i] / n;
ipt2[i] %= n;
}
for (int i = 0; i < ipt2.size(); i++) { //还原为stirng
if (ipt2[i] >= 10) //十六进制的还原
ipt2[i] += 7;
ipt2[i] += '0';
}
bool judge = 0;
for (int i = ipt2.size()-1; i >= 0; i--) //去除前导零
if (ipt2[i] == '0'&&judge == 0) { ipt2.erase(i, 1); }
else { judge = 1; }
ipt.resize(ipt2.size()); //返回值resize预备输出
for (int i = 0; i < ipt2.size(); i++) //倒序
ipt[i] = ipt2[ipt.size() - 1 - i];
return ipt;
}
void solve(int n,string ipt){ //统计步数
int cnt = 0;
while (isKaiten(ipt) == 0 && cnt<31) {
ipt = KaitenKapatsu(n, ipt);
cnt++;
}
if (cnt > 30){cout << "Impossible!";}
else { cout << "STEP=" << cnt; }
}
bool isKaiten(string ipt) { //判断是不是回文
for (int i = 0; i < ipt.size(); i++)
if (ipt[i] != ipt[ipt.size() - i - 1])return 0;
return 1;
} 来源：Rika
国家电网稳定性 57人发布
