算法刷题记录：[NOIP1999]回文数

题目链接

https://ac.nowcoder.com/acm/contest/19859/G

题目分析

高精度相加 + 进制转换 + 判断回文的模拟题。

AC代码

// Problem: [NOIP1999]回文数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19859/G
// Memory Limit: 262144 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>

using namespace std;

int n;
string a, b;

vector<int> add(vector<int> A)
{
	vector<int> B;
	int t = 0;
	for (size_t i = 0, j = A.size() - 1; i < A.size() && j >= 0; ++ i, -- j)
	{
		t += A[i] + A[j];
		B.push_back(t % n);
		t /= n;
	}
	if (t) B.push_back(t);
	while (B.size() > 1 && B.back() == 0) B.pop_back();
    return B;
}

bool f(vector<int> B)
{
	for (size_t i = 0, j = B.size() - 1; i < B.size() && j >= 0; ++ i, -- j)
		if (B[i] != B[j]) return false;
	return true;
}

int main()
{
	cin >> n >> a;
	
	for (int i = a.size() - 1; i >= 0; -- i) b += a[i];
	
	// 字符串 -> 数字
	vector<int>	A, B;
	for (int i = a.size() - 1; i >= 0; -- i) 
		if (a[i] >= '0' && a[i] <= '9') A.push_back(a[i] - '0');
		else A.push_back(a[i] - 'A' + 10);
	
	// 用两个指针相加，结果加入B，判断B是否为回文
	int cnt = 0;
	do
	{
		B = add(A);		// 相加完后，B的值赋值给A
		A = B;
		++ cnt;
	}while(!f(B) && cnt <= 30);		// 不是回文的时候，一直循环
	
	if (cnt > 30) cout << "Impossible!" << endl;
	else cout << "STEP=" << cnt << endl; 	
}