P1643 完美数题解

tXX_F · 2024-01-11 07:22:15 · 题解

完美数

传送门

前言

居然只有一篇题解，还是 py3 的那么就由本人写一篇 c++ 题解吧

解题思路

暴力思路

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

伪代码：

读入 T
循环 T 次：
1. 读入 X 和 N
2. 初始化 count 为0， ans 为 0
3. 从 X+1 开始逐个判断是否是回文数，直到 count 等于 N 为止：
  1. 将当前数转化为字符串
  2. 判断该字符串是否是回文字符串：
    1. 初始化 i 为 0 ， j 为字符串长度 -1
    2. 循环 i 小于 j ：
    3. 如果字符串第 i 个字符不等于第 j 个字符，则不是回文字符串跳出循环
    4. 否则， i 加 1 ， j 减 1
    5. 如果 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;
}

暴力优化

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

判断一个数是否是回文数，可以不用将其转化为字符串，而是直接在数字上进行操作。
可以利用回文数的对称性质来判断是否是回文数，即从两端往中间进行比较。
找到第 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;

#define int long long

vector<int> temp(1, 0);

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

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

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

inline int Mksum(int x) {
    pair<int, int> result = Cnt(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()));
    }
}

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

inline void solve() {
    int N, X;
    cin >> N >> X;
    int Answer = Mksum(X + rev(N));
    cout << Answer << endl;
}

inline void work() {
    initialize();
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}

AC Code

// Code5 加上高精度

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

P1643 完美数 题解

完美数

传送门

前言