PAT (Advanced Level) Practice 1081~1100_综合

文章目录

1081 Rational Sum
1082
1083
1084
1085
1086
1087
1088 Rational Arithmetic
1089
1090
1091
1092
1093 Count PAT's
1094
1095
1096
1097 Deduplication on a Linked List
1098
1099
1100 Mars Numbers

1081 Rational Sum

一道比较简单的考查分数运算的题目。
注意点：

负数不用特殊处理，只需将分子变为负数即可；
用 long long 来定义所以的整数类型；
每一步加法做完之后要约分；
要计算分子分母绝对值的最大公约数；
在 PAT 里，abs 函数不在头文件 cmath里，而是 algorithm 里。

关于分数运算的知识，可以学习 PTA 算法笔记重点总结（一）的第25点，写的很易懂详细。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll; // 记 long long 为 llll gcd(ll a, ll b) // 求 a 与 b 的最大公约数
{
    return b == 0 ? a : gcd(b, a % b);
}struct Fraction // 分数的结构体
{
    ll up, down; //up 为分子，down 为分母
};Fraction reduction(Fraction result) // 该函数实现分数的化简
{
    if (result.down < 0) // 分子为负数，分子分母变相反数{
    result.up = -result.up;result.down = -result.down;}else if (result.up == 0) // 分子为0，分母变1result.down = 1;else // 约分{
    int d = gcd(abs(result.up), abs(result.down)); // 求分子分母的最大公约数result.up /= d; // 约去最大公约数result.down /= d;}return result;
}Fraction add(Fraction f1, Fraction f2) // 分数加法
{
    Fraction result;result.up = f1.up * f2.down + f2.up * f1.down; // 分数和的分子result.down = f1.down * f2.down; // 分数和的分母return reduction(result); // 返回化简后的分数
}void showResult(Fraction r) // 输出分数 r
{
    r = reduction(r); // 化简if (r.down == 1) // 整数printf("%lld\n", r.up);else if (abs(r.up) > r.down) // 假分数printf("%lld %lld/%lld\n", r.up / r.down, abs(r.up) % r.down, r.down);elseprintf("%lld/%lld\n", r.up, r.down); // 真分数
}int main()
{
    int n;scanf("%d", &n);Fraction temp, sum;sum.up = 0, sum.down = 1; // 初始化for (int i = 0; i < n; ++i){
    scanf("%lld/%lld", &temp.up, &temp.down);sum = add(sum, temp); // sum 加上 temp}showResult(sum); // 输出结果return 0;
}

1082

1083

1084

1085

1086

1087

1088 Rational Arithmetic

题意：
给出两个分数（可能有负分数），求它们的加法、减法、乘法、除法的计算式。如果是假分数，则按带分数的形式输出；如果是整数，则输出整数；否则，输出真分数；如果做除法时除数为0，那么应当输出 “Inf"。

思路：
这是一道比较常规的分数四则运算的题目，只不过加减乘除都有所涉及，所以代码量稍微大一点。详情可以参考PTA 算法笔记重点总结（一）的第23、25点内容。

注意点：

