开发: 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甲级刷题记录-(AcWing)-(Day03高精度与进位制 8题) -> 正文阅读

[C++知识库]PAT甲级刷题记录-(AcWing)-(Day03高精度与进位制 8题)

PAT甲级刷题记录-(AcWing)-(Day03高精度与进位制 8题)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目

今日刷题列表

1002 A+B for Polynomials
1009 Product of Polynomials
1023 Have Fun with Numbers
1024 Palindromic Number
1010 Radix
1015 Reversible Primes
1027 Colors in Mars
1100 Mars Numbers

1002 A+B for Polynomials

AcWing链接
 PAT链接

英语单词

polynomials 多项式
nonzero terms 非零项
exponents and coefficients 指数和系数

解析

使用三个double数组来存放多项式的系数
数组的下标代表了多项式的次数
通过遍历将a与b多项式的和累加到c上

注意点

con的判断过程中,要注意到类似a = [1 ... ],b =[ -1 ... ]的情况, 也就是说在a,与b中存在该次数的系数,但是累加之后被消去,不能统计到con中
如果最后的结果是0, 单单输出0即可
输出控制保留一位小数

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

const int N = 1010;
using namespace std;

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

int main() {
    int k;
    cin >> k;
    int exponent; // 指数
    for (int i = 0; i < k; ++i) {
        cin >> exponent;
        cin >> a[exponent];
    }
    cin >> k;
    for (int i = 0; i < k; ++i) {
        cin >> exponent;
        cin >> b[exponent];
    }
    int con = 0;
    for (int i = 0; i < N; ++i) {
        if (a[i] || b[i]) {
            c[i] += a[i] + b[i];
            if(c[i])
                con++;
        }
    }
    cout << con;
    for (int i = N - 1; i >= 0; i--) {
        if (c[i]) {
            printf(" %d %.1f", i, c[i]);
        }
    }
    return 0;
}

1009 Product of Polynomials

AcWing链接
 PAT链接

英语单词

Product 乘积
解析
存储方面与上一题类似, 主要区别在于计算多项式的乘法
对于多项式的乘法可以采取两层循环,即让多项式a的每一项与多项式b来相乘, 相乘的过程为c[i + j] += a[i] * b[j]; 也就是系数相乘, 指数相加- 后面的操作与上一题一模一样

#include <iostream>
#include <cstdio>

const int N = 1010;
using namespace std;
double a[N], b[N], c[2 * N];

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

1023 Have Fun with Numbers

AcWing链接
 PAT链接

英语单词

consisting 组成
permutation 排列
this property 这个性质

解析
long long形的整数大概是18位左右,而题目中的要求是no more than 20 digits, 因此这里用数组或者vector来存取
知识点

tips: c++中的sort函数

可以直接用==来比较两个vector 数组是否相等
sort排序的用法
- 首先要导入头文件algorithm
- sort(起始地址，结束地址)
- C++中sort排序用法跳转链接

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

using namespace std;

vector<int> double_number(vector<int> &a) {
    vector<int> b;
    int t = 0, i;
    for (i = a.size() - 1; i >= 0; i--) {
        b.push_back((a[i] * 2 + t) % 10);
        t = (a[i] * 2 + t) / 10;
    }
    if (t)
        b.push_back(t);
    return b;
}

int main() {
    // 1234567899
    string n;
    cin >> n;
    vector<int> number;
    for (int i = 0; i < n.size(); ++i) {
        number.push_back(n[i] - '0');
    }
    vector<int> result = double_number(number);
    vector<int> tmp = result;
    sort(number.begin(), number.end());
    sort(tmp.begin(), tmp.end());
    if (tmp == number) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    for (int i = result.size() - 1; i >= 0; i--) {
        cout << result[i];
    }


    return 0;
}

1024 Palindromic Number

AcWing链接
 PAT链接

英语单词

Palindromic Number 回文数
via 经过,通过

解析

编写函数判断是否为回文数
编写函数执行数字翻转相加

tips: vector反转

vector<int> b(a.rbegin(), a.rend())

tips: 两数相加通用模板

