分门别类刷PAT甲级

\quad 博主正在准备PAT考试中，欲将PAT155道甲级考试题分门别类罗列出来，这样刷能让自己对每种类型的题有一个综合的认识。这篇博客会持续更新，力求每道题思路尽可能清楚简洁，欢迎大家加我QQ:1613511883一起探讨。

一、模拟题

1、字符串处理(11题)

\quad 字符串处理在PAT中占有较高比重，几乎每年都会考，难度不高，一般在第1题或者第2题，但需要考虑到各种情况，有些题想拿满分有一定难度，需要很细致。

编号	标题	题解	难度等级	备注
1001	A+B Format (20 分)	C++题解	1
1005	Spell It Right (20 分)	C++题解	1
1022	Digital Library (30 分)	C++题解	3	字符串+map
1035	Password (20 分)	C++题解	1
1061	Dating (20 分)	C++题解	2
1060	Are They Equal (25 分)	C++题解	3	科学计数法
1071	Speech Patterns (25 分)	C++题解	1	词频统计
1073	Scientific Notation (20 分)	C++题解	2	科学计数法
1077	Kuchiguse (20 分)	C++题解	1
1082	1082 Read Number in Chinese (25 分)	C++题解	3
1108	Finding Average (20 分)	C++题解	2	字符串转数字
1140	Look-and-say Sequence (20 分)	C++题解	1

2、模拟(26题)

编号	标题	题解	难度等级	备注
1002	A+B for Polynomials (25 分)	C++题解	1	多项式加法
1008	Elevator (20 分)	C++题解	1	模拟电梯运行
1009	Product of Polynomials (25 分)	C++题解	1	多项式乘法
1014	Waiting in Line (30 分)	C++题解	3	队列模拟，全网最简单写法
1016	Phone Bills (25 分)	C++题解	3	电话账单
1017	Queueing at Bank (25 分)	C++题解	3	模拟银行排队
1026	Table Tennis (30)	C++题解	4
1042	Shuffling Machine (20 分)	C++题解	1	数组模拟
1046	Shortest Distance (20)	C++题解	1
1047	Student List for Course (25)	C++题解	1
1054	The Dominant Color (20)	C++题解	1
1056	Mice and Rice (25)	C++题解	1
1063	Set Similarity (25)	C++题解	1
1065	A+B and C (64bit) (20)	C++题解	1
1095	Cars on Campus (30)	C++题解	1
1105	Spiral Matrix (25)	C++题解	1
1109	Group Photo (25)	C++题解	1
1117	Eddington Number(25)	C++题解	1
1120	Friend Numbers (20)	C++题解	1
1124	Raffle for Weibo Followers (20)	C++题解	1
1128	N Queens Puzzle (20)	C++题解	1
1128	Recommendation System（25）	C++题解	1
1139	First Contact (30)	C++题解	1
1144	The Missing Number (20)	C++题解	1
1148	Werewolf - Simple Version (20)	C++题解	1
1149	Dangerous Goods Packaging(25)	C++题解	1
1154	Vertex Coloring (25)	C++题解	1

3、进制转换(4题)

\quad 进制转换作为基本操作，会在pat中有所体现，一般以简单题为主，或者是作为其他类型题的一小部分，知道怎么把十进制数转化成任意进制数和把任意进制数转化为十进制数即可。
\quad 将p进制数x转化为10进制数

int to_dec(int x, int p)
{
	int res = 0, product = 1;  // product在循环中会不断乘p，得到1,p,p^2,p^3...
	while(x)
	{
		res += (x%10)*product;
		x /= 10;
		product *= p;
	}
	return res;
}

\quad 将10进制数x转化为p进制数

string dec_to(int x, int p)
{
	string res = "";
	do
	{
		int t = x%p;
		res += (t+'0');
		x /= p;
	}while(x);
	reverse(res.begin(), res.end());
	return res;
}

编号	标题	题解	难度等级	备注
1019	General Palindromic Number (20)	C++题解	1
1027	Colors in Mars (20)	C++题解	1
1058	A+B in Hogwarts (20)	C++题解	1
1100	Mars Numbers (20)	C++题解	2

4、图形输出(1题)

\quad 这种题不常考，且较为简单，不用花额外精力去攻克。

编号	标题	题解	难度等级	备注
1031	Hello World for U (20)	C++题解	1

5、查找元素(3题)

\quad 查找元素的题均为简单题，按要求查找最大或者最小即可。

