[NOIP1999] 回文数 - 代码 - 做个记录

高精度加法 + 进制转换 + 回文数

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

const int N = 110;

// 构造反串 
string fan(string& x) {  
	int p = x.size();
	while(p > 1 && x[p - 1] == '0') p--;
	string y = x.substr(0, p); // 去除后导零            // substr 少了个参数 pos - 坑 3 
	reverse(y.begin(), y.end());						// 忘记反转了 - 坑 4 
	return y;
}

// 判断是否为回文串 
bool pd(string& x) {
	string y = fan(x);
	return x == y;
}

// n >= 2 && n <= 10    - 参数顺序写错了 - 坑 5 
string add1(int c[], int a[], int b[], int lc, int la, int lb, string& x, string& y, int n) {
	// 逆序存放 
	for(int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
	for(int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';
	
	// 加法过程
	for(int i = 0; i < lc; i++) {
		c[i] += a[i] + b[i];
		c[i + 1] += c[i] / n;
		c[i] %= n;
	}
	
	// 最高位进一位 
	if(c[lc]) lc++;
	
	// 转化为字符串返回 - 记得逆回来   						// 忘记逆回来了 -  坑 1 
	string ret = "";
	for(int i = lc - 1; i >= 0; i--) {
		ret.push_back(c[i] + '0');
	}
	
	return ret;
}

// n == 16            				  - 参数顺序写错了 - 坑 5 
string add2(int c[], int a[], int b[], int lc, int la, int lb, string& x, string& y, int n) {
	// 逆序存放 
	for(int i = 0; i < la; i++) {
		if(isdigit(x[i])) a[la - 1 - i] = x[i] - '0';
		else a[la - 1 - i] = x[i] - 'A' + 10; 
	}
	for(int i = 0; i < lb; i++) {
		if(isdigit(y[i])) b[lb - 1 - i] = y[i] - '0';
		else b[lb - 1 - i] = y[i] - 'A' + 10;
	}
	
	// 加法过程
	for(int i = 0; i < lc; i++) {
		c[i] += a[i] + b[i];
		c[i + 1] += c[i] / n;
		c[i] %= n;
	}
	
	// 最高位进一位 
	if(c[lc]) lc++;
	
	// 转化为字符串返回 - 记得逆回来  
	string ret = "";
	for(int i = lc - 1; i >= 0; i--) {
		if(c[i] < 10) ret.push_back(c[i] + '0');             //  c[i] < 10 写成了 c[i] <= 10 - 坑 6 
		else ret.push_back(c[i] - 10 + 'A');
	}
	
	return ret;
}

// 高精度加法 - 针对不同进制 - 返回字符串 
string add(string& x, string& y, int n) {
	int a[N] = {0}, b[N] = {0}, c[N] = {0};
	int la = x.size(), lb = y.size(), lc = max(la, lb);
	
	// n == 16 的情况要特判 
	if(n == 16) return add2(c, a, b, lc, la, lb, x, y, n);
	return add1(c, a, b, lc, la, lb, x, y, n);
	
}

// 计算答案 
int calc(string& x, int n) {
	// 特判 x 为回文串的情况              - 忘记特判  - 坑 7  
	if(pd(x)) return 0;
	
	string y = fan(x);
	
	int ret = 0;
	string t;
	do {									// 坑 2   实际上用 while () 也行 
		t = add(x, y, n); 
		ret++;
		if(ret > 30) return -1;
		x = t; y = fan(x); // 更新参数 
	} while(!pd(t));
	
	return ret;
}

void solve() {
	int n; cin >> n;
	string x; cin >> x;
	
	int ans = calc(x, n);
	
	if(ans == -1) cout << "Impossible!" << endl;
	else cout << "STEP=" << ans << endl; 
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
	
	return 0;
}