P1643 完美数 题解

完美数

首先，介绍一下这篇题解的特邀嘉宾：ChatGPT4.0

传送门

题目描述

考古队员小星在一次考察中意外跌入深渊，穿越到了一个神秘的荒漠。这里有许多超越他认识的事物存在，例如许多漂浮在空中的建筑，例如各种奇怪的动物。

在这片荒漠的中央，小星发现了一个巨大的类似神庙的建筑，为了脱离这片空间，小星决定前去探索。

在临近神庙大门时，突然跳出了一个人面狮（不是斯芬达克斯）！它咆哮着：

“我是这里的守卫，要想通过这里，必须回答出我的一系列问题，否则，我就吃了你。”

人面狮告诉小星，问题总是这样的模式：比 $X$ 大的第 $N$ 小的回文数是多少。

小星想，这个问题看来不难，于是问答开始了。

“比 $1$ 大的第 $1$ 小回文数数是多少？”

“$2$”

“比 $17$ 大的第 $2$ 小的回文数是多少？”

“$33$”

“比 $98$ 大的第 $2$ 小的回文数是多少？”

“$101$”

“那比 948237 大的第 2339587 小的回文数是多少？”

“*（?%（*?—#?#￥*—%（*—%”

为了避免被守卫吃掉，小星只好打开笔记本想借助电脑，却意外地发现可以通过网络（网通？电信？宇宙通？）找到你，于是这个问题就拜托给你了！

输入格式

本题每一个数据包含有多组数据。

对于每一个数据包，第一行一个数 $T$，表示总共有 $T$ 组数据。

对于每一组数据，包括两行，第一行为 $X$，第二行为 $N$，表示当前询问是比 X 大的第 N 小的回文数是多少。

输出格式

对于每一组数据输出一行，表示询问的结果。

样例 #1

样例输入 #1

3
1
1
17
2
98
2

样例输出 #1

2
33
101

提示

【数据规模】

$20\%$ 的数据满足 $X\le 200000$，$N\le 1000$。

$30\%$ 的数据满足 $X,N$ 在 longint 范围之内，且答案也在 longint 范围之内。

$100\%$ 的数据满足 $X,N\le {10}^{10000}$，答案 $\le {10}^{20001}$。$T\le 10$。

$以上来自洛谷$

解题思路（所有思路与代码都由ChatGPT特供，本人只加以润色）

暴力思路（ChatGPT友情赞助）

1. 首先需要找到比X大的第N小的回文数，可以从X+1开始逐个判断是否是回文数，直到找到第N个回文数为止。
2. 判断一个数是否是回文数可以将其转化为字符串，然后判断字符串是否是回文字符串。
3. 找到第N个回文数后输出即可。

伪代码：

1. 读入T
2. 循环T次：
   1. 读入X和N
   2. 初始化count为0，ans为0
   3. 从X+1开始逐个判断是否是回文数，直到count等于N为止：
      1. 将当前数转化为字符串
      2. 判断该字符串是否是回文字符串：
         1. 初始化i为0，j为字符串长度-1
         2. 循环i小于j：
            1. 如果字符串第i个字符不等于第j个字符，则不是回文字符串跳出循环
            2. 否则，i加1，j减1
         3. 如果i大于等于j，表示是回文字符串，将count加1
      3. 如果count等于N，表示找到了第N个回文数，将ans赋值为当前数
   4. 输出ans

Code1

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(string num) {
	int i = 0, j = num.length() - 1;
	while (i < j) {
		if (num[i] != num[j]) {
			return false;
		}
		i++;
		j--;
	}
	return true;
}