负数无需特殊处理，只需当作分子为负数的分数即可。
分母相乘时，最大可以达到 long long，因此要用 long long 定义分子分母。
计算最大公约数时，要注意是计算分子分母绝对值的公约数，否则下面的数据会错误。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;ll gcd(ll a, ll b)
{
     // 求 a 与 b 的最大公约数return !b ? a : gcd(b, a % b);
}struct Fraction // 分数结构体
{
    ll up, down; // 分别表示分子和分母
}a, b;Fraction reduction(Fraction result) // 化简
{
    if (result.down < 0) // 分子为负，分子分母变相反数{
    result.up = -result.up;result.down = -result.down;}if (result.up == 0) // 分子为0，分母变1result.down = 1;else // 分子不为0，约分{
    int d = gcd(abs(result.up), abs(result.down)); // 求分子分母的最大公约数result.up /= d; // 约去最大公约数result.down /= d;}return result;
}Fraction add(Fraction f1, Fraction f2) // 分数加法
{
    Fraction result;result.up = f1.up * f2.down + f2.up * f1.down;result.down = f1.down * f2.down;return reduction(result);
}Fraction minu(Fraction f1, Fraction f2) // 分数减法
{
    Fraction result;result.up = f1.up * f2.down - f2.up * f1.down;result.down = f1.down * f2.down;return reduction(result);
}Fraction multiply(Fraction f1, Fraction f2) // 分数乘法
{
    Fraction result;result.up = f1.up * f2.up;result.down = f1.down * f2.down;return reduction(result);
}Fraction divide(Fraction f1, Fraction f2) // 分数除法
{
    Fraction result;result.up = f1.up * f2.down;result.down = f1.down * f2.up;return reduction(result);
}void showResult(Fraction r)
{
    r = reduction(r); // 化简if (r.up < 0) printf("(");if (r.down == 1) // 整数printf("%lld", r.up);else if (abs(r.up) > r.down) // 假分数printf("%lld %lld/%lld", r.up / r.down, abs(r.up) % r.down, r.down);elseprintf("%lld/%lld", r.up, r.down); // 真分数if (r.up < 0) printf(")");
}int main()
{
    scanf("%lld/%lld %lld/%lld", &a.up, &a.down, &b.up, &b.down);// 加法showResult(a);printf(" + ");showResult(b);printf(" = ");showResult(add(a, b));printf("\n");// 减法showResult(a);printf(" - ");showResult(b);printf(" = ");showResult(minu(a, b));printf("\n");// 乘法showResult(a);printf(" * ");showResult(b);printf(" = ");showResult(multiply(a, b));printf("\n");// 除法showResult(a);printf(" / ");showResult(b);printf(" = ");if (b.up == 0) printf("Inf");else showResult(divide(a, b));printf("\n");return 0;
}

1089

1090

1091

1092

1093 Count PAT’s

思路：
直接由 P 或 T来计算形成的 PAT 的个数是很复杂的。如果我们换个思路，对于每一个 A 来说，它能形成多少个 PAT 取决于左右 P 和 T 个数的乘积。我们只需再将所有乘积求和，问题就迎刃而解了。那么剩下的问题就是如何知道，每一个 A 左右 P 和 T 的个数了。不妨这样做，我们设置一个数组 leftNumP，它存储着字符串中每一位字符左边 P 的个数，所以要先将它初始化为0。然后我们枚举每一个字符，先让它的值继承前一位的值，当它恰好又是字符 P 时，我们就将它的值加一，枚举完所有的字符后，它们左边的 P 的个数也就记录下来了。举个例子，对于每个字符来说，由于它继承了前一位的值 x，就表明它的左边有 x 个 P。如果它本身也是 P，那么就让它自身的加一即为 x + 1。对于下一位字符来说，它继承了前一位的值，于是变成了 x + 1，说明它左边有 x + 1 个 P，这与前面的论述并不矛盾。

然后我们就从末尾字符开始枚举，用 ans 表示答案，rightNumT 表示每一位字符右边的 T 个数，这时候就不需要数组了，直接记录即可。枚举到字符 T，rightNumT 就加一，枚举到 A，就更新 ans 的值即可。

#include <iostream>
#include <cstring>
using namespace std;const int maxn = 100010;
const int MOD = 1000000007;int main()
{
    char str[maxn];cin >> str;int len = strlen(str);int leftNumP[maxn] = {
    0}; // 记录字符串中每一位字符左边字符P的个数for (int i = 0; i < len; ++i){
    if (i > 0)leftNumP[i] = leftNumP[i - 1]; // 继承上一位的结果if (str[i] == 'P')++leftNumP[i];}int ans = 0, rightNumT = 0; // ans为答案，rightNumT记录右边T的个数for (int i = len - 1; i >= 0; --i){
    if (str[i] == 'T')++rightNumT;if (str[i] == 'A')ans = (ans + leftNumP[i] * rightNumT) % MOD;}cout << ans << endl;return 0;
}

