PAT (Advanced Level) Practice 1021~1040

1021

---

1022 Digital Library

题意：
给出 N 本书的编号、书名、作者、关键词（可能有多个）、出版社及出版年份，并给出M个查询，每个查询给出书名、作者、关键词（单个）、出版社及出版年份中的一个，要求输出满足该给出信息的所有书的编号。

思路：

1. 利用 map<string, set< int >> mp 的写法来建立字符串 string 与有序整数集合 set 之间的映射。mp[string] 下记录的是所有与该 string 有关的书的 id；
2. 要考虑遍历的问题，即当需要输出所有 string 下的 id 时，如何编写代码？事实上，mp[string] 即为一个 set< int >，这样就转变为遍历容器 set 中的元素，因此可以使用迭代器进行遍历；
3. 题目要求按编号从小到大顺序输出。这恰好可以用 map 的自动排序来解决，即分别建立书名、作者、关键词、出版社及出版年份与编号的 map 映射，当需要查询时即可按第二步的方法很方便地获取需要的书的编号。

值得一提的是关键词的提取。由于题目中的每本书都可能有多个关键词，因此需要将这些关键词分离开来。一个比较好的办法是使用 cin 来读入单个关键词，然后用 getchar() 接收紧跟在这个关键词后面的字符：如果是空格，则继续读入；如果是换行符，则说明关键词的输入结束了。这样做的原因是 cin 读入字符串是以空格或换行为结束标志的。

注意点：

• 如果单独把查询操作提炼成一个函数，那么一定要对参数使用引用，否则最后一组数据会超时。由此可见，字符串以及 map 的参数传递速度较慢，如果需要作为函数的参数的话，需要尽可能加上引用。
• 在 scanf 或者 cin 输入书的编号 id 后，必须用 getchar 接收掉后面的换行符，否则 getline 会换行读入（将换行当成了一组输入）。

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;//5个map变量分别建立书名、作者、关键词、出版社及出版年份与 id 的映射关系
map<string, set<int> > mpTitle, mpAuthor, mpKey, mpPub, mpYear;void query(map<string, set<int> >& mp, string& str)//在mp中查找str
{
    if(mp.find(str) == mp.end())printf("Not Found\n"); // 找不到else //找到strfor(set<int>::iterator it = mp[str].begin(); it != mp[str].end (); ++it)printf("%07d\n", *it); // 输出 str 对应的所有 id
}int main()
{
    int n, m, id, type;string title, author, key, pub, year;scanf("%d", &n); // 书的数目for(int i = 0; i < n; ++i){
    scanf("%d", &id); // idchar c = getchar(); // 接收 id 后面的换行getline(cin, title); // 读入书名 titlempTitle[title].insert(id); // 把 id 加入 title 对应的集合中getline(cin, author); // 读入作者 authormpAuthor[author].insert(id); // 把 id 加入 author 对应的集合中while(cin >> key) // 每次读入单个关键词 key{
    mpKey[key].insert(id); // 把 id 加入 key 对应的集合中c = getchar(); // 接收关键词 key 之后的字符if(c == '\n') break; // 如果是换行，说明关键词输入结束}getline(cin, pub); // 输入出版社 pubmpPub[pub].insert(id); // 把 id 加入 pub 对应的集合中getline(cin, year); // 输入年份 yearmpYear[year].insert(id); // 把 id 加入 year 对应的集合中}string temp;scanf("%d", &m); // 查询次数for(int i = 0; i < m; ++i){
    scanf("%d: ", &type); // 查询类型getline(cin, temp); // 欲查询的字符串cout << type << ": " << temp << endl; // 输出类型和该字符串if(type == 1) query (mpTitle, temp); // 查询书名对应的所有 idelse if(type == 2) query(mpAuthor, temp); // 查询作者对应的所有 idelse if(type == 3) query(mpKey, temp); //查询关键词对应的所有 idelse if(type == 4)query(mpPub, temp); // 查询出版社对应的所有 idelse query(mpYear, temp); //查询出版年份对应的所有id}return 0;
}

---

1023 Have Fun with Numbers

题意：
给出一个长度不超过20的大整数，问这个整数两倍后的数位是否为原数数位的一个排列。