int main() {
	int T;
	cin >> T;
	
	for (int t = 0; t < T; t++) {
		int X, N;
		cin >> X >> N;
		
		int count = 0;
		int ans = 0;
		for (int num = X + 1; count < N; num++) {
			string numStr = to_string(num);
			if (isPalindrome(numStr)) {
				count++;
				ans = num;
			}
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

暴力优化（依旧是ChatGPT大佬提供）

要降低时间复杂度，可以采用以下方法：

• 判断一个数是否是回文数，可以不用将其转化为字符串，而是直接在数字上进行操作。
• 可以利用回文数的对称性质来判断是否是回文数，即从两端往中间进行比较。
• 找到第N个回文数后，不需要继续判断后面的数，可以直接跳出循环。

Code2

#include <iostream>
using namespace std;

bool isPalindrome(int num) {
	int reversedNum = 0;
	int temp = num;
	while (temp > 0) {
		int digit = temp % 10;
		reversedNum = reversedNum * 10 + digit;
		temp /= 10;
	}
	return num == reversedNum;
}

int main() {
	int T;
	cin >> T;
	
	for (int t = 0; t < T; t++) {
		int X, N;
		cin >> X >> N;
		
		int count = 0;
		int ans = 0;
		for (int num = X + 1; count < N; num++) {
			if (isPalindrome(num)) {
				count++;
				ans = num;
			}
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

继续优化（依然是它）

要进一步降低时间复杂度，可以采用以下方法：

• 判断一个数是否是回文数的操作可以进一步优化。可以只判断一半的数字，而不需要全部反转，然后与另一半进行比较。
• 可以通过找到下一个回文数的规律来快速找到第N个回文数。

优化后的代码如下：

Code3

#include <iostream>
using namespace std;

bool isPalindrome(int num) {
    if (num < 0 || (num % 10 == 0 && num != 0)) {
        return false;
    }
    
    int reversedNum = 0;
    while (num > reversedNum) {
        reversedNum = reversedNum * 10 + num % 10;
        num /= 10;
    }
    
    return num == reversedNum || num == reversedNum / 10;
}

int getNextPalindrome(int num) {
    num++;
    while (!isPalindrome(num)) {
        num++;
    }
    return num;
}

int main() {
    int T;
    cin >> T;
    
    for (int t = 0; t < T; t++) {
        int X, N;
        cin >> X >> N;
        
        int ans = getNextPalindrome(X);
        for (int i = 1; i < N; i++) {
            ans = getNextPalindrome(ans);
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

这样，我们通过优化判断回文数的方式以及找到下一个回文数的规律，可以更快地找到第N个回文数，进一步降低时间复杂度。

加上高精度算法优化（是它）

要使用高精度算法优化，可以采用以下方法：

• 定义一个高精度整数类，可以实现大整数的加法、减法和乘法等操作。
• 在每次计算回文数时，将当前数字转化为高精度整数，进行高精度的加法操作，直到找到第N个回文数。

Code4（TLE 20）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> add(vector<int>& a, vector<int>& b) {
	vector<int> res;
	int carry = 0;
	int n = max(a.size(), b.size());
	for (int i = 0; i < n; i++) {
		int sum = carry;
		if (i < a.size()) {
			sum += a[i];
		}
		if (i < b.size()) {
			sum += b[i];
		}
		res.push_back(sum % 10);
		carry = sum / 10;
	}
	if (carry) {
		res.push_back(carry);
	}
	return res;
}

bool isPalindrome(vector<int>& num) {
	int n = num.size();
	for (int i = 0; i < n / 2; i++) {
		if (num[i] != num[n - 1 - i]) {
			return false;
		}
	}
	return true;
}

vector<int> getNextPalindrome(vector<int>& num) {
	int carry = 1;
	int n = num.size();
	for (int i = 0; i < n; i++) {
		num[i] += carry;
		carry = num[i] / 10;
		num[i] %= 10;
	}
	if (carry) {
		num.push_back(carry);
	}
	return num;
}

int main() {
	int T;
	cin >> T;
	
	for (int t = 0; t < T; t++) {
		vector<int> X;
		string str;
		cin >> str;
		for (int i = str.size() - 1; i >= 0; i--) {
			X.push_back(str[i] - '0');
		}
		
		int N;
		cin >> N;
		
		vector<int> ans = X;
		for (int i = 0; i < N; i++) {
			ans = getNextPalindrome(ans);
			while (!isPalindrome(ans)) {
				ans = getNextPalindrome(ans);
			}
		}
		
		for (int i = ans.size() - 1; i >= 0; i--) {
			cout << ans[i];
		}
		cout << endl;
	}
	
	return 0;
}

• 注：该程序经本人改造。

优化++（还是它）

要进一步优化该程序，我们可以通过以下方式来提高效率：

• 不需要每次都判断当前数是否是回文数，只需要在最后输出时判断即可。
• 在计算下一个回文数时，可以直接从当前数一半开始倒序复制，这样可以减少循环次数。

Code5（RE 30）（加上高精度就AC了）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> tmp(1, 0);

void initialize() {
	for (int i = 0; i < 20000; i++) {
		tmp.push_back(-1);
	}
}

int sum(int x) {
	if (tmp[x] != -1) {
		return tmp[x];
	}
	if (x % 2 == 0) {
		tmp[x] = (pow(10, x / 2) - 1) / 9 * 2;
	}
	if (x % 2 == 1) {
		tmp[x] = sum(x + 1) - pow(10, x / 2);
	}
	return tmp[x];
}

pair<int, int> count(int x) {
	x = (x + 8) / 9;
	int i = to_string(x).length() - 9;
	if (i < 1) {
		i = 1;
	}
	while (true) {
		if (sum(i) >= x) {
			return make_pair(i, 9 * sum(i - 1));
		}
		i++;
	}
}

int solve(int x) {
	pair<int, int> result = count(x);
	int cnt = result.first;
	int sum = result.second;
	int half = pow(10, (cnt + 1) / 2 - 1) + (x - sum - 1);
	if (cnt % 2 == 1) {
		string halfStr = to_string(half);
		return stoi(halfStr.substr(0, halfStr.length() - 1) + string(halfStr.rbegin(), halfStr.rend()));
	} else {
		string halfStr = to_string(half);
		return stoi(halfStr + string(halfStr.rbegin(), halfStr.rend()));
	}
}

int rev(int x) {
	int sz = to_string(x).length();
	int Sum = sum(sz - 1) * 9;
	Sum += stoi(to_string(x).substr(0, (sz + 1) / 2)) - pow(10, sz / 2 + sz % 2 - 1);
	while (solve(Sum) <= x) {
		Sum++;
	}
	return Sum - 1;
}

int main() {
	initialize();
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N, X;
		cin >> N >> X;
		cout << solve(X + rev(N)) << endl;
	}
	return 0;
}

AC Code

//Code5加上高精度

我之所以不给代码是为了你们养成勤于动手的好习惯