【PAT甲级】1023 Have Fun with Numbers

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1023 Have Fun with Numbers (pintia.cn)
🔑中文翻译：趣味数字
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1023 Have Fun with Numbers

Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!

Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.

Input Specification:

Each input contains one test case. Each case contains one positive integer with no more than 20 digits.

Output Specification:

For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.

Sample Input:

1234567899
1

Sample Output:

Yes
2469135798
1
2

题意

这道题是让我们计算给定的数字加倍过后的结果是否满足题目要求，比如 123456789 加倍过后得到 246913578 ，发现加倍后的数字都完全由加倍前的数字构成，即加倍前和加倍后都用到了相同的数字构成。

现在让我们输出加倍后的结果，如果满足要求就输出 Yes ，否则输出 No ，并且还要输出加倍后的结果。

思路

这道题由于数字的长度最多能取到 20 ，所以要用到高精度的算法。因为题目只要求算给定数字的平方，故我们可以直接计算该数自加的结果即 $a\ast 2=a+a$ ，这样就可以将高精度乘法问题转换为高精度加法问题，然后再套用高精度加法的模板即可求出本题的答案。

代码

#include
using namespace std;

int main()
{
    string str;
    cin >> str;

    vector<int> a;
    for (int i = str.size() - 1; i >= 0; i--)    a.push_back(str[i] - '0');

    //高精度加法运算模板，a*2=a+a
    vector<int> b;
    int t = 0;
    for (int i = 0; i < a.size(); i++)
    {
        t = a[i] + a[i] + t;
        b.push_back(t % 10);
        t = t / 10;
    }
    if (t) b.push_back(t);

    //判断是否满足条件
    vector<int> c = b;
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());
    if (a == c)    puts("Yes");
    else    puts("No");

    //输出加倍后的数字
    for (int i = b.size() - 1; i >= 0; i--)  cout << b[i];

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34