PAT题解

1

PAT_甲级_1149 Dangerous Goods Packaging

• 乔梓鑫   2020-11-30 发布
• 1 收藏

首先使用$incompatible$二维数组存储每一个物体的所有不兼容的物体，并使用$incompat$数组记录当前货箱有哪些无法兼容的物品(为true即为不可兼容)，然后在每一个需要装箱的货物进行依次装箱的时候，先检查当前物...

1

PAT_甲级_1147 Heaps

• 乔梓鑫   2020-11-30 发布
• 1 收藏

对于完全二叉树可以使用一个数组来保存其层序序列，然后使用函数isMaxHeap和isMinHeap分别判断该完全二叉树是否是大根堆还是小根堆，如果都不是则输出Not Heap，然后再使用postTraverse对该完全二叉树进行后序遍...

1

PAT_甲级_1146 Topological Order

• 乔梓鑫   2020-11-29 发布
• 1 收藏

给定一个有向图，N个顶点，M条边，现给定K个查询，每一个查询输入一个序列，判断该序列是否是该图的拓扑排序序列，如果不是，输出该序列的编号(从0开始)

1

PAT_甲级_1145 Hashing - Average Search Time

• 乔梓鑫   2020-11-29 发布
• 1 收藏

给定N个数字插入到用户指定长度为MSize的hash表中，如果X无法插入就输出X cannot be inserted.紧接着给出M个查询的数字，计算平均M个数字的查找时间。

1

PAT_甲级_1144 The Missing Number

• 乔梓鑫   2020-11-29 发布
• 1 收藏

2、虽然题目说输入的数字在int范围内，但是如果没有出现缺少的情况下，最大的正数就是N ,因为如果有缺失一定在N以内的数字，并且后面就算出现比N大的数字也没有必要求解了。(该条件不考虑直接死循环可以)

1

PAT_甲级_1143 Lowest Common Ancestor

• 乔梓鑫   2020-11-29 发布
• 1 收藏

使用$pre$存放输入的先序序列，$isLegal$标记每一个树中的节点，对于输入的节点只要小于0或者$isLegal$对应值为false，就说明不在树中，输出对应的$ERROR$信息，都在就在先序序列中进行搜索，假设输入的结点为$a$...

1

PAT_甲级_1135 Is It A Red-Black Tree

• 乔梓鑫   2020-11-28 发布
• 1 收藏

首先使用isRed记录所有的红色结点，这样在建树的时候就可以使用正数来建树。然后再根据先序序列建立二叉搜索树(不需要中序),然后再使用先序遍历判断该数是否是红黑树即可。

1

PAT_甲级_1142 Maximal Clique

• 乔梓鑫   2020-11-28 发布
• 1 收藏

给定一个无向图G，顶点编号为1到Nv,Ne条边，判断给出的一组顶点集合是否构成该图的一个极大完全子图，如果是输出Yes,否则判断是否是一个完全子图，如果是输出Not Maximal，否则输出Not a Clique。

1

PAT_甲级_1141 PAT Ranking of Institutions

• 乔梓鑫   2020-11-28 发布
• 1 收藏

我们使用Institution保存需要输出的学院的每一个信息，在输入的时候使用map institution容器来保存每一个学校的相关信息，然后再将信息搜集完毕所有学校添加进vector result容器中以方便排序从而获取排名，最后再...

1

PAT_甲级_1140 Look-and-say Sequence

• 乔梓鑫   2020-11-28 发布
• 1 收藏

给定一个[0,9]的数字D和正整数N，第一个数字为D，后面每一个数字都是用来描述前面一个数字所产生的，要求输出第N个数字。比如第一个数字为1，描述为有一个1，那么第二个数字就是数字1和次数1的组合11，依次类推。

1

PAT_甲级_1139 First Contact

• 乔梓鑫   2020-11-28 发布
• 1 收藏

一张人际关系网络图，然后给出一对情侣A和B(负数代表女生，正数代表男生)，要求找到A的朋友(不是B,和A性别相同)C,B的朋友(不是A,和B的性别相同)D,如果C和D是朋友那么输出C和D的编号(输出的编号均为正数)，并且按...

1

PAT_甲级_1138 Postorder Traversal

• 乔梓鑫   2020-11-27 发布
• 1 收藏

这里采用不建树但是借鉴建树的过程，后序遍历第一个结点实际上是左子树最左的结点，我们只需要不断递归访问左子树，直到第一次遇到最左的结点即可，这里使用变量c来控制是否是第一次访问，初始为0，在c==0&&a...

1

PAT_甲级_1137 Final Grading

• 乔梓鑫   2020-11-27 发布
• 1 收藏

给出三个名单表格，分别记录考生的在线编程的成绩、期中成绩和期末成绩；需要计算最终成绩，然后筛选出能够获得证书的名单，并按照最终成绩的降序和ID的升序排列输出。

1

PAT_甲级_1136 A Delayed Palindrome

• 乔梓鑫   2020-11-27 发布
• 1 收藏

给定一个不超过1000位的数字A，如果是回文数，就输出A is a palindromic number.否则就计算该数和其逆置数的和如果在10次计算内其结果C是回文数，就输出每一步的计算过程和C is a palindromic number.

1

PAT_甲级_1134 Vertex Cover

• 乔梓鑫   2020-11-26 发布
• 1 收藏

如果一个图的所有边的领接点至少有一个点在集合中，那么就称为这个集合为一个vertex cover，现给出一个图的顶点N和边数M，M条边的信息,和K次查询的集合元素，问当前集合是否是该图的一个vertex cover。

1

PAT_甲级_1133 Splitting A Linked List

• 乔梓鑫   2020-11-26 发布
• 1 收藏

给定一个单链表，节点数目N和阈值K，从新将链表按照如下规则进行排序，节点值小于0的在最左边，[0,K]的在中间，大于K的在最右边,同时同一类别的节点其相对顺序不能改变.

1

PAT_甲级_1132 Cut Integer

• 乔梓鑫   2020-11-26 发布
• 1 收藏

看到分割问题，首先想到的是字符串分割，我们采用string s来接受输入的数字，然后将其前半部分分割并转化为整数为a，后半部分分割并转化为整数为B，并将s转化为整数z,如果z%(a*b)==0，输出Yes,否则输出No。

1

PAT_甲级_1131 Subway Map

• 乔梓鑫   2020-11-26 发布
• 1 收藏

一开始想到的是用Dijkstra算法求解该问题，但是Dijkstra算法更适合求解第一标尺为边权相关问题，所以想到了DFS，并设置其参数depth,用来记录在从起点到终点的遍历过程中所经历的结点个数，然后采用全局量minDepth...

1

PAT_甲级_1072 Gas Station

• 乔梓鑫   2020-11-24 发布
• 1 收藏

现在有N座房子,M个加油站待选择点,K条边,现在要在M个加油站待选择点选择一个加油站出来,要求满足距离N个房子尽可能远但是同时也得保证房子均在服务范围Ds中,如果有多个选择平均距离最小的,如果还有多个，选择编号...

1

PAT_甲级_1087 All Roads Lead to Rome

• 乔梓鑫   2020-11-24 发布
• 1 收藏

有N个城市，K条无向边,现在需要从某个给定的起始城市出发,前往名为"ROM"的城市，给出每条边所需要消耗的花费,求从起始城市出发,到达城市ROM所需要的最少花费,并输出最少花费的路径。如果这样的路径有多条，则选择...