PAT甲级真题：高精度系列题解

1002 A+B for Polynomials
1009 Product of Polynomials
1023 Have Fun with Numbers
1024 Palindromic Number
1058 A+B in Hogwarts
1136 A Delayed Palindrome

1. 高精度加法模板

vector add(vector a, vector b)   // 高精度加法
{
    vector c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++)
    {
        int sum = t;
        if (i < a.size())   sum += a[i];
        if (i < b.size())   sum += b[i];
        c.push_back(sum % 10);
        t = sum / 10;
    }
    return c;
}

2. 双指针判断回文

bool check(vector a)       // 双指针判断回文
{
    for (int i = 0, j = a.size() - 1; i < j; i ++, j --)
        if (a[i] != a[j])
            return false;
    return true;
}

3. 将vector a 中的数取反存到 b 中

vector b(a.rbegin(), a.rend())		// 取反

#include 
#include 
#include 

using namespace std;

const int N = 1005;

double a[N], b[N], c[N];    // x[i] 表示x的i次方的系数

int main( )
{
    int k;
    
    cin >> k;            // 输入a数组
    while (k --)
    {
        int i;
        double m;
        cin >> i >> m;
        a[i] = m;
    }
    
    cin >> k;           // 输入b数组
    while (k --)
    {
        int i;
        double m;
        cin >> i >> m;
        b[i] = m;
    }
    
    for (int i = 0; i < N; i ++) c[i] = a[i] + b[i];
    
    k = 0;
    for (int i = 0; i < N; i ++)
        if (c[i] != 0)
            k ++;
            
    cout << k;
    
    for (int i = N - 1; i >= 0; i --)
        if (c[i] != 0)
            printf(" %d %.1lf", i, c[i]);
    
    
}

#include 
#include 
#include 

using namespace std;

const int N = 1005;

double a[N], b[N], c[N * 2];

void input(double a[])
{
    int k;
    cin >> k;
    while (k --)
    {
        int i;
        double m;
        cin >> i >> m;
        a[i] = m;
    }
}

int main( )
{
    input(a);
    input(b);
    
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            c[i + j] += a[i] * b[j];
    
    int k = 0;
    for (int i = 0; i < N * 2; i ++)
        if (c[i])
            k ++;
            
    cout << k;
    
    for (int i = N * 2 - 1; i >= 0; i --)
        if(c[i])
            printf(" %d %.1lf", i, c[i]);
    
    return 0;
}

#include 
#include 
#include 
#include 

using namespace std;

int main( )
{
    string s;
    cin >> s;
    
    vector a;  // 原数
    vector b;  // 计算过的数
    
    
    // 从各位依次添加进vector
    for (int i = s.size() - 1; i >= 0; i --)
        a.push_back(s[i] - '0');
    
    // 计算
    int t = 0;      // 进位
    for (int i = 0; i < a.size(); i ++)
    {
        int sum = a[i] + a[i] + t;
        b.push_back(sum % 10);
        t = sum / 10;
    }
    
    vector c = b;  // 用来比较的数 
    
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());
    
    if (a == c) puts("Yes");
    else
        puts("No");
    
    if(t) cout<< 1; 
    for (int i = b.size() - 1; i >= 0; i --)
        cout << b[i];
    
    
}

#include 
#include 
#include 
#include 

using namespace std;


bool check(vector a)            // 判断是否回文
{
    for (int i = 0, j = a.size() - 1; i < j; i ++, j --)
        if (a[i] != a[j])
            return false;
            
    return true;
}

vector add(vector a, vector b)       // 高精度加法
{
    vector c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++)
    {
        int s = t;
        if (i < a.size())   s += a[i];
        if (i < b.size())   s += b[i];
        
        c.push_back(s % 10);
        t = s / 10;
    }
    return c;
    
}


int main( )
{
    string n;
    int k;
    cin >> n >> k;

    vector num;
    
    // 存原数
    for (int i = n.size() - 1; i >= 0; i --)    num.push_back(n[i] - '0');
    
    int cnt = 0;
    if (!check(num))
    {
        while (cnt < k)
        {
            vector b(num.rbegin(), num.rend());    // 取反
            
            num = add(num, b);        // 相加
            cnt ++;
            
            if (check(num))   break;
        }
    }
    
    // 输出
    for (int i = num.size() - 1; i >= 0; i --)
        cout << num[i];

    cout << endl << cnt < 
题目：1058 A+B in Hogwarts 
AC代码： 
#include 

using namespace std;

int main()
{
    int a, b, c, d, e, f;
    scanf("%d.%d.%d %d.%d.%d", &a, &b, &c, &d, &e, &f);
    a += d, b += e, c += f;

    b += c / 29, c %= 29;
    a += b / 17, b %= 17;

    printf("%d.%d.%dn", a, b, c);

    return 0;
}
 
题目：1136 A Delayed Palindrome 
AC代码： 
#include 
#include 
#include 
#include 

using namespace std;

bool check(vector a)            // 判断是否回文
{
    for (int i = 0, j = a.size() - 1; i < j; i ++, j --)
        if (a[i] != a[j])
            return false;
            
    return true;
}

vector add(vector a, vector b)       // 高精度加法
{
    vector c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++)
    {
        int s = t;
        if (i < a.size())   s += a[i];
        if (i < b.size())   s += b[i];
        
        c.push_back(s % 10);
        t = s / 10;
    }
    return c;
    
}

void shuchu(vector num)
{
    for (int i = num.size() - 1; i >= 0; i --)
        cout << num[i];
}

int main( )
{
    string n;
    int k = 10;
    cin >> n;
    
    vector num;
    
    // 存原数
    for (int i = n.size() - 1; i >= 0; i --)    num.push_back(n[i] - '0');
    
    int cnt = 0;
    bool st = false;
    if (!check(num))
    {   
        while (cnt < k)
        {
            shuchu(num);
            cout << " + ";
            
            vector b(num.rbegin(), num.rend());    // 取反
            shuchu(b);
            
            num = add(num, b);        // 相加
            cnt ++;
            
            cout << " = ";
            shuchu(num);
            cout << endl;
            
            if (check(num))   
            {
                st = true;
                shuchu(num);
                cout<< " is a palindromic number." << endl;
                break;
            }
        }
    }
    else  // 无需变换，本身就是回文数
    {
        shuchu(num);
        cout<< " is a palindromic number." << endl;
        return 0;
    }    
    
    if(!st)
        cout << "Not found in 10 iterations." << endl;
    
    return 0;
}