[C++知识库] 【PAT】02 高精度

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【PAT】02 高精度 -> 正文阅读

[C++知识库]【PAT】02 高精度

02 高精度

AcWing 1474. 多项式 A + B

问题描述

问题链接：AcWing 1474. 多项式 A + B、原题链接

分析

注意到指数都是整数，范围在[0, 1000]之间，因此可以使用两个数组a、b记录输入的每个指数对应的系数。
最终将a、b相加的结果存储到数组c中即可。

代码

#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    
    int k;
    cin >> k;
    while (k--) {
        int n;
        double v;
        cin >> n >> v;
        a[n] = v;
    }
    
    cin >> k;
    while (k--) {
        int n;
        double v;
        cin >> n >> v;
        b[n] = v;
    }
    
    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])
            k++;
    
    cout << k;
    for (int i = N - 1; i >= 0; i--)
        if (c[i])
            printf(" %d %.1lf", i, c[i]);
    
    return 0;
}

时空复杂度分析

时间复杂度： $O (N)$ ，N为1000。
空间复杂度： $O (N)$ 。

AcWing 1481. 多项式乘积

问题描述

问题链接：AcWing 1481. 多项式乘积、原题链接

分析

注意到指数都是整数，范围在[0, 1000]之间，因此可以使用两个数组a、b记录输入的每个指数对应的系数。
最终将a、b相加的结果存储到数组c中即可。注意c数组的大小是a、b数组的两倍。

代码

#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    
    int k;
    cin >> k;
    while (k--) {
        int n;
        double v;
        cin >> n >> v;
        a[n] = v;
    }
    
    cin >> k;
    while (k--) {
        int n;
        double v;
        cin >> n >> v;
        b[n] = v;
    }
    
    for (int i = 0; i < N; i++)  // 枚举b[i], 然后乘以a中的每一项
        for (int j = 0; j < N; j++)
            c[i + j] += b[i] * a[j];
    
    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]);
    
    cout << endl;
    
    return 0;
}

时空复杂度分析

时间复杂度： $O (N)$ ，N为1000。
空间复杂度： $O (N)$ 。

AcWing 1500. 趣味数字

问题描述

问题链接：AcWing 1500. 趣味数字、原题链接

分析

高精度加法，关于高精度可以参考：高精度运算。
判断两个序列是否完全相同，可以先对序列排序，然后直接比较即可。

代码

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

using namespace std;

int main() {
    
    string s;
    cin >> s;
    vector<int> a;
    for (int i = s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    
    vector<int> b;
    for (int i = 0, t = 0; i < a.size() || t; i++) {
        if (i < a.size()) t += a[i] + a[i];
        b.push_back(t % 10);
        t /= 10;
    }
    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];
    
    cout << endl;
    
    return 0;
}

时空复杂度分析

时间复杂度： $O (n)$ ，n为数字位数。
空间复杂度： $O (n)$ 。

AcWing 1501. 回文数

问题描述

问题链接：AcWing 1501. 回文数、原题链接

分析

模拟。按照题目要求进行运算即可。
因为K最大为100，对于一个10位的数运算，最多变为110位，因此需要使用高精度。关于高精度可以参考：高精度运算。

代码

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<int> &num) {
    for (int i = 0, j = num.size() - 1; i < j; i++, j--)
        if (num[i] != num[j])
            return false;
    return true;
}

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main() {
    
    string n;
    int k;
    cin >> n >> k;
    
    vector<int> a;
    for (int i = n.size() - 1; i >= 0; i--) a.push_back(n[i] - '0');
    
    int cnt = 0;
    if (!check(a)) {
        while (cnt < k) {
            vector<int> b(a.rbegin(), a.rend());
            a = add(a, b);
            cnt++;
            if (check(a)) break;
        }
    }
    
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << endl << cnt << endl;
    
    return 0;
}

AcWing 1544. 霍格沃茨的 A + B

问题描述

问题链接：AcWing 1544. 霍格沃茨的 A + B、原题链接

分析

将每位对应相加，然后从低位向高位进位即可。

代码

#include <cstdio>

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.%d\n", a, b, c);
    
    return 0;
}

AcWing 1629. 延迟的回文数

问题描述

问题链接：AcWing 1629. 延迟的回文数、原题链接

分析

模拟。按照题目要求进行运算即可。
关于高精度可以参考：高精度运算。

代码

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<int> &num) {
    for (int i = 0, j = num.size() - 1; i < j; i++, j--)
        if (num[i] != num[j])
            return false;
    return true;
}

vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

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

void output(vector<int> &a, vector<int> &b, vector<int> &c) {
    out(a);
    cout << " + ";
    out(b);
    cout << " = ";
    out(c);
    cout << endl;
}

int main() {
    
    string s;
    cin >> s;
    
    vector<int> a;
    for (int i = s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    
    int cnt = 0;
    bool flag = false;
    if (!check(a)) {
        while (cnt < 10) {
            vector<int> b(a.rbegin(), a.rend());
            vector<int> c = add(a, b);
            
            output(a, b, c);
            
            a = c;
            cnt++;
            if (check(a)) {
                flag = true;
                break;
            }
        }
    } else {
        flag = true;
    }
    if (!flag) puts("Not found in 10 iterations.");
    else {
        out(a);
        puts(" is a palindromic number.");
    }
    
    return 0;
}