PAT A1023 Have Fun with Numbers (20 分) 大数加法

    题目大意:给出一个不超过20位的整数,判断它的两倍的结果是否是原有的数字的一个排列。

    unsigned long long 最多表示到 2^64 - 1,小于 10^20,所以要用大数加法的方式去得到两倍的结果,存储在vector<int>中,然后将原数和两倍分别排序,比较排序后的两个vector是否相同即可。

AC代码如下:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>


using namespace std;

bool isPermuation(vector<int> &v, vector<int> &ans)
{
    int carry = 0;
    for (int i = v.size() - 1; i >= 0; --i)
    {
        int tmp = v[i] * 2 + carry;
        if(tmp >= 10)
        {
            ans.push_back(tmp - 10);
            carry = 1;
        }
        else
        {
            ans.push_back(tmp);
            carry = 0;
        }
    }
    if(carry == 1)
    {
        ans.push_back(1);
        return false;
    }
    vector<int> ansCopy = ans;
    sort(ansCopy.begin(), ansCopy.end());
    sort(v.begin(), v.end());
    if(v != ansCopy) return false;
    return true;
}


int main()
{
    string str;
    cin >> str;
    vector<int> v, ans;
    for (int i = 0; i < str.size(); ++i)
    {
        v.push_back(str[i] - '0');
    }
    bool flag = isPermuation(v, ans);
    if(flag) printf("Yes\n");
    else printf("No\n");
    for (int i = ans.size() - 1; i >= 0; --i)
    {
        printf("%d", ans[i]);
    }
    return 0;
}


 

上一篇:PAT A1024 Palindromic Number (25 分) 大数加法


下一篇:数组加1