第2章 高精度

1002. A+B for Polynomials

笔记

• 类似高精度加法，但无需考虑进位问题
• 注意系数用double类型，指数可选用int类型

#include <iostream>
using namespace std;
const int N = 1010;
double a[N], b[N], c[N];

int read_data(double x[N]) {
    int k, n;
    double coef;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n >> coef;
        x[n] = coef;
    }
    return k;
}

int add() {
    int k = 0;
    for (int i = 0; i < N; i++) {
        c[i] = a[i] + b[i];
        if (c[i]) k++;
    }
    return k;    
}

int main() {
    int k, k1, k2;
    k1 = read_data(a);
    k2 = read_data(b);

    k = add();
    cout << k;
    for (int i = N - 1; ~i; i--)
        if (c[i]) printf(" %d %.1lf", i, c[i]);

    return 0;
}

1009. Product of Polynomials

笔记

• 类似多项式加法，只是一重循环变成两重循环

#include <iostream>
using namespace std;
const int N = 1010;
double a[N], b[N], c[2 * N];

int input(double x[N]) {
    int k, n;
    double coef;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n >> coef;
        x[n] = coef;
    }
    return k;
}

void mul() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            c[i + j] += a[i] * b[j];
}

int count() {
    int res = 0;
    for (int i = 0; i < 2 * N; i++)
        if (c[i]) res++;
    return res;
}

int main() {
    int k, k1, k2;
    k1 = input(a);
    k2 = input(b);

    mul();
    k = count();
    cout << k;
    for (int i = 2 * N - 1; ~i; i--)
        if (c[i]) printf(" %d %.1lf", i, c[i]);

    return 0;
}

1023. Have Fun with Numbers

笔记

• 大整数加法
• 排序后再判断是否构成相同

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

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

    vector<int> b;
    int t = 0;  
    for (int i = 0; i < a.size(); i++) {
        int tmp = a[i] + a[i] + t;
        b.push_back(tmp % 10);
        t = tmp / 10;
    }
    if (t) b.push_back(t);

    string res;
    for (int i = b.size() - 1; ~i; i--)
        res += (char)('0' + b[i]);

    bool flag = true;
    if (a.size() == b.size()) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        for (int i = 0; i < a.size(); i++)
            if (a[i] != b[i]) {
                flag = false;
                break;
            }
    } else flag = false;

    if (flag) puts("Yes");
    else puts("No");

    cout << res;

    return 0;
}

1024. Palindromic Number

笔记

• 用(a.rbegin(), a.rend())可代替reverse()实现逆置
• y总给出高精度加法的另一种实现形式，无需比较两个数谁长谁短

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool check(vector<int>& a) {
    for (int i = 0, j = a.size() - 1; i < j; i++, j--)
        if (a[i] != a[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++) {
        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 s;
    int k;
    cin >> s >> k;

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

    int cnt;
    for (cnt = 0; cnt < k; cnt++)
        if (!check(a)) {
            vector<int> b(a.rbegin(), a.rend());
            a = add(a, b);
        } else break;

    for (int i = a.size() - 1; ~i; i--)
        printf("%d", a[i]);

    cout << endl << cnt << endl;

    return 0;
}

1058. A+B in Hogwarts

笔记

• 不同的进位制转换，仿照10进制即可

#include <iostream>
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);

    c += f;
    b += e;
    a += d;

    b += c / 29;
    c = c % 29;
    a += b / 17;
    b = b % 17;
    printf("%d.%d.%d\n", a, b, c);

    return 0;
}

1136. A Delayed Palindrome

笔记

• 大整数加法+回文数判断

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

string tostring(vector<int>& A) {
    string res;
    for (int i = 0; i < A.size(); i++)
        res = to_string(A[i]) + res;
    return res;
}

vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t += A[i] + B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);

    return C;
}

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

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

    int i;
    for (i = 0; i < 10; i++)
        if (!check(A)) {
            vector<int> B(A.rbegin(), A.rend());
            vector<int> C = add(A, B);
            cout << tostring(A) << " + " << tostring(B) << 
                            " = " << tostring(C) << endl;
            A = C;
        } else break;

    if (i == 10) puts("Not found in 10 iterations.");
    else cout << tostring(A) << " is a palindromic number." << endl;

    return 0;
}