编号	标题	题解	难度等级	备注
1006	Sign In and Sign Out (25 分)	C++题解	1
1011	World Cup Betting (20)	C++题解	1
1036	Boys vs Girls (25)	C++题解	1

二、排序(14题)

编号	标题	题解	难度等级	备注
1012	The Best Rank (25)	C++题解	3	成绩分科目排序
1025	PAT Ranking (25 )	C++题解	2	成绩分考场排序
1029	Median (25)	C++题解	3	优先队列解决内存溢出
1055	The World’s Richest (25)	C++题解	1
1062	Talent and Virtue (25)	C++题解	1
1075	PAT Judge (25)	C++题解	1
1080	Graduate Admission (30)	C++题解	1
1083	List Grades (25)	C++题解	1
1089	Insert or Merge (25)	C++题解	2	插入排序和归并排序
1098	Insertion or Heap Sort (25)	C++题解	2	插入排序和堆排序
1101	Quick Sort (25)	C++题解	2	快速排序的另一种思考
1137	Final Grading (25)	C++题解	1
1141	PAT Ranking of Institutions (25)	C++题解	1
1153	Decode Registration Card of PAT (25)	C++题解	1

三、散列(哈希)(11题)

编号	标题	题解	难度等级	备注
1039	Course List for Student (25)	C++题解	1
1041	Be Unique (20)	C++题解	1
1050	String Subtraction (20)	C++题解	1
1078	Hashing (25)	C++题解	2
1084	Broken Keyboard (20)	C++题解	1
1092	To Buy or Not to Buy (20)	C++题解	1
1112	Stucked Keyboard (20)	C++题解	2
1116	Let’s C (20)	C++题解	1
1121	Damn Single (25)	C++题解	1
1134	Vertex Cover (25)	C++题解	1
1145	Hashing - Average Search Time (25)	C++题解	3

四、贪心(5题)

编号	标题	题解	难度等级	备注
1033	To Fill or Not to Fill(30)	C++题解	1
1037	Magic Coupon (25)	C++题解	1
1067	Sort with Swap(0,*) (25)	C++题解	1
1070	Mooncake (25)	C++题解	1
1125	Chain the Ropes (25)	C++题解	1

五、二分(4题)

编号	标题	题解	难度等级	备注
1010	Radix (25)	C++题解	1
1044	Shopping in Mars (25)	C++题解	1
1048	Find Coins (25)	C++题解	1
1085	Perfect Sequence (25)	C++题解	1

六、数论(12题)

1、最大公约数(gcd)和最小公倍数(lcm)

2、素数

编号	标题	题解	难度等级	备注
1015	Reversible Primes (20)	C++题解	1
1152	Google Recruitment	C++题解	1

3、分数运算

编号	标题	题解	难度等级	备注
1081	Rational Sum (20)	C++题解	1
1088	Rational Arithmetic (20)	C++题解	1

4、质因子分解

编号	标题	题解	难度等级	备注
1059	Prime Factors (25)	C++题解	1

5、大整数运算

编号	标题	题解	难度等级	备注
1023	Have Fun with Numbers (20)	C++题解	1
1024	Palindromic Number (25)	C++题解	1
1136	A Delayed Palindrome (20)	C++题解	1

6、其他

编号	标题	题解	难度等级	备注
1069	The Black Hole of Numbers (20)	C++题解	1
1093	Count PAT’s (25)	C++题解	1
1104	Sum of Number Segments (20)	C++题解	1
1113	Integer Set Partition (25)	C++题解	1

七、栈和队列(1题)

编号	标题	题解	难度等级	备注
1051	Pop Sequence (25)	C++题解	1

八、链表(6题)

编号	标题	题解	难度等级	备注
1028	List Sorting (25)	C++题解	1
1032	Sharing (25)	C++题解	1
1052	Linked List Sorting (25)	C++题解	1
1074	Reversing Linked List (25)	C++题解	1
1097	Deduplication on a Linked List (25)	C++题解	1
1133	Splitting A Linked List (25)	C++题解	1

九、搜索(DFS和BFS)(2题)

编号	标题	题解	难度等级	备注
1091	Acute Stroke (30)	C++题解	1
1103	Integer Factorization (30)	C++题解	1
1131	Subway Map(30)	C++题解	1

十、树(23题)

1、树的遍历

