- 博客(97)
- 收藏
- 关注
RSS订阅原创 【PAT甲级题解记录】1107 Social Clusters (30 分)
Problem：1107 Social Clusters (30 分)Tags：并查集。
2023-03-02 23:59:14
161
1
原创 【PAT甲级题解记录】1034 Head of a Gang (30 分)
Problem：1034 Head of a Gang (30 分)Tags：图的遍历 连通分量统计 DFS。
2023-03-02 20:00:02
313
原创 【PAT甲级题解记录】1119 Pre- and Post-order Traversals (30 分)
Problem：1119 Pre- and Post-order Traversals (30 分)Tags：树的三种遍历 建树。
2023-03-02 01:31:35
197
原创 【PAT甲级题解记录】1110 Complete Binary Tree(25 分)
Problem：1110 Complete Binary Tree (25 分)Tags：完全二叉树 二叉树的层序遍历 BFS DFS。
2023-03-01 18:54:26
218
原创 【PAT甲级题解记录】1079 Total Sales of Supply Chain(25 分)
Problem：1079 Total Sales of Supply Chain (25 分)Tags：树的带权路径长度 树的遍历。
2023-03-01 16:18:08
299
原创 【PAT甲级题解记录】1155 Heap Paths (30 分)
问题描述给一棵完全二叉树，求其是否为堆，要求输出大根堆还是小根堆，并且输出每一条自上而下的分支路径。解题思路对于路径的输出，利用dfs（其实就是二叉树的NRL遍历，和先序遍历差不多，先序遍历是NLR）配合动态维护vector就可以完成。至于堆性质的判定，我们可以直接判断heap[0]和heap[1]的大小顺序，然后以此顺序为参照，在dfs里判断path是否按照该顺序排序。
2023-02-27 23:03:37
219
原创 【PAT甲级题解记录】1154 Vertex Coloring (25 分)
问题描述给定一个图的节点和边，以及每一个点的颜色，如果有临接点颜色相同输出No，否则输出不同的颜色数量。解题思路方法一：遍历边即可，如果当成无向图遍历一遍会每个边多遍历一遍，但是时间足够就这么简单的写吧。方法二：除了直接遍历边，还可以用dfs来判断。
2023-02-27 21:50:54
47
原创 【PAT甲级题解记录】1152 Google Recruitment (20 分)
求一个长度为L的字符串，求第一个长为K的素数（考虑字符串中存在的前缀0）stoi()字符串转整型，简单的字符串处理好帮手。
2023-02-27 19:31:13
262
原创 【PAT甲级题解记录】1151 LCA in a Binary Tree (30 分)
问题描述给定一棵二叉树，求两个元素 lowest common ancestor (LCA) 即最低公共祖先，也就是离两个元素的最近公共祖先节点。解题思路这道题至少可以有两种解法：暴力并查集法：利用并查集，说是并查集，其实只是一个保存前置节点的数组，在建树的过程中就可以得到。然后对输入的元素分别向上遍历，找到第一个相同的即可，但节点的值可以为负数，若存储下标也会超范围，所以我们需要离散化，可以自己写离散化，也可以利用map直接写（实测这道题需要unorder_map才不会超时）。DFS建树法：
2023-02-27 18:47:26
200
原创 【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分)
问题描述给定一个图和一些路径，求这些路径是否为旅行商环路、简单旅行商环路或者非旅行商环路。TS simple cycle if it is a simple cycle that visits every city;TS cycle if it is a cycle that visits every city, but not a simple cycle;Not a TS cycle if it is NOT a cycle that visits every city.解题思路只要会存储
2023-02-27 16:48:08
205
原创 【PAT甲级题解记录】1149 Dangerous Goods Packaging (25 分)
问题描述有一批化学货品，会发生反应的货品不能放在一个集装箱，现在两两给定会互相发生反应的化学货品，再给出每一个集装箱的货品清单，分别求这些集装箱是否可安全装箱。解题思路首先明确一点，若AB会反应，BC会反应，那不代表AC会反应，所以这不是一个并查集的问题，而是一个映射的问题，用map可轻松解决。
2023-02-26 23:32:01
351
原创 【PAT甲级题解记录】1148 Werewolf - Simple Version (20 分)
在一场狼人杀游戏中有2头狼，其余均为人，每名玩家都有一条发言说另一个玩家的身份，其中分别有一头狼和一个人说的话是错误的。其他均指认正确。求哪俩个玩家是狼（输出编号靠前的情况）。这个问题描述很奇怪，“Given that there were 2 werewolves among them, at least one but not all the werewolves were lying”，即“其中有两个狼人，至少有一个但不是所有的狼人在撒谎”，那不就是一个狼人在撒谎吗😓。
2023-02-26 22:13:29
246
原创 【PAT甲级题解记录】1025 PAT Ranking (25 分)
问题描述PAT 考试有不同考场，给出不同考场的学生成绩，要求汇总后根据成绩高低输出考生id、考场号、考场排名、总排名。解题思路我们写一个结构体用来存储学生信息：id、考场号、成绩、考场排名、总排名，结构体排序以成绩降序为第一顺序，考场id为第二顺序。输入每个考场的学生信息，包括id、考场号和成绩。然后对这个考场的考生成绩排序，拍完序后可以得到这个考场每个学生考场排名。最后把所有学生一起排序，同理得到每个学生的总排名。
2023-02-26 19:46:49
82
原创 【PAT甲级题解记录】1024 Palindromic Number (25 分)
问题描述简单的字符串处理解题思路关键俩个点：最多要加100次，注意数据范围并不是简单的乘以100，而是 21002 100 ，所以long long不行需要string进行大整数加法。注意输入即是回文的情况，这种情况就直接输出N和0即可。
2023-02-26 18:20:19
243
原创 【PAT甲级题解记录】1022 Digital Library (30 分)
问题描述给定一些书的数据，包括书名，编号，作者等等，然后再输入一些关键字，把所有符合的书的编号输出来即可。解题思路一开始还写了个结构体来存储，后来发现只需要输出对应的id序列，那就简单了，用一个string为键、string的数组为值的map就可以了。map中，键是我们query时属于的title、author等信息，而值就是对应的id序列。我们有5类query，那这样的map就需要5个，定义为一个map数组即可。
2023-02-26 15:22:40
68
原创 【PAT甲级题解记录】1021 Deepest Root (25 分)
问题描述求一个N个点N-1条边的图是否能构成二叉树，能的话输出能形成最大深度的根结点，不能的话输出联通分支数。解题思路一开始还以为要分别看回路和联通分支，但这道题给的数据N点N-1条边保证了这两种情况只会同时出现，那就简单很多了，直接暴力就可以过题。
2023-02-25 23:40:49
274
原创 【PAT甲级题解记录】1020 Tree Traversals (25 分)
众所周知，当有中序序列+前序序列或者中序序列+后序序列时就可以生成一个具体的二叉树，本题求层序序列其实就是求生成二叉树按照下标顺序输出而已。已知中前或者中后求二叉树的原理其实一模一样，由于中序序列其每一个根的左子树必在序列前面，右子树必在序列后面，而前序的第一个和后序的最后一个就是根，依靠这俩点就可以生成二叉树。比如 post= “4 5 2 6 7 3 1” ，in = “4 2 5 1 6 3 7” ，那么根据post得知1就是当前二叉树的根，我们在in中找到1，也就得到了in中的左子树"4 2
2023-02-25 21:13:41
312
原创 【PAT甲级题解记录】1019 General Palindromic Number (20 分)
问题描述给定一个正整数N，求其作为b进制数时是否为回文数。解题思路进制转化完后存储下来，半个循环对比左右数值即可。
2023-02-25 14:27:26
292
原创 【PAT甲级题解记录】1018 Public Bike Management (30 分)
简单来说就是求单源最短路径，但是每个点都有一定数量的自行车，并且给定一个标准车数，我们要从起点到终点一边走一边调整每个点的车数至标准车数。也就是说我们出发时需要拿一定数量的车，在路上遇到多的可以补充进来，少的就要用出去，最终满足使所有车数都标准。现在要求最短路径下，出发时拿的车数最小的情况，当拿出最小情况一样，就要求拿回车数最小的情况（车多出来了就要拿回去）。这里很坑，他有三个条件，前两个条件相同情况下还会看第三个，感觉姥姥这题出的太折磨了。（菜是原罪）
2023-02-25 01:01:49
328
原创 【PAT甲级题解记录】1017 Queueing at Bank (25 分)
一个银行K个窗口，每个窗口接待一个客户，营业时间8:00到17:00，之前到达的需要等，之后到达的不接待。给出N个客户的到达时间和需要服务时间，求平均等待时间。
2023-02-24 22:46:56
452
原创 【PAT甲级题解记录】1016 Phone Bills (25 分)
问题描述给定一些人的通话记录（有开始时间和结束时间构成），不同的时间段收费不一样，要求生成每个人的具体账单。解题思路思路每个人有每个人的想法，一般来说肯定要对名字和时间排序，就看大家习惯怎么保存数据怎么写了。
2023-02-24 18:38:20
421
原创 【PAT甲级题解记录】1015 Reversible Primes (20 分)
问题描述求一个数在给定进制下的逆序数和顺序数是否都为素数。解题思路写个反转加进制转化，再判断下素数即可，题目数据小无需过多操作。
2023-02-24 18:32:49
44
原创 【PAT甲级题解记录】1014 Waiting in Line (30 分)
银行有N个业务窗口，每个窗口可以排队M人，如果有多的人就在外面等，8点开始K个人按照输入顺序去办理业务，当外面等的人能进去排队时优先选择人少的队伍，如果一样就优先选择序号靠前的窗口。现在给定所有人的业务需要的时间，求每个人按照这个规则办完业务的时间。（只接受17点前开始办理的业务，坑点在于17点前办理的业务结束时间可能超过17点，所以输出时不能只判断结束时间还应考虑开始时间）
2023-02-24 16:46:48
443
1
原创 【PAT甲级题解记录】1014 Waiting in Line (30 分)
银行有N个业务窗口，每个窗口可以排队M人，如果有多的人就在外面等，8点开始K个人按照输入顺序去办理业务，当外面等的人能进去排队时优先选择人少的队伍，如果一样就优先选择序号靠前的窗口。现在给定所有人的业务需要的时间，求每个人按照这个规则办完业务的时间。（只接受17点前开始办理的业务，坑点在于17点前办理的业务结束时间可能超过17点，所以输出时不能只判断结束时间还应考虑开始时间）
2023-02-24 16:46:02
400
原创 【PAT甲级题解记录】1013 Battle Over Cities (25 分)
问题描述给出一个城市和公路的连通图（虽然题目里没有明确说明），城市编号1-N。每一次询问都独立输入一个城市编号，求删去这个城市后需要至少加几条路使得连通图成立。解题思路其实就是求连通分量数量，想了想试了试没有想到很巧妙的方法，那还是用搜索稳一点：以每个城市为起点开一个dfs，如果被搜索过就直接跳过，最后开了几个dfs就是几个连通分量。
2023-02-24 16:40:29
360
1
原创 【PAT甲级题解记录】1012 The Best Rank (25 分)
问题描述一个学生有三门课的成绩以及一个平均分成绩，分别用A、C、M、E表示。每一个学生都有一个 best ranks – 最好排名，指的是四个成绩里取排名最高的成绩，求每个学生的最好排名以及是哪门成绩（若最好排名的成绩可以是不同的学科，按照ACME顺序优先输出）。解题思路一个学生有四个成绩，用一个结构体或者类存储会比较方便，又考虑到每个成绩都需要排名，结构体内应还有四个成绩的排名值、最好排名的课程号以方便查询。对四个成绩分别排序以此初始化所有学生的四个成绩的排名值。（小技巧：利用stl的sor
2023-02-24 00:27:27
110
原创 【PAT甲级题解记录】1011 World Cup Betting (20 分)
分别给定3场比赛不同结果的赔率，问怎么买能到达最大可能收益。这题题目有点长，看不懂单词可能都不知道在讲什么，但是根据样例能大概想出来，所以根据题意直接写就行了，甚至连个坑都没有。
2023-02-23 22:28:32
39
原创 【PAT甲级题解记录】1010 Radix (25 分)
问题描述问题转化过来就是给你俩个数，其中一个数确定进制，确定另一个数的进制，要求是能使俩数相等的最小进制。解题思路基础思路就是先把确定进制的数转化为10进制数 temp，然后找另一个数的进制使其转化为10进制后相等。
2023-02-23 21:52:55
221
原创 【PAT甲级题解记录】1009 Product of Polynomials (25 分)
问题描述求两个多项式的乘积。解题思路数据范围很小，直接开俩个数组表示输入多项式，再开一个数组表示结果多项式，用普通的乘法思想去模拟即可（系数相乘，指数相加）。注意点在于结果数组大小不要开错了，不是和输入数组一样大的。
2023-02-23 20:12:54
56
原创 【PAT甲级题解记录】1008 Elevator (20 分)
Problem：1008 Elevator (20 分)Tags：模拟。和上一题一样，由于数组访问顺序具有单调性，其实只需要提供上一个值就可以了，无需数组
2023-02-23 19:09:52
38
原创 【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)
问题描述求最大连续子序列和，输出这个连续子序列的首值、尾值和序列和（优先最靠前的），如果都为这个序列都为负的输出0和整个序列的首尾值。解题思路一道经典又特殊的动态规划，本身很简单，但考虑到要求最靠前的首尾值，容易出错，难度相应提高。
2023-02-23 17:49:16
276
原创 【PAT甲级题解记录】1006 Sign In and Sign Out (25 分)
问题描述每个学生都有一个签到时间和签退时间，求第一个签到和最后一个签退的学生ID。解题思路如果理解成最值问题，那就搜索一遍找到最值即可。如果当成排序问题做，那就写个结构体排下序。
2023-02-23 01:07:32
48
原创 【PAT甲级题解记录】1004 Counting Leaves (30 分)
1. 其实算是树的遍历，但不需要花心思写太多数据结构，只需要拿一个二维数组去存取每一个节点的子节点集合。2. 遍历方法可以采取递归dfs较为简单，搜索到叶子节点时对相应层的叶子数累加即可。
2023-02-22 20:47:53
32
原创 【PAT甲级题解记录】1003 Emergency (25 分)
对于单源最短路径（这道题也应该不会出现负边），一般我们最常用的就是dijkstra算法，但这里不单单是求最短路径，但是依旧可以用这个算法，算是dijkstra求最短路径的变题。
2023-02-22 17:32:42
409
原创 【PAT甲级题解记录】1002 A+B for Polynomials (25 分)
This time, you are supposed to find *A*+*B* where *A* and *B* are two polynomials.简单来说给定俩个多项式求和。
2023-02-22 15:05:02
49
原创 【PAT甲级题解记录】1001 A+B Format (20 分)
Problem：1001 A+B Format (20 分)Tags：整型转字符串 字符串截断
2023-02-22 14:26:28
214
原创 常用排序算法总结（冒泡、简单选择、直接插入、归并、快排、计数排序...）
【C++代码】常用排序算法总结（冒泡、简单选择、直接插入、归并、快排、计数排序...）
2023-02-09 18:04:41
802
原创 CFS-Round-762 D.New Year‘s Problem 题解 (二分+贪心)
文章目录1 题意1.1 原文1.2 题目简意2 思路2.1 二分2.2 贪心1 题意1.1 原文Vlad has 𝑛 friends, for each of whom he wants to buy one gift for the New Year.There are 𝑚 shops in the city, in each of which he can buy a gift for any of his friends. If the 𝑗-th friend (1≤𝑗≤𝑛) receive
2022-05-05 19:24:37
1010
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人