[数据结构与算法]P1015 [NOIP1999 普及组] 回文数 题解 |c++

题目提供者：CCF—NOI?

时间限制1.00s

内存限制125.00MB

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数?5656，将?5656?加?6565（即把?5656?从右向左读），得到?121121?是一个回文数。

又如：对于十进制数?8787：

STEP1：87+78=16587+78=165
STEP2：165+561=726165+561=726
STEP3：726+627=1353726+627=1353
STEP4：1353+3531=48841353+3531=4884

在这里的一步是指进行了一次?NN?进制的加法，上例最少用了?44?步得到回文数?48844884。

写一个程序，给定一个?NN（2 \le N \le 102≤N≤10?或?N=16N=16）进制数?MM（100100?位之内），求最少经过几步可以得到回文数。如果在?3030?步以内（包含?3030?步）不可能得到回文数，则输出?Impossible!。

输入格式

两行，分别是?NN，MM。

输出格式

如果能在?3030?步以内得到回文数，输出格式形如?STEP=ans，其中?ansans?为最少得到回文数的步数。

否则输出?Impossible!。

输入输出样例

输入 #1

10
87

输出#1

STEP=4

#include <bits/stdc++.h>
using namespace std;
const int maxN = 105;
char sixt[20] = "0123456789ABCDEF";
int n;
string m;
bool hw(string a) { //判断回文
	string s = a; //把 a 赋值给 s
	reverse(s.begin(), s.end()); //反转字符串 s
	return s == a; //判断 a 和 s 是否相等
}
string add(int k, string b) { //高精度加法过程，推广到 k 进制
	string a = b;
	reverse(a.begin(), a.end());
	int numa[maxN], numb[maxN], numc[maxN];
	int len = a.length(), lenc = 1;
	string ans;
	for (int i=0; i<len; i++) {
		if (isdigit(a[i])) numa[len-i] = a[i] - '0'; //对于十六进制的特判，如果是数字减去 0 ，下同
		else numa[len-i] = a[i] - 'A' + 10; //如果不是数字减去 A 再加上 10
		if (isdigit(b[i])) numb[len-i] = b[i] - '0';
		else numb[len-i] = b[i] - 'A' + 10;
	}
	int x = 0;
	while (lenc <= len) {
		numc[lenc] = numa[lenc] + numb[lenc] + x;
		x = numc[lenc] / k; //把除以 10 修改为除以 k
		numc[lenc] %= k; //这里把对 10 取模修改为对 k 取模
		lenc++;
	}
	numc[lenc] = x;
	while (numc[lenc] == 0) lenc--;
	for (int i=lenc; i>=1; i--) ans += sixt[numc[i]];
	return ans;
}
int main() {
	cin >> n >> m;
	for (int i=0; i<=30; i++){ //模拟过程
		if(hw(m)) { //如果是回文数就输出步骤数
			printf("STEP=%d", i);
			return 0;
		}
		else m = add(n, m);
	}
	printf("Impossible!"); //如果超过 30 步则输出 Impossible!
	return 0;
}

此题目题解来源于洛谷作者：hawa130

好了，今天就给大家分享到这里了！我们下次再见！
记得三连哦！