.网站建设的基本步骤,企业网站开发使用方法,湖南网站推,东营人才网完美数
首先#xff0c;介绍一下这篇题解的特邀嘉宾#xff1a;ChatGPT4.0
传送门
题目描述
考古队员小星在一次考察中意外跌入深渊#xff0c;穿越到了一个神秘的荒漠。这里有许多超越他认识的事物存在#xff0c;例如许多漂浮在空中的建筑#xff0c;例如各种奇怪的…完美数
首先介绍一下这篇题解的特邀嘉宾ChatGPT4.0
传送门
题目描述
考古队员小星在一次考察中意外跌入深渊穿越到了一个神秘的荒漠。这里有许多超越他认识的事物存在例如许多漂浮在空中的建筑例如各种奇怪的动物。
在这片荒漠的中央小星发现了一个巨大的类似神庙的建筑为了脱离这片空间小星决定前去探索。
在临近神庙大门时突然跳出了一个人面狮不是斯芬达克斯它咆哮着
“我是这里的守卫要想通过这里必须回答出我的一系列问题否则我就吃了你。”
人面狮告诉小星问题总是这样的模式比 X X X 大的第 N N N 小的回文数是多少。
小星想这个问题看来不难于是问答开始了。
“比 1 1 1 大的第 1 1 1 小回文数数是多少”
“ 2 2 2”
“比 17 17 17 大的第 2 2 2 小的回文数是多少”
“ 33 33 33”
“比 98 98 98 大的第 2 2 2 小的回文数是多少”
“ 101 101 101”
“那比 948237 大的第 2339587 小的回文数是多少”
“*•%*•—#•#*—%*—%”
为了避免被守卫吃掉小星只好打开笔记本想借助电脑却意外地发现可以通过网络网通电信宇宙通找到你于是这个问题就拜托给你了
输入格式
本题每一个数据包含有多组数据。
对于每一个数据包第一行一个数 T T T表示总共有 T T T 组数据。
对于每一组数据包括两行第一行为 X X X第二行为 N N N表示当前询问是比 X 大的第 N 小的回文数是多少。
输出格式
对于每一组数据输出一行表示询问的结果。
样例 #1
样例输入 #1
3
1
1
17
2
98
2样例输出 #1
2
33
101提示
【数据规模】 20 % 20 \% 20% 的数据满足 X ≤ 200000 X \le 200000 X≤200000 N ≤ 1000 N \le 1000 N≤1000。 30 % 30 \% 30% 的数据满足 X , N X, N X,N 在 longint 范围之内且答案也在 longint 范围之内。 100 % 100 \% 100% 的数据满足 X , N ≤ 10 10000 X, N \le {10}^{10000} X,N≤1010000答案 ≤ 10 20001 \le {10}^{20001} ≤1020001。 T ≤ 10 T \le 10 T≤10。 以上来自洛谷 以上来自洛谷 以上来自洛谷
解题思路所有思路与代码都由ChatGPT特供本人只加以润色
暴力思路ChatGPT友情赞助
首先需要找到比X大的第N小的回文数可以从X1开始逐个判断是否是回文数直到找到第N个回文数为止。判断一个数是否是回文数可以将其转化为字符串然后判断字符串是否是回文字符串。找到第N个回文数后输出即可。
伪代码
读入T循环T次 读入X和N初始化count为0ans为0从X1开始逐个判断是否是回文数直到count等于N为止 将当前数转化为字符串判断该字符串是否是回文字符串 初始化i为0j为字符串长度-1循环i小于j 如果字符串第i个字符不等于第j个字符则不是回文字符串跳出循环否则i加1j减1 如果i大于等于j表示是回文字符串将count加1 如果count等于N表示找到了第N个回文数将ans赋值为当前数 输出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个回文数。
Code4TLE 20
#include iostream
#include vector
#include algorithm
using namespace std;vectorint add(vectorint a, vectorint b) {vectorint 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(vectorint num) {int n num.size();for (int i 0; i n / 2; i) {if (num[i] ! num[n - 1 - i]) {return false;}}return true;
}vectorint getNextPalindrome(vectorint 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) {vectorint X;string str;cin str;for (int i str.size() - 1; i 0; i--) {X.push_back(str[i] - 0);}int N;cin N;vectorint 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;
}注该程序经本人改造。
优化还是它
要进一步优化该程序我们可以通过以下方式来提高效率
不需要每次都判断当前数是否是回文数只需要在最后输出时判断即可。在计算下一个回文数时可以直接从当前数一半开始倒序复制这样可以减少循环次数。
Code5RE 30加上高精度就AC了
#include iostream
#include vector
#include cmath
using namespace std;vectorint 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];
}pairint, 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) {pairint, 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加上高精度我之所以不给代码是为了你们养成勤于动手的好习惯
