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加上高精度

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