编号	标题	题解	难度等级	备注
1004	Counting Leaves (30)	C++题解	2	树的层次遍历
1053	Path of Equal Weight (30)	C++题解	3	树的路径问题
1079	Total Sales of Supply Chain (25)	C++题解	2	树的遍历
1090	Highest Price in Supply Chain (25)	C++题解	1
1094	The Largest Generation (25)	C++题解	2	树的遍历
1102	Invert a Binary Tree (25)	C++题解	2	静态建树和遍历
1106	Lowest Price in Supply Chain (25)	C++题解	1
1110	Complete Binary Tree (25)	C++题解	2	判断是否是完全二叉树
1115	Counting Nodes in a BST (30)	C++题解	2	统计每一层节点个数
1130	Infix Expression(25)	C++题解	2	树的中序遍历和中缀表达式
1138	Postorder Traversal (25)	C++题解	1
1143	Lowest Common Ancestor (30)	C++题解	1
1151	LCA in a Binary Tree(30)	C++题解	1

2、树的重建

编号	标题	题解	难度等级	备注
1020	Tree Traversals (25)	C++题解	1
1043	Is It a Binary Search Tree (25)	C++题解	1
1064	Complete Binary Search Tree(30)	C++题解	1
1086	Tree Traversals Again (25)	C++题解	1
1099	Build A Binary Search Tree (30)	C++题解	1
1119	Pre- and Post-order Traversals (30)	C++题解	1
1127	ZigZagging on a Tree (30)	C++题解	1

3、平衡二叉树

编号	标题	题解	难度等级	备注
1066	Root of AVL Tree (25)	C++题解	1
1123	Is It a Complete AVL Tree (30)	C++题解	1
1135	Is It A Red-Black Tree(30)	C++题解	1

十一、图(17题)

1、图遍历和连通分量

编号	标题	题解	难度等级	备注
1013	Battle Over Cities (25)	C++题解	2	图连通分量计数
1021	Deepest Root (25)	C++题解	3	树的最大深度
1034	Head of a Gang (30)	C++题解	4	图遍历
1076	Forwards on Weibo (30)	C++题解	2	图的BFS

2、最短路径

\quad 图的最短路径是常考题，在PAT里面属于最后一二题位置，难度较高。我对两种常见的最短路算法

• 优先队列优化的Dijistra，无负权的情况下使用，$O(n+m)log(n)$
• SPFA，有负权情况下使用，$O(kE)$，k一般小于2，但可通过构造数据卡成$O(VE)$

\quad PAT对时间复杂度要求很低，无需优化即可通过，甚至Floyd都能过，所以题解中我统一使用spfa，原因是spfa跟图的BFS写法差不多，写起来简单。
\quad 我在博客中对这两种最短路算法进行了解释并给出了模板，欢迎点击查看。

编号	标题	题解	难度等级	备注
1003	Emergency (25)	C++题解	3	最短路径+其他变量的更新(第二标尺)
1018	Public Bike Management (30)	C++题解	4	最短路径+DFS
1030	Travel Plan (30)	C++题解	3	最短路径+其他变量的更新(第二标尺)
1072	Gas Station (30)	C++题解	3	多个点的最短路
1087	All Roads Lead to Rome (30)	C++题解	4	最短路径+三个标尺层层更新
1111	Online Map (30)	C++题解	3	最短路径+两个尺度

3、新定义类型题

编号	标题	题解	难度等级	备注
1122	Hamiltonian Cycle (25)	C++题解	1
1126	Eulerian Path (25)	C++题解	1
1142	Maximal Clique (25)	C++题解	1
1150	Travelling Salesman Problem (25)	C++题解	1

4、拓扑排序

编号	标题	题解	难度等级	备注
1146	Topological Order (25)	C++题解	1

5、最小生成树

十二、动态规划(4题)

编号	标题	题解	难度等级	备注
1007	Maximum Subsequence Sum (25)	C++题解	2	最大子序列和
1045	Favorite Color Stripe (30)	C++题解	1
1068	Find More Coins(30)	C++题解	1
1142	Maximal Clique (25)	C++题解	1

十三、堆(2题)

编号	标题	题解	难度等级	备注
1047	Heaps (30)	C++题解	1
1055	Heap Paths (30)	C++题解	1

十四、并查集(3题)

编号	标题	题解	难度等级	备注
1107	Social Clusters (30)	C++题解	1
1114	Family Property (25)	C++题解	1
1118	Birds in Forest (25)	C++题解	1

十五、树状数组(1题)

编号	标题	题解	难度等级	备注
1057	Stack (30)	C++题解	1