a没循环完就继续加a
b没循环完就继续加b
进位t还在就继续加t
在这里插入图片描述

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

using namespace std;

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

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

int main() {
    string N;
    int K;
    cin >> N >> K;
    vector<int> number;
    int cur_k = 0;
    for (int i = 0; i < N.size(); ++i) {
        number.push_back(N[i] - '0');
    }
    if (is_data(number)) {
        for (auto num:number) {
            cout << num;
        }
        cout << endl << cur_k;
    } else {
        while (!is_data(number)) {
            cur_k++;
            number = add_vec(number);
            if (cur_k == K)
                break;
        }
        for (int i = number.size() - 1; i >= 0; --i) {
            cout << number[i];
        }
        cout << endl << cur_k;
    }

    return 0;
}

1010 Radix

AcWing链接
 PAT链接

英语单词

equation 等式,方程
decimal number 十进制数, 小数
radix 基数, 进制
解析
这道题花了很久的时间, 主要卡在了long long类型边界一些地方,这里的cal函数中的radix也要改为long long类型, 因为之后的进制可能会很大,超过int的范围
LL cal(string N1, LL radix) 用来将给定进制的字符串转换为十进制的值

二分查找

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

题解

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

typedef long long LL;
using namespace std;

int get(char c) {
    if (c <= '9') return c - '0';
    else return c - 'a' + 10;
}

LL cal(string N1, LL radix) {
    LL res = 0;
    for (auto c:N1) {
        if ((double) res * radix + get(c) > 1e16) return 1e18;
        res = res * radix + get(c);
    }
    return res;
}

int main() {
    string N1, N2;
    int tag, radix;
    cin >> N1 >> N2 >> tag >> radix;
    if (tag == 2) {
        swap(N1, N2);
    }// 使得radix对应为N1的进制
    // 将N1转换为radix进制数字
    LL target = cal(N1, radix);
    // 二分查找
    LL l = 0;
    for (auto c : N2) l = max(l, (LL) get(c) + 1);
    LL r = target + 1;
    while (l < r) {
        LL mid = l + r >> 1;
        if (cal(N2, mid) >= target) r = mid;
        else l = mid + 1;
    }
    if (cal(N2, r) != target) puts("Impossible");
    else cout << r << endl;
    return 0;
}

1015 Reversible Primes

AcWing链接
 PAT链接

英语单词

Prime 质数

解析

注意反转数字的时候要先转成对应的进制反转,我一开始没想清楚直接用十进制反转了就G了
在翻转数字的过程中可以直接求得翻转后的十进制结果
比如6转为2进制本该为110,翻转后得到011
而使用辗转相除法得到的二进制结果正是011, 可以直接使用res = res * 2 + n % d的方式求和

#include <sstream>
#include <iostream>
#include <cstdio>
#include <algorithm>

typedef long long LL;
using namespace std;

bool is_prime(int x) {
    if (x == 1) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0)return false;
    }
    return true;
}
// 7 2
// 7 / 2 = 3 ... 1
// 3 / 2 = 1 ... 1
// 1 / 2 = 0 ... 1

bool check(int n, int d) {
    if (!is_prime(n)) return false;
    // reverse
    int res = 0;
    while (n) {
        res = res * d + n % d;
        n = n / d;
    }
    return is_prime(res);
}


int main() {
    int n,d;
    while (true) {
        cin >> n;
        if (n < 0)
            break;
        cin >> d;
        if (check(n, d)) puts("Yes");
        else puts("No");
    }
    return 0;

}

1027 Colors in Mars

AcWing链接
 PAT链接

解析
本题思路很简单, 输入的三个数字, 把每个数字都转成相应的13进制就可以了
这里要注意到进制之间的转换问题,以及不满两位的补0问题
我的代码

#include <iostream>
#include <cstdio>

using namespace std;