思路：
基本想法是读取大整数的时候记录各个数位出现的次数，乘以2后再减去相应的次数，如果最后得到的数组 table 所有元素值都为0说明 double 后的大整数是原数数位的一个排列。

1. 按字符串方式读入整数，并且逆序存入数组 num 中，这样数组 num 的低位（下标更小的位置）存放的就是大整数的低位。存入的过程用数组 table 记录原大整数中每个数出现的次数。
2. 对大整数进行 double 操作，由于是逆序存放，故下标从0开始逐位乘2即可。每一位乘完得到新的数，根据这个数将数组 table 相应下标的值减1。乘完后，若依然存在数位，表明多出现了一个数，此时数组 table 相应位应该执行+1操作，同时 double 后的大整数数位+1。
3. 最后遍历数组 table，若存在不为0的值，输出“No”，否则输出“Yes”。

注意点：

• 对于大整数的概念可以参考文章PTA 算法笔记重点总结（二）第29点。
• 一定要注意，大整数进行加法或乘法操作后，数位有可能+1，而这个进位在最后需要输出，否则2、7测试点会答案错误。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;int main()
{
    int table[10] = {
    0}, num[25]; // table 记录每个数出现的次数string str;cin >> str; // 数字字符串int len = str.length(); // 大整数的长度for (int i = len - 1; i >= 0; --i){
     // 将字符串逆序存入大整数数组num[i] = str[len - i - 1] - '0';++table[num[i]]; // 计数+1}int temp, carry = 0, flag = 0;for (int i = 0; i < len; ++i){
    temp = num[i] * 2 + carry; // 中间值num[i] = temp % 10; // 取余，作为新的数位carry = temp / 10; // 进位--table[num[i]]; // 计数-1}if (carry != 0) // 进位不为0{
    ++table[carry]; // 计数+1num[len++] = carry; // 大整数数位+1}for (int i = 0; i < 10; ++i)if (table[i] != 0)flag = 1; // flag = 1 表示存在计数不一致的数位if (flag == 1) cout << "No\n";else cout << "Yes\n";for (int i = len - 1; i >= 0; --i) // 输出 double 后的大整数cout << num[i];return 0;
}

---

1024 Palindromic Number

题意：
定义一种操作：让一个整数加上这个整数逆序的整数。现在给出一个正整数和最多操作次数，问在限定的操作次数内能是否能得到回文数。如果能得到，则输出那个回文数，并输出操作的次数；否则，输出最后一次操作得到的数字以及操作次数。

思路：
由于存在多次逆序相加的可能，即使用 long long 也有可能溢出，因此采用数组来存储每个数位，即大整数的思想。

1. 用数组 before 和数组 after 分别表示逆置前和逆置后的大整数，以字符串形式读入整数，然后存入数组 before 中。
2. step 记录操作次数，当 step >= k 时跳出循环。每次循环首先判断 before 是否为回文数，如果是就结束循环。
3. 如果不是，则将 before 逆序存入 after 中，然后执行操作，将两者逐位相加。最后若进位不为0，还需将其添加进 before 中。step + 1，进入下次循环，重复2的步骤。

注意点：

• 对于大整数的概念可以参考文章PTA 算法笔记重点总结（二）第29点。
• 最后输出 before 时记得逆序输出。如果是回文数则从下标0开始输出即可，如果最终结果不是回文数则需要从数组尾部往前输出。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;const int maxl = 1010;bool isPal(int a[], int n) // 判断数组 a 中存储的大整数是否为回文数，n 为数组长度
{
    for (int i = 0; i <= n / 2; ++i)if (a[i] != a[n - i - 1])return false;return true;
}int main()
{
    int k, before[maxl], after[maxl]; // 分别表示逆置前的大整数和逆置后的大整数string str;cin >> str >> k; // 读取大整数字符串和最多相加次数int len = str.length(), step = 0;for (int i = 0; i < len; ++i) // 将字符串的数存入原大整数数组before[i] = str[i] - '0';while (step < k) // 当步数大于 k 时结束循环{
    if (isPal(before, len))break;for (int i = len - 1; i >= 0; --i) // 将数组 before 逆序存入数组 afterafter[i] = before[len - i - 1];int temp, carry = 0;for (int i = 0; i < len; ++i) // 用数组 before 存储相加后的结果{
    temp = before[i] + after[i] + carry; // 同位相加before[i] = temp % 10; // 余数carry = temp / 10; // 进位}if (carry != 0)before[len++] = carry;++step;}for (int i = len - 1; i >= 0; --i) // 要从高位开始输出cout << before[i];cout << "\n" << step;return 0;
}

