【PAT甲级 - C++题解】1023 Have Fun with Numbers

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

题意

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

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

思路

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

代码

#include<bits/stdc++.h>
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;
}