void change(int r) {
    // 将r转换为13进制的数并输出
    // 因为数字小于169
    // 15: 15 / 13 = 1 14 % 13 = 2 14 = 12
    if (r < 10)
        printf("%02d", r);
    else if (r < 13)
        printf("0%c", r - 10 + 'A');
    else { // r>=13
        int high = r / 13;
        int low = r % 13;
        if (high >= 10 && low >= 10)
            printf("%c%c", high - 10 + 'A', low - 10 + 'A');
        else if (high >= 10)
            printf("%c%d", high - 10 + 'A', low);
        else if (low >= 10)
            printf("%d%c", high, low - 10 + 'A');
        else
            printf("%d%d", high, low);
    }

}

int main() {
    int r, g, b;
    scanf("%d %d %d", &r, &g, &b);
    printf("#");
    change(r);
    change(g);
    change(b);
    return 0;
}

优雅的代码

cout << get(a[i] / 13) << get(a[i] % 13);
如果只有一位的情况下a[i] / 13其实是等于0的,只要这边输出0就好了,我没想到这一点

#include <iostream>

using namespace std;

char get(int x) {
    if (x <= 9) return '0' + x;
    return 'A' + x - 10;
}

int main() {
    int a[3];
    for (int i = 0; i < 3; ++i)cin >> a[i];
    cout << '#';
    for (int i = 0; i < 3; ++i) {
        cout << get(a[i] / 13) << get(a[i] % 13);
    }
    return 0;
}

1100 Mars Numbers

AcWing链接
 PAT链接

英语单词

mutual translation 相互转换
either or 要么要么
corresponding 相应的相关的对应的

解析
做这道题的时候碰到了很多小坑

用getline 获取一行，然后整行进行解析
如果带有数字，那么将数字转换为火星数字
如果是字符串那么将字符串转换为整型数字
由于火星文只有两位所以数字转火星数字，只要将数字除以13和数字mod13进行操作
字符串需要对一位和两位的情况进行讨论

tips: stringstream的用处

C++ stringstream之妙用
 stringstream用法
本题中使用stringstream ssin(data);获取输入的string类型地球字/火星字
自动根据空格分割他们并输出到指定的类型num2(string)中
或转换为int形变量num
我的答案

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;
string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; // 个位
string b[12] = {"tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; // 高位
int get_num(string num) {
    for (int i = 0; i < 13; ++i) {
        if (a[i] == num) return i;
    }
    for (int i = 0; i < 12; ++i) {
        if (b[i] == num) return (i + 1) * 13;
    }
}

int main() {

    // 29 = 2 3  elo nov = 8 11 = 8*13+11 = 115
    int n;
    cin >> n;
    getchar();
    for (int i = 0; i < n; ++i) {
        string data;
        getline(cin, data);
        stringstream ssin(data);
        if (data[0] <= '9') {
            // 输入的是地球的数字, 需要转换为13进制 29 => 2 3  => hel mar
            int num;
            ssin >> num;
            if (num < 13) {
                cout << a[num] << endl;
            } else {
                // 15 => 1 2 => 15/13 =1 15 %13 = 2
                cout << b[num / 13 - 1];
                if (num % 13 != 0)
                    cout << " " << a[num % 13];
                cout << endl;
            }
        } else {
            // 输入的是火星的数字,需要先转换为13进制再转为10进制 elo nov => 8 11 => 8*13 + 11 = 115
            string num2;
            int res = 0;
            while (ssin >> num2) {
                res += get_num(num2);
            }
            cout << res << endl;
        }
    }
    return 0;
}

AcWing课程的答案

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;

char names[][5] = {
        "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec",
        "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"
};

int get(string word) {
    for (int i = 0; i < 25; ++i) {
        if (names[i] == word) {
            if (i < 13) return i;
            return ((i + 1) % 13) * 13;
        }
    }
}

int main() {
    int n;
    cin >> n;
    getchar();
    while (n--) {
        string line;
        getline(cin, line);
        stringstream ssin(line);
        if (line[0] <= '9') {
            int v;
            ssin >> v;
            if (v < 13) cout << names[v] << endl;
            else {
                cout << names[12 + v / 13];
                if (v % 13 == 0) cout << endl;
                else cout << " " << names[v % 13] << endl;
            }
        } else {
            int res = 0;
            string word;
            while (ssin >> word) res += get(word);
            cout << res << endl;
        }
    }
    return 0;
}