1094

1095

1096

1097 Deduplication on a Linked List

题意：
给出单链表的头结点地址、结点总数 N。接下来 N 行条数据，每行给出结点的地址、数据以及下一个结点的地址。要求只保留绝对值第一次出现的结点，而去掉链表中绝对值重复的结点。最后按照地址、数据以及下一个结点的地址输出非重值链表，以及重值结点。

思路：
首先给出了结点的地址值且范围较小，故可以考虑用静态链表来处理。我的就基本思路就是用一个 bool 数组 check 来记录结点值的绝对值是否出现过。然后单链表将整个链表拆分成两条链表：重值链表和非重值链表。将绝对值第一次出现的链表链接到重值链表上，将绝对值已经出现过的连接到非重值链表上。最后按照顺序分别输出两条链表上的结点。

定义 bool 数组。 check 记录结点绝对值是否出现过，初始化为 false；
输入结点的数据。用 first 和 second 分别表示重值和非重值链表的第一个结点的地址，q 指向枚举当中的结点，p 指向它的前驱，r 指向非重值链表的尾结点，初值为-1。
枚举单链表。根据 check[x] 的值来判断是否为重值结点，枚举的过程手动模拟一下就能懂。cnt 用来表明有多少个重值结点，当 cnt == 1 时表明是重值链表的第一个结点，此时要用 second 记录下该结点的地址。枚举完后要令非重值链表的结尾指向-1。
输出链表。先后输出重值链表和非重值链表上的结点信息。当 second != first 时说明存在非重值链表，此时还需要输出非重值链表。

注意点：