---

1025 PAT Ranking

简单的排序，没什么需要记录的。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;struct student
{
    char number[15]; // 准考证号int score; // 分数int location; // 考场号int local_rank; // 考场内排名
} stu[30010]; // 最多三万名学生bool cmp(student a, student b) // 比较函数，分数降序排列，分数相等时准考证号升序排列
{
    if (a.score != b.score)return a.score > b.score;elsereturn strcmp(a.number, b.number) < 0;
}int main()
{
    int N, K, num = 0; // num为总考生数cin >> N;for (int i = 1; i <= N; ++i){
    cin >> K; // 该考场内人数for (int j = 0; j < K; ++j) // 输入k个受测者信息{
    cin >> stu[num].number >> stu[num].score; // 输入注册号和分数stu[num++].location = i; // 记录考场号，同时考生数+1}sort(stu + num - K, stu + num, cmp); // 将该考场的考生排序stu[num - K].local_rank = 1; // 将该考场第一名的考场排名记为1for (int j = num - K + 1; j < num; ++j){
    if (stu[j].score == stu[j - 1].score) // 考场stu[j].local_rank = stu[j - 1].local_rank;elsestu[j].local_rank = j + 1 - num + K; // 此处要注意，如果两个人分数相等，排在他们后面的考生排名应为 + 2}}sort(stu, stu + num, cmp); // 所有数据输入完后重新排列cout << num << endl; // 输出总考生数int r = 1;for (int i = 0; i < num; ++i){
    if (i > 0 && stu[i].score != stu[i - 1].score)r = i + 1;cout << stu[i].number << ' ' << r << ' ' << stu[i].location << ' ' << stu[i].local_rank << endl;}return 0;
}

---

1026

---

1027

---

1028

---

1029

---

1030

1031

---

1032 Sharing

题意：
第一行给出两条链表（也即两个单词）的首地址以及所有结点（每个结点代表一个字母）的个数 N。接下来给出 N 行结点的信息，包括首地址、其中的字母以及后继结点的地址。要求两条链表的首个共用结点的地址。如果两条链表没有共用结点，则输出-1。要注意的是，两个链表中所有的结点是打乱顺序给出的。

思路：

1. 地址范围比较小，定义静态链表即可，其中结点性质由 bool 型变量 flag 定义，表示结点是否在某条链表中出现过。
2. 由题目给出的第一条链表的首地址 s1 遍历整条链表，将遍历到的结点 flag 标记为 true，表示其在第一条链表上出现过。
3. 枚举第二条链表，当出现第一个 flag == true 的结点，说明是第一条链表中出现过的结果，即为两条链表的第一个共用结点。如果第二条链表枚举完仍然没有发现共用结点，则输出-1。

注意点：

• 使用 %05d 格式输出地址，可以使不足5位的整数的高位补0。
• 使用 scanf 可以更方便的处理输入数据之间的空格。

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;const int maxn = 100010;struct Node
{
    char data; // 数据域int next; // 指针域bool flag; // 结点是否在第一条链表中出现
} node[maxn];int main()
{
    for (int i = 0; i < maxn; ++i)node[i].flag = false;int s1, s2, n; // s1与s2分别代表两条链表的首地址cin >> s1 >> s2 >> n;int address, next; // 结点地址与后继地址char data; // 数据while (n--){
    cin >> address >> data >> next;node[address].data = data;node[address].next = next;}int p;for (p = s1; p != -1; p = node[p].next)node[p].flag = true; // 枚举第一条链表的所有结点，令其出现次数为1for (p = s2; p != -1; p = node[p].next)if (node[p].flag == true) // 找到第一个在第一条链表中出现的结点break;if (p != -1) // 如果第二条链表还没有到达结尾，说明找到了共用结点cout << setfill('0') << setw(5) << setiosflags(ios::right) << p << endl;elsecout << "-1\n";return 0;
}

---

1033

---

1034

---

1035

---

1036

---

1037

---

1038

---

1039

---

1040

---

一定要自己写一遍哦~~