1145. Hashing – Average Search Time (25) – 甲级

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table first. Then try to find another sequence of integer keys from the table and output the average search time (the number of comparisons made to find whether or not the key is in the table). The hash function is defined to be “H(key) = key % TSize” where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize, N, and M, which are the user-defined table size, the number of input numbers, and the number of keys to be found, respectively. All the three numbers are no more than 104. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space and are no more than 105.
Output Specification:
For each test case, in case it is impossible to insert some number, print in a line “X cannot be inserted.” where X is the input number. Finally print in a line the average search time for all the M keys, accurate up to 1 decimal place.
Sample Input:
4 5 4
10 6 4 15 11
11 4 15 2
Sample Output:
15 cannot be inserted.
2.8

题目大意:给定一个序列,用平方探测法解决哈希冲突,然后给出m个数字,如果这个数字不能够被插入就输出”X cannot be inserted.”,然后输出这m个数字的平均查找时间
分析:先找到大于tsize的最小的素数为真正的tsize,然后建立一个tsize长度的数组。首先用平方探测法插入数字a,每次pos = (a + j * j) % tsize,j是从0~tsize-1的数字,如果当前位置可以插入就将a赋值给v[pos],如果一次都没有能够插入成功就输出”X cannot be inserted.”。其次计算平均查找时间,一开始cnt=1表示查找一次,每次计算pos = (a + j * j) % tsize,如果v[pos]处正是a则查找到了,所以退出循环,如果v[pos]处不存在数字表示没查找到,那么也要退出循环,最后将cnt累加到ans里表示总的查找时间,最后除以m得到平均查找时间然后输出~

 

PAT 1147. Heaps (30) – 甲级

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))
Your job is to tell if a given complete binary tree is a heap.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 100), the number of trees to be tested; and N (1 < N <= 1000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.
Output Specification:
For each given tree, print in a line “Max Heap” if it is a max heap, or “Min Heap” for a min heap, or “Not Heap” if it is not a heap at all. Then in the next line print the trees postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

Sample Input:
3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56
Sample Output:
Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10

题目大意:给一个树的层序遍历,判断它是不是堆,是大顶堆还是小顶堆。输出这个树的后序遍历~
分析:30分大题,28行代码,一行代码一分……((⊙o⊙)嗯) // 我为什么这么机智可爱又伶俐?
首先根据v[0]和v[1]的大小比较判断可能是大顶还是小顶,分别赋值flag为1和-1,先根据层序遍历,从0~(n-1)/2【所有有孩子的结点】判断他们的孩子是不是满足flag的要求,如果有一个结点不满足,那就将flag=0表示这不是一个堆。根据flag输出是否是堆,大顶堆还是小顶堆,然后后序遍历,根据index分别遍历index*2+1和index*2+2,即他们的左右孩子,遍历完左右子树后输出根结点,即完成了后序遍历~

 

PAT 1146. Topological Order (25) – 甲级

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (<= 1,000), the number of vertices in the graph, and M (<= 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (<= 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.
Output Specification:
Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.
Sample Input:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
Sample Output:
3 4

题目大意:给一个有向图,判断给定序列是否是拓扑序列~
分析:用邻接表v存储这个有向图,并将每个节点的入度保存在in数组中。对每一个要判断是否是拓扑序列的结点遍历,如果当前结点的入度不为0则表示不是拓扑序列,每次选中某个点后要将它所指向的所有结点的入度-1,最后根据是否出现过入度不为0的点决定是否要输出当前的编号i~flag是用来判断之前是否输出过现在是否要输出空格的~judge是用来判断是否是拓扑序列的~

PAT 1143. Lowest Common Ancestor (30) – 甲级

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
A binary search tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Given any two nodes in a BST, you are supposed to find their LCA.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.
Output Specification:
For each given pair of U and V, print in a line “LCA of U and V is A.” if the LCA is found and A is the key. But if A is one of U and V, print “X is an ancestor of Y.” where X is A and Y is the other node. If U or V is not found in the BST, print in a line “ERROR: U is not found.” or “ERROR: V is not found.” or “ERROR: U and V are not found.”.
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题目大意:给出一棵二叉搜索树的前序遍历,问结点u和v的共同最低祖先是谁~
分析:map<int, bool> mp用来标记树中所有出现过的结点,遍历一遍pre数组,将当前结点标记为a,如果u和v分别在a的左、右,或者u、v其中一个就是当前a,说明找到了这个共同最低祖先a,退出当前循环~最后根据要求输出结果即可~
PS:30分的题目30行代码解决,1行1分,惊不惊喜?意不意外?(真的是水题啊…)

 

PAT 1144. The Missing Number (20) – 甲级

Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<= 105). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.
Output Specification:
Print in a line the smallest positive integer that is missing from the input list.
Sample Input:
10
5 -25 9 6 1 3 4 2 5 17
Sample Output:
7

题目大意:给n个数字,找到不在这个数字列表里面的最小的正整数
分析:将每个数字出现的次数存储在map里面,num从1开始,如果m[num] == 0说明不存在,则输出这个num~

 

PAT 1085. PAT单位排行 (25) – 乙级

每次 PAT 考试结束后,考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。
输入格式:
输入第一行给出一个正整数N(<=105),即考生人数。随后N行,每行按下列格式给出一个考生的信息:
准考证号 得分 学校
其中“准考证号”是由6个字符组成的字符串,其首字母表示考试的级别:“B”代表乙级,“A”代表甲级,“T”代表顶级;“得分”是 [0,100] 区间内的整数;“学校”是由不超过6个英文字母组成的单位码(大小写无关)。注意:题目保证每个考生的准考证号是不同的。
输出格式:
首先在一行中输出单位个数。随后按以下格式非降序输出单位的排行榜:
排名 学校 加权总分 考生人数
其中“排名”是该单位的排名(从1开始);“学校”是全部按小写字母输出的单位码;“加权总分”定义为“乙级总分/1.5 + 甲级总分 + 顶级总分*1.5”的整数部分;“考生人数”是该属于单位的考生的总人数。
学校首先按加权总分排行。如有并列,则应对应相同的排名,并按考生人数升序输出。如果仍然并列,则按单位码的字典序输出。
输入样例:
10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu
输出样例:
5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2

分析:两个map,一个cnt用来存储某学校名称对应的参赛人数,另一个sum计算某学校名称对应的总加权成绩。每次学校名称string school都要转化为全小写,将map中所有学校都保存在vector ans中,类型为node,node中包括学校姓名、加权总分、参赛人数。对ans数组排序,根据题目要求写好cmp函数,最后按要求输出。对于排名的处理:设立pres表示前一个学校的加权总分,如果pres和当前学校的加权总分不同,说明rank等于数组下标+1,否则rank不变~
注意:总加权分数取整数部分是要对最后的总和取整数部分,不能每次都直接用int存储,不然会有一个3分测试点不通过~