可以直接使用 %05d 的输出格式，以在不足5位时在高位补0。但是要注意-1不能使用 %05d 输出，否则会输出 -0001（而不是-1或者-00001)，因此必须要留意-1的输出。
题目可能会有无效结点，即不在题目给出的首地址开始的链表上。
r 的值一定要记得初始化，否则链表只存在一个结点时，语句 if (r != -1) node[r].next = -1; // 重值链表结尾置-1会出现数组越界的情况。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;struct NODE{
     // 结点结构体int data; // 数据域int next; // next 指向下一个结点
} node[100010];bool check[10110] = {
    false}; // check[x] == 1 表明该绝对值出现过void print(int index) // 从地址 index 开始输出链表
{
    while (index != -1){
    if (node[index].next == -1) // next 域为-1的要特别输出printf("%05d %d -1\n", index, node[index].data);elseprintf("%05d %d %05d\n", index, node[index].data, node[index].next);index = node[index].next;}
}int main()
{
    int first, n, addr; // 首结点的地址、结点总数scanf("%d%d", &first, &n);for (int i = 0; i < n; ++i){
    scanf("%d", &addr); // 输入结点的地址scanf("%d%d", &node[addr].data, &node[addr].next);}int second = first, p = first, q = node[p].next, r = -1, cnt = 0;check[abs(node[p].data)] = true; // 记录第一个结点的绝对值while (q != -1) // q 始终为 p 的后继{
    if (check[abs(node[q].data)]) // 若结点 q 的绝对值出现过{
    ++cnt; // 重值结点计数+1node[p].next = node[q].next; // 从非重值链表上去除结点 qif (cnt == 1) // 计数值为1，说明 q 为重值链表的第一个结点second = r = q; // second, r 分别为重值链表的第一个和最后一个结点else // 计数值不为1{
    node[r].next = q; // q 加入重值链表尾部r = q; // r 指向新的重值链表尾结点}q = node[p].next; // q 指向 p 的后继}else // 结点 q 的绝对值没出现过{
    check[abs(node[q].data)] = true; // 记录 q 的绝对值p = q; // p, q 均往后挪一位q = node[p].next;}}if (r != -1)node[r].next = -1; // 重值链表结尾置-1print(first); // 输出非重值链表if (second != first) // 如果存在重值链表，则输出print(second);return 0;
}

1098

1099

1100 Mars Numbers

题意：
该题就是十进制数和十三进制数的转换，火星文即为十三进制下的数，只不过题目要求用字符串来表示每一位，其实就类似于十六进制的 ABCDEF。

思路：
题目中提到，不论是十进制数还是火星文的范围都在 [0, 169)，因为13的平方是169，而十三进制下的169为100，因此按照题中的火星文规则，比100小的十三进制数都只有两个字符串位。从而可以定义两个字符串数组 low 和 high，分别表示低位字符串和高位字符串。数据范围比较小，可以在程序开始的时候就直接将此范围内十进制数对应的火星文和火星文对应的十进制数全部求出来，输入数据后直接查询即可。

numToStr 即为字符串数组，下标为十进制数，其元素为十进制数对应的火星文。strToNum 为 map 类型的数据，实现火星文到十进制数的映射。在程序开始时首先预处理所有的映射，并存储到 numToStr 和 strToNum 中，也即“打表”。但是对于火星文有两种特殊情况需要单独处理，这两种情况不论是高位还是低位的范围都是 [0, 12]。

第一种情况是高位为0，低位不为0，此时它对应的火星文就是 “tret” ~ “dec”。
第二种情况是高位不为0，低位为0，对应到十进制数下时，它们皆为13的倍数（自己验证一下即可），此时它对应的火星文就是 “tret” ~ “jou”。
因此建立这两种情况映射的代码可以如下写：

for (int i = 0; i < 13; ++i)
{
    // 第一种情况numToStr[i] = low[i]; // 十进制数映射低位火星文strToNum[low[i]] = i; // 低位火星文映射十进制数// 第二种情况numToStr[i * 13] = high[i]; // 13的倍数映射高位火星文strToNum[high[i]] = i * 13; // 高位火星文映射13的倍数
}

其他情况的映射如下写：

for (int i = 1; i < 13; ++i)
{
    for (int j = 1; j < 13; ++j){
    string str = high[i] + " " + low[j]; // 火星文numToStr[i * 13 + j] = str; // 数字转火星文strToNum[str] = i * 13 + j; // 火星文转数字}
}

注意点：

用 getline() 来读取一行字符，详情可见PTA 算法笔记重点总结（一）中的第十点。由于 getline() 以回车键作为字符串输入结束的标志，因为 n 输入完后要记得用 getchar() 读取回车。
字符串转数字的做法要记住，括号最好加上，以免出问题。

#include <iostream>
#include <string>
#include <map>
using namespace std;const int maxl = 170; // 字符串最大长度
// [0, 12] 的火星文
string low[13] = {
    "tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
// 13的 [0, 12] 倍的火星文
string high[13] = {
    "tret", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
string numToStr[170]; // 数字转火星文
map<string, int> strToNum; // 数字转火星文void init()
{
    for (int i = 0; i < 13; ++i){
    // 第一种情况numToStr[i] = low[i]; // 十进制数映射低位火星文strToNum[low[i]] = i; // 低位火星文映射十进制数// 第二种情况numToStr[i * 13] = high[i]; // 13的倍数映射高位火星文strToNum[high[i]] = i * 13; // 高位火星文映射13的倍数}for (int i = 1; i < 13; ++i){
    for (int j = 1; j < 13; ++j){
    string str = high[i] + " " + low[j]; // 火星文numToStr[i * 13 + j] = str; // 数字转火星文strToNum[str] = i * 13 + j; // 火星文转数字}}
}int main()
{
    init();int n;cin >> n; // n 行整数getchar(); // 读取输入 n 后的回车，防止被 getling 读取while (n--){
    string str;getline(cin, str); // 查询的数if (str[0] >= '0' && str[0] <= '9') // 如果是数字{
    int num = 0; // 字符串转成数字for (int i = 0; i < str.length(); ++i)num = num * 10 + (str[i] - '0');cout << numToStr[num] << endl; // 直接查表}else // 如果是火星文cout << strToNum[str] << endl;}
}

一定要自己写一遍哦~~~