PAT

题目	知识点	题目大意	难度	备注
1001 A+B Format （20 分）	字符串处理	按规定格式输出两数之和	0
1002 A+B for Polynomials （25 分）	模拟，多项式	计算两个多项式的和	0
1003 Emergency （25 分）	Dijkstra算法	求最短路径即可	4
1004 Counting Leaves （30 分）	dfs或者bfs	按层序输出所有叶节点	3
1005 Spell It Right （20 分）	水题		0
1006 Sign In and Sign Out （25 分）	水题		0
1007 Maximum Subsequence Sum （25 分）	DP	最大连续子序列和	4	按照一般思路可以快速写出demo，但是有个比较难处理的case：-1 -1 0 -1
1008 Elevator （20 分）	水题		2	题目有一个小坑
1009 Product of Polynomials （25 分）	模拟，多项式	输出多项式的乘积	3
1010 Radix （25 分）	进制转换，二分法	确定某一数等于另一个数的几进制	5++	很麻烦的一道题，想ac很难，各种小问题。题目表达也有问题。
1011 World Cup Betting （20 分）	简单计算		1
1012 The Best Rank （25 分）	排序	计算各项的排名	4	还是需要思考的。做了一下感觉心态崩了
1013 Battle Over Cities	图的连通分量		2	scanf 160ms，cin 400ms+ 从此以后只用scanf
1014 Waiting in Line （30 分）	模拟排队， queue	反正我是没做出来	5++	恶心的一匹，以后再做
1015 Reversible Primes （20 分）	素数，进制转换		2
1016 Phone Bills （25 分）	排序，模拟	对电话记录排序，计算账单	5++	条件比较多，很麻烦的一道题。
1017 Queueing at Bank （25 分）	模拟排队， queue	银行排队，k个窗口，计算等待时间	5+	比较麻烦。自己做这道题思考了很多
1018 Public Bike Management （30 分）	Dijkstra算法+DFS	自行车调度	5+	如果把一切都想清楚，细心写，其实不难
1019 General Palindromic Number （20 分）	进制转换，回文	判断k进制的某数是否是回文	1
1020 Tree Traversals （25 分）	二叉树	后序中序转层序	2	模板很重要
1021 Deepest Root （25 分）	图的遍历，dfs	求可以使树最深的根是哪些	4	dl的思想，两次dfs，取最深点的并集就是所求
1022 Digital Library （30 分）	map的应用，查询	图书馆，按书名，关键词等查询	4	输入方式比较特别，是按行输入，根据空格划分关键词
1023 Have Fun with Numbers （20 分）	大整数运算	整数乘以二，判断是否是原来各位数字的组合	2
1024 Palindromic Number （25 分）	大整数相加	逆置然后相加，直到得到回文	2
1025 PAT Ranking （25 分）	排序	整体按顺序输出，同时输出组内序号	2
1026 Table Tennis （30 分）	模拟排队，排序	队列等待，vip优先	5++	题目坑很多。理解题目意思，然后理清思路很重要。除了那些坑以外其他地方和之前的几个排队模拟类似
1027 Colors in Mars （20 分）	进制转换	水题	0
1028 List Sorting （25 分）	排序	水题	1
1029 Median （25 分）	双指针法	求两个有序数组的中间值	5++	内存卡得太紧，需要试很多次才能AC
1030 Travel Plan （30 分）	Dijkstra算法+DFS	路径最短，总花费最短	4	只有第二条件是节点数的时候才可以不dfs直接得到最优解，否则还是稳一点写个dfs
1031 Hello World for U （20 分）	图形打印		1
1032 Sharing （25 分）	链表	输出两链表的首个共用节点	1
1033 To Fill or Not to Fill （25 分）	贪心	输出最远行驶距离	5+	想思考清楚挺难的
1034 Head of a Gang （30 分）	图的遍历，dfs
1035 Password （20 分）	字符串处理		1
1036 Boys vs Girls （25 分）	查找元素		1
1037 Magic Coupon （25 分）	贪心算法	带正负的优惠券和带正负的商品，求能买到的最大的价值	2
1038 Recover the Smallest Number （30 分）	据说是贪心算法	给出几个小数字串，求他们组成的最小数	3	要想清楚如何比较，找到最简洁的方法
1039 Course List for Student （25 分）	不定长数组，hash	给出课程和注册的学生名，查询学生注册的课程	3	把学生名hash掉。用vector存数据
1040 Longest Symmetric String （25 分）	据说是动态规划	最长对称子串	3	之前用以每个字符为中心逐个扩展的方法也能过，不算慢，就是看起来有点傻。我后来想的方法是长度递增，逐个舍弃中心点。这个方法看起来就有点像dp了
1041 Be Unique （20 分）	hash	求数列中首个仅出现一次的数字	2
1042 Shuffling Machine （20 分）	模拟	洗牌	1
1043 Is It a Binary Search Tree （25 分）	BST	给出前序序列，判断是否是一棵BST（可能左大右小或者右大左小）	3	经典题型 细心！！
1044 Shopping in Mars （25 分）	二分法	找出和大于且最接近给定值的所有连续子串	3	不用二分法也能过
1045 Favorite Color Stripe （30 分）	动态规划，LIS / LCS	找出匹配串中每个字符可以重复出现，也可以缺少的最长子序列	5	想清楚很重要
1046 Shortest Distance （20 分）	模拟	环形高速公路，输出两出口间最近的距离	1
1047 Student List for Course （25 分）	STL使用	给出学生的课程，输出课程的学生	2
1048 Find Coins （25 分）	hash	找出元素范围有限的长串中和为给定值的两数	1
1049 Counting Ones （30 分）	数学问题	数从1到n的所有数里面有几个“1”	5	早忘了怎么做的了，反正有点麻烦
1050 String Subtraction （20 分）	hash	删除字符串里的给定字符	1
1051 Pop Sequence （25 分）	栈	判断序列是否可以是某栈的pop序列	2
1052 Linked List Sorting （25 分）	链表排序	给出链表排序后的结果	2	当然不是真的给链表排序了
1053 Path of Equal Weight （30 分）	树的遍历	给出带权树根节点到叶节点的权等于给定值的所有路径并排序	3	输入过程中对每个非叶节点的子树排序
1054 The Dominant Color （20 分）	贪心？	求出数列中个数过半的元素	2	用贪心会很快。也可以用map映射来做。
1055 The World's Richest （25 分）	排序	给出年龄和身价，然后按身价降序输出给定年龄区间内的所有人	5+	case很难过，用传统方法做必须在每个点上都尽力缩短时间。以前做的AC了，后来反而死活AC不了。本题中缩短时间的方法：用scanf而不是cin，用c字符串。
1056 Mice and Rice （25 分）	queue？	老鼠比赛，先按序号分组，每组留下一个胜者，重复这个过程。	4	题目本身逻辑很简单，但是题目阐述含混不清，而且有有歧义的地方。不值得做
1057 Stack （30 分）	树状数组+二分法	模拟一个栈，包括一个特殊功能，即可以查看当前栈中所有元素的中位数。	5++	树状数组存储了原始数组的前i项和，树状数组的好处在于可以把数组的更新的查询维持在同一个较低的时间复杂度（O(logn)）
1058 A+B in Hogwarts （20 分）	进制转换	简单进制转换	1
1059 Prime Factors （25 分）	素数	求大数的所有素因数	2
1060 Are They Equal （25 分）	字符串处理	判断两大数保留k位数字后是否相等	3
1061 Dating （20 分）	字符串处理	字符串对比，解密	2	难点在于弄清题目的意思
1062 Talent and Virtue （25 分）	排序	根据”德”和“才”，给“圣人”“小人””君子“”愚人“”小人“排序	2
1063 Set Similarity （25 分）	set	给出几个数列，输出任意两数列中重复元素个数占总元素个数的百分比	3	不用map很难做
1064 Complete Binary Search Tree （30 分）	满 二叉查找树	给出乱序，构造一个二叉查找树，并且是个满二叉树。	5	思路不难想，就是排序得到中序序列，在每个子树的处理中，可以直接得到根节点的位置，难点在于如何得到左右子树的大小。可以通过二叉树的性质计算，但是比较繁琐。我是利用一个函数来数
1065 A+B and C (64bit) （20 分）	大数运算	判断a+b是否大于c	2	可以写个string加法，也可以利用计算机加法溢出的规律来判断
1066 Root of AVL Tree （25 分）	AVL树	根据输入序列判断AVL树的根节点	4	关键在于熟练掌握AVL树的写法
1067 Sort with Swap(0, i) （25 分）	或许是贪心？	只允许swap(a[i], a[0])，求使数列有序所需要的最小交换次数	4	一直换啊换就行了，也不知道怎么证明这种做法的正确性。
1068 Find More Coins （30 分）	01背包，动态规划	支付特定的数额	5+	经典的动态规划。注意做之前要倒序。
1069 The Black Hole of Numbers （20 分）	简单数字操作	数字的简单操作	1
1070 Mooncake （25 分）	简单数学问题	已知单价和总量，求最大利润	2
1071 Speech Patterns （25 分）	map	统计出现数目最多的单词	3
1072 Gas Station （30 分）	Dijkstra算法	如何建加油站使得到房子的最小距离最大	5	只要搞清题意了还是很简单的
1073 Scientific Notation （20 分）	科学计数法，字符串处理	输入科学计数法的数，输出相应的小树	3
1074 Reversing Linked List （25 分）	链表	分段反转链表	3	要注意不一定所有的节点都是有用的
1075 PAT Judge （25 分）	排序	根据各项参数排序	3	注意读懂题目，搞清楚细节问题。比如有的
1076 Forwards on Weibo （30 分）	图的遍历	计算一条微博可以被转发多少次	3
1077 Kuchiguse （20 分）	字符串处理	找出字符串的共同后缀	1	注意整行字符串的输入
1078 Hashing （25 分）	hash，平方探查法	输出hash之后的位置，利用平方探查法	2	相关基础知识和概念一定要搞清楚，毕竟马上考研了
1079 Total Sales of Supply Chain （25 分）	树的遍历	计算销售树的总利润	2
1080 Graduate Admission （30 分）	排序	志愿填报机制模拟，先排序，随后按顺序看会被第几志愿录取	4	时间卡得比较紧，不过学到的一点是，比较函数用引用传参可以很大程度上缩短比较时间
1081 Rational Sum （20 分）	有理数模拟	输出两有理数之和	3	要注意辗转相除法结束的判定条件，即为最后一步余数为0
1082 Read Number in Chinese （25 分）	模拟	输出数字的中文读法	4	要考虑的情况比较多，如果要把不同情况的代码整合到一起会更麻烦
1083 List Grades （25 分）	简单排序	根据成绩排序并输出区间内的成绩	1
1084 Broken Keyboard （20 分）	字符串处理	找到键盘上坏掉的键（对比字符串找到所有缺失的字符）	1	记住cctype里面各函数的用法，可以大大节省coding时间
1085 Perfect Sequence （25 分）	二分法	给定p，求满足max	3
1086 Tree Traversals Again （25 分）	树的遍历	给出栈的操作，求后序序列	4	可以利用栈来得到前序和中序序列，然后用经典方法解决。也可以想办法利用本题的特点。
1087 All Roads Lead to Rome （30 分）	Dijkstra+DFS	求出依次满足路径最短、总快乐最多、平均快乐最多的路径	4	熟能生巧
1088 Rational Arithmetic （20 分）	有理数模拟	按格式输出有理数的四则运算结果	5	可能是写的时候思路不清晰，写了很久而且很多bug。
1089 Insert or Merge （25 分）	归并排序	根据中间结果判断是插入排序还是归并排序。并且进行下一步排序	3	归并排序的特点要清楚
1090 Highest Price in Supply Chain （25 分）	树的遍历	根据供应商树求最大利润	3	浮点大数的处理还是比较麻烦。
1091 Acute Stroke （30 分）	DFS	三维点阵，求满足条件的最大肿瘤块	5	搞清题目意思有点麻烦。搞清楚了还是很容易的。要注意的点是直接用递归会导致段错误，改用队列之后就不会了，这说明递归调用在空间利用率上还是很吃亏的。
1096 Consecutive Factors （20 分）	数学问题	求数的最长连续因子串	3	要搞清楚问题的数学特点。否则大case不容易过
1097 Deduplication on a Linked List （25 分）	链表	去掉链表中绝对值与之前存在的节点相同的所有节点，并且分别输出原来的和保留的链表	2
1098 Insertion or Heap Sort （25 分）	堆排序	根据中间结果判断是插入排序还是堆排序，并输出下一步的结果	3	一定要熟悉堆排序的过程！！
1099 Build A Binary Search Tree （30 分）	BST	给出二叉搜索树的结构和元素，求层序输出	2	貌似练了这几个月，比以前更菜了
1100 Mars Numbers （20 分）	数字处理	地球和火星的数字转换，不同的进制和写法	2
1101 Quick Sort （25 分）	快速排序	求数列中使得可以把数列看做一次partition操作结果的枢纽的数目。	2
1102 Invert a Binary Tree （25 分）	树的遍历	给出二叉树，输出层序序列和反转树之后的中序序列	2
1103 Integer Factorization （30 分）	动态规划或者DFS	找出k个数的和等于特定值n，这k个数只能是正整数幂，同时这k个数要满足其和最大、和相同的情况下数列更大	5+	自己写dfs剪枝剪得有问题。会出现超时。用dp做会很快，就是会更复杂一点。我第一次和第二次做这个题都是用dp才AC的。这两天有时间再看一下dfs的做法
1104 Sum of Number Segments （20 分）	数学问题	浮点数数列的一个连续子串称为一个segment，求一个数列的所有segment里所有元素的和	4	想清楚了代码就两行。但是还是AC不了，对于大case需要优化计算过程。这个还是挺难的。因为不是bug导致的不通过，做的时候还要坚信自己思路的正确性
1105 Spiral Matrix （25 分）	打印	旋转打印矩阵	2
1106 Lowest Price in Supply Chain （25 分）	树的遍历	求供应链中的最低价格	2
1107 Social Clusters （30 分）	并查集	给出每个人的爱好，如果两个人有一个共同爱好，则属于同一个社交圈，求所有的社交圈	4	并查集的写法要牢记
1108 Finding Average （20 分）	字符串处理	输入一些字符串，判断是否是数，并求其平均数	3	如果不用库函数，自己写会比较麻烦
1109 Group Photo （25 分）	模拟	根据身高要求排队照相	3	题目不难，略显麻烦
1110 Complete Binary Tree （25 分）	完全二叉树	判断是否是完全二叉树	2
1111 Online Map （30 分）	Dijkstra算法	给出有向图，权值是长度和时间，分别求时间最短的最短路径和长度最短的最快路径，按照格式输出	5	题目不难，有些麻烦。根据题目特点（同权路径的取舍只与第二权和节点数当中的一个变量有关）可以省去dfs，直接用贪心的思想来做。当然最重要的还是要对Dijkstra算法足够熟悉
1112 Stucked Keyboard （20 分）	字符串处理	键盘上有的键坏了，按一次会输入k个该字符。已知输入的字符串，求正确的字符串。	4	这道题还是有点麻烦。动手做以前一定要先想清楚。想清楚了还是比较简单
1113 Integer Set Partition （25 分）	简单数学问题	把数列分成两份，使两份元素个数相差最小的情况下和相差最大	1	就是排序
1114 Family Property （25 分）	并查集	给出每个家庭的成员关系和房产、面积，把所有家【族】按照单位面积房产数增序输出	5	并查集一定要熟悉
1115 Counting Nodes in a BST （30 分）	BST，树的遍历	按输入序列构造BST，然后数最底层和倒数第二层有几个节点	3
1116 Come on! Let's C （20 分）	简单逻辑题	判断素数	1
1117 Eddington Number （25 分）	简单逻辑题	求爱丁顿数	1	理解题目意思很重要。不过想做到这点并不容易
1118 Birds in Forest （25 分）	并查集	给出一系列数组，每个数组里的鸟属于同一颗树，求树和每棵树上鸟的个数	4	并查集并查集！
1119 Pre- and Post-order Traversals （30 分）	树的遍历，前序后序	给出前序后序序列，判断树是否唯一，输出任意一个中序序列	4	理清思路是首要，其次是要尽量使代码优雅
1120 Friend Numbers （20 分）	set	整数的各位数字和称为友id，求数列中所有的友id，增序输出	1
1121 Damn Single （25 分）	set	给出所有couple和所有来party的人，求party上的所有单身狗（对象没来也算）	2
1122 Hamiltonian Cycle （25 分）	图的简单操作	汉密尔顿环是包含所有节点的简单路径。求给出的序列是否是汉密尔顿环	1
1123 Is It a Complete AVL Tree （30 分）	AVL树	给出构造序列，求构成的AVL树的后序序列	5	AVL树的写法要牢记
1124 Raffle for Weibo Followers （20 分）	模拟	微博回复抽奖，每第N个人中奖	2	理解题目意思
1125 Chain the Ropes （25 分）	简单逻辑题	两根绳子分别对半折可以练成一个链条，把链条作为一个绳子可以重复上述操作，给出数列求可以构成的最大的链条	1
1126 Eulerian Path （25 分）	图论	欧拉路径是遍历每条边的路径，欧拉环是成环的欧拉路径。给出图求是否存在欧拉路径或者欧拉环	2	用dfs会超时，必须用题目中给的判断方法，即根据点的入度和出度判断。
1127 ZigZagging on a Tree （30 分）	中序后序转层序	根据中序后序求层序，要求是要按照来回反复的顺序输出	4
1128 N Queens Puzzle （20 分）	模拟	N皇后问题。给出N个皇后的位置（棋盘定义为N*N），判断是否冲突	1
1129 Recommendation System （25 分）	模拟	根据用户点击物品的历史进行推荐，规则是按照点击的数目降序，相同数目id升序的优先级推荐前k个商品	3	要读懂题目。据说可以用set和运算符重载数目的。以后可以看看
1130 Infix Expression （25 分）	中缀表达式	给出语法树，输出带括号的中缀表达式	2
1131 Subway Map （30 分）	dfs	根据地铁图给出路径。首先要求站点数最短，其次换乘数最少，给出换乘的具体路径（几号线第几站）	5++	总之就是一个字：麻烦。题目逻辑不是很难。不能用bfs，会有bug，详见代码。
1132 Cut Integer （20 分）	字符串处理	把整数分成前后两部分，判断这个整数是不是这两部分之积	1
1133 Splitting A Linked List （25 分）	链表	把链表分成正数和负数两部分并输出	2
1134 Vertex Cover （25 分）	hash	顶点覆盖是指连接所有边的顶点集。给出图，判断一些顶点集是不是顶点覆盖	2
1135 Is It A Red-Black Tree （30 分）	红黑树，BST，前序	给出红黑树的定义和一些BST的前序序列，判断他们分别是不是红黑树	3
1136 A Delayed Palindrome （20 分）	字符串处理	数和其逆置的结果相加，重复多次判断是否是回文数	1
1137 Final Grading （25 分）	排序	按照各科成绩加权给学生排序	2
1138 Postorder Traversal （25 分）	树的遍历	中序后序转前序	2
1139 First Contact （30 分）	图	两个想成为情侣的人需要通过两个【分别与两人性别相同、分别与两人认识且相互认识】的人作为媒人来搭桥。给出朋友网以及想成为情侣的两人，求他们之间可以有几对媒人。注意情侣不一定是异性	5
1140 Look-and-say Sequence （20 分）	字符串处理	按照规则迭代字符串。后一个字符串的构成大概是前一个字符串离有几个几。具体见题目	2	要花时间读懂题意，读懂之后很简单
1141 PAT Ranking of Institutions （25 分）	排序、map	pat分a、b、t三个等级权重不一，每个大学（字符串表示）参加了若干次pat，求最后排名。	5	容易超时。从本题总结出的节省时间的方法：利用unordered_map而不是map可以节省很多时间，当有多个要存储的数据时用多个简单的map可能要比用一个struct的map节省时间。
1142 Maximal Clique （25 分）	无向完全图	给出图和若干顶点集，判断这些顶点集是否构成一个无向完全子图	2	完全图，挺简单的
1143 Lowest Common Ancestor （30 分）	BST中的LCA	给出BST的前序序列和若干query，求这些query的LCA	4	想清楚再做。。。
1144 The Missing Number （20 分）	hash	给出序列，找出不在序列中的最小正整数	1
1145 Hashing - Average Search Time （25 分）	hash，平方探查法	给出表长，插入序列和查询，求平均查询时间。Hashtable用二次方探查法	2	要知道平方探查法是什么
1146 Topological Order （25 分）	拓扑排序	给出拓扑图和若干序列，判断他们是不是该图的拓扑排序	2
1147 Heaps （30 分）	堆	给出完全二叉树判断是不是堆，是大顶堆还是小顶堆	2
1148 Werewolf - Simple Version （20 分）	模拟	每个人给出一个陈述，一共有两个狼人两个说谎者，求狼人。	5	思路很重要，一定是假设狼，判断说谎者，反之会很复杂。
1149 Dangerous Goods Packaging （25 分）	stl	危险物品不能一起包装，判断case能不能包装	2
1150 Travelling Salesman Problem （25 分）	图	判断是不是欧拉路径	3
1151 LCA in a Binary Tree （30 分）	LCA	给出前序中序求二叉树的LCA	4
1152 Google Recruitment （20 分)	字符串处理	求序列中第一个k位的奇数	1
1153 Decode Registration Card of PAT	STL的使用	对ID进行分类，排序，计数等处理	4	细心。这道题不怎么卡时间，我在时间上花了太长时间，忽视了输出的细节，导致这次没有满分
1154 Vertex Coloring （25 分)	图	判断相邻节点颜色是否一条，求总颜色数	2
1155 Heap Paths （30 分)	堆	判断是不是堆，是什么堆	2