PAT考试真题解析
[1136] A Delayed Palindrome (20)
字符串
题目
Consider a positive integer $N$ written in standard notation with $k+1$ digits $a_i$ as $a_k$ $⋯$ $a_1$ $a_0$ with $0≤a_i<10$ for all $i$ and $a_k>0$. Then $N$ is palindromic if and only if $a_i=a_{k−i}$ for all $i$. Zero is written 0 and is also palindromic by definition.
Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. Such number is called a delayed palindrome.
Given any positive integer, you are supposed to find its paired palindromic number.
Input Specification:
Each input file contains one test case which gives a positive integer no more than 1000 digits.
Output Specification:
For each test case, print line by line the process of finding the palindromic number. The format of each line is the following:
1 | A + B = C |
where A is the original number, B is the reversed A, and C is their sum. A starts being the input number, and this process ends until C becomes a palindromic number – in this case we print in the last line C is a palindromic number.; or if a palindromic number cannot be found in 10 iterations, print Not found in 10 iterations. instead.
注意点与解析
- 水题
代码
1 | bool isPalindrome(string s) { |
[1137] Final Grading (25)
哈希、排序
题目
For a student taking the online course “Data Structures” on China University MOOC, to be qualified for a certificate, he/she must first obtain no less than 200 points from the online programming assignments, and then receive a final grade no less than 60 out of 100. The final grade is calculated by $G=(G_{mid−term}× 0.4 +G_{final} × 0.6)$ if $G_{mid−term}>G_{final}$, or $G_{final}$ will be taken as the final grade G. Here $G_{mid−term}$ and $G_{final}$ are the student’s scores of the mid-term and the final exams, respectively.
The problem is that different exams have different grading sheets. Your job is to write a program to merge all the grading sheets into one.
Input Specification:
Each input file contains one test case. For each case, the first line gives three positive integers: P , the number of students having done the online programming assignments; M, the number of students on the mid-term list; and N, the number of students on the final exam list. All the numbers are no more than 10,000.
Then three blocks follow. The first block contains P online programming scores $G_p$’s; the second one contains M mid-term scores $G_{mid−term}$’s; and the last one contains N final exam scores $G_{final}$’s. Each score occupies a line with the format: StudentID Score, where StudentID is a string of no more than 20 English letters and digits, and Score is a nonnegative integer (the maximum score of the online programming is 900, and that of the mid-term and final exams is 100).
Output Specification:
For each case, print the list of students who are qualified for certificates. Each student occupies a line with the format:
StudentID $G_p$ $G_{mid−term}$ $G_{final}$ $G$
If some score does not exist, output $−1$ instead. The output must be sorted in descending order of their final grades ($G$ must be rounded up to an integer). If there is a tie, output in ascending order of their StudentID‘s. It is guaranteed that the StudentID‘s are all distinct, and there is at least one qullified student.
注意点与解析
- map使用
map[key]方式查找失败会自动插入一个值，初始值为0，不能这么用，因为可能有人期中考考了0分。要使用map.find()的方法
代码
1 | unordered_map<string, int> online, mid, last, name; |
[1138] Postorder Traversal (25)
树的遍历
题目
Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the first number of the postorder traversal sequence of the corresponding binary tree.
代码
1 | vector<int> pre, in; |
[1139] First Contact (30)
图模拟
题目
Unlike in nowadays, the way that boys and girls expressing their feelings of love was quite subtle in the early years. When a boy A had a crush on a girl B, he would usually not contact her directly in the first place. Instead, he might ask another boy C, one of his close friends, to ask another girl D, who was a friend of both B and C, to send a message to B – quite a long shot, isn’t it? Girls would do analogously.
Here given a network of friendship relations, you are supposed to help a boy or a girl to list all their friends who can possibly help them making the first contact.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (1 < N ≤ 300) and M, being the total number of people and the number of friendship relations, respectively. Then M lines follow, each gives a pair of friends. Here a person is represented by a 4-digit ID. To tell their genders, we use a negative sign to represent girls.
After the relations, a positive integer K (≤ 100) is given, which is the number of queries. Then K lines of queries follow, each gives a pair of lovers, separated by a space. It is assumed that the first one is having a crush on the second one.
Output Specification:
For each query, first print in a line the number of different pairs of friends they can find to help them, then in each line print the IDs of a pair of friends.
If the lovers A and B are of opposite genders, you must first print the friend of A who is of the same gender of A, then the friend of B, who is of the same gender of B. If they are of the same gender, then both friends must be in the same gender as theirs. It is guaranteed that each person has only one gender.
The friends must be printed in non-decreasing order of the first IDs, and for the same first ones, in increasing order of the seconds ones.
注意点与解析
- 使⽤
unordered_map<int, bool> arr替代⼆维数组可避免内存超限 - 对于⼀对想要在⼀起的A和B，他们需要先找A的所有同性朋友C，再找B的所有同性朋友D，当C和D两⼈是朋友的时候则可以输出C和D
- A在寻找同性朋友时，需要避免找到他想要的伴侣B，所以当当前朋友就是B或者B的同性朋友就是A时舍弃该结果
- 如果⽤int接收⼀对朋友，-0000和0000对于int来说都是0，将⽆法得知这个⼈的性别，也就会影响他找他的同性朋友的那个步骤，所以考虑⽤字符串接收，因为题⽬中已经表示会以符号位加四位的⽅式给出输⼊，所以只要判断字符串是否⼤⼩相等，如果⼤⼩相等说明这两个⼈是同性
- 结果数组因为必须按照第⼀个⼈的编号从⼩到⼤排序（当第⼀个相等时按照第⼆个⼈编号的从⼩到⼤排序），所以要⽤sort对ans数组排序后再输出结果
代码
1 | unordered_map<int, bool> arr; |