Svaling/PAT

浙江大学PAT题解(C/C++/Java) - 努力成为萌萌的程序媛~~

耶耶耶～～PAT甲级与乙级的所有题目都已更新完成～撒花撒花～～我不管，反正我最萌～

PAT的这个仓库我一直在维护，包括每次考试后新出的题目都会第一时间更新，不出意外的话会一直更新下去，甲级部分基本都写了思路分析，做得很用心，力争做github的PAT题解仓库中最完善、最用心的，希望能帮助到大家，求star支持～

目录

• PAT甲级题解
• PAT乙级题解
• PAT团体程序设计天梯赛GPLT题解
• 致谢

PAT甲级题解

ID	Title	C/C++(附分析)	备注
1001	A+B Format (20)	查看题解	字符串处理
1002	A+B for Polynomials (25)	查看题解	模拟
1003	Emergency (25)	查看题解	Dijkstra算法
1004	Counting Leaves (30)	查看题解	BFS，DFS，树的层序遍历
1005	Spell It Right (20)	查看题解	字符串处理
1006	Sign In and Sign Out (25)	查看题解	查找元素
1007	Maximum Subsequence Sum(25)	查看题解	动态规划，最大连续子序列和
1008	Elevator (20)	查看题解	数学问题
1009	Product of Polynomials (25)	查看题解	模拟
1010	Radix (25)	查看题解	二分法
1011	World Cup Betting (20)	查看题解	查找元素
1012	The Best Rank (25)	查看题解	排序
1013	Battle Over Cities (25)	查看题解	图的遍历，统计连通分量的个数，DFS
1014	Waiting in Line (30)	查看题解	queue的应用
1015	Reversible Primes (20)	查看题解	素数
1016	Phone Bills (25)	查看题解	排序
1017	Queueing at Bank (25)	查看题解	模拟
1018	Public Bike Management (30)	查看题解	Dijkstra算法 + DFS
1019	General Palindromic Number (20)	查看题解	回文数
1020	Tree Traversals (25)	查看题解	进制转换
1021	Deepest Root (25)	查看题解	图的遍历，DFS，计算连通分量的个数
1022	Digital Library (30)	查看题解	map映射，STL的使用
1023	Have Fun with Numbers (20)	查看题解	大整数运算
1024	Palindromic Number (25)	查看题解	大整数相加
1025	PAT Ranking (25)	查看题解	排序
1026	Table Tennis (30)	查看题解	模拟，排序
1027	Colors in Mars (20)	查看题解	进制转换
1028	List Sorting (25)	查看题解	排序
1029	Median (25)	查看题解	two pointers
1030	Travel Plan (30)	查看题解	Dijkstra算法 + DFS，最短路径，边权
1031	Hello World for U (20)	查看题解	图形打印
1032	Sharing (25)	查看题解	链表
1033	To Fill or Not to Fill (25)	查看题解	贪心算法
1034	Head of a Gang (30)	查看题解	图的遍历，DFS
1035	Password (20)	查看题解	字符串处理
1036	Boys vs Girls (25)	查看题解	查找元素
1037	Magic Coupon (25)	查看题解	贪心算法
1038	Recover the Smallest Number (30)	查看题解	贪心算法
1039	Course List for Student (25)	查看题解	不定长数组vector，STL的使用
1040	Longest Symmetric String (25)	查看题解	动态规划
1041	Be Unique (20)	查看题解	Hash散列
1042	Shuffling Machine (20)	查看题解	模拟
1043	Is It a Binary Search Tree (25)	查看题解	二叉查找树BST
1044	Shopping in Mars (25)	查看题解	二分查找
1045	Favorite Color Stripe (30)	查看题解	动态规划，LIS / LCS
1046	Shortest Distance (20)	查看题解	模拟
1047	Student List for Course (25)	查看题解	不定长数组vector，STL的使用
1048	Find Coins (25)	查看题解	Hash散列
1049	Counting Ones (30)	查看题解	数学问题
1050	String Subtraction (20)	查看题解	Hash散列
1051	Pop Sequence (25)	查看题解	栈模拟
1052	Linked List Sorting (25)	查看题解	链表
1053	Path of Equal Weight (30)	查看题解	树的遍历
1054	The Dominant Color (20)	查看题解	map映射，STL的使用
1055	The World’s Richest (25)	查看题解	排序
1056	Mice and Rice (25)	查看题解	queue的用法
1057	Stack (30)	查看题解	树状数组
1058	A+B in Hogwarts (20)	查看题解	进制转换
1059	Prime Factors (25)	查看题解	素数表的建立
1060	Are They Equal (25)	查看题解	科学计数法
1061	Dating (20)	查看题解	字符串处理
1062	Talent and Virtue (25)	查看题解	排序
1063	Set Similarity (25)	查看题解	集合set，STL的使用
1064	Complete Binary Search Tree (30)	查看题解	二叉查找树BST
1065	A+B and C (64bit) (20)	查看题解	模拟
1066	Root of AVL Tree (25)	查看题解	平衡二叉树（AVL树）
1067	Sort with Swap(0,*) (25)	查看题解	贪心算法
1068	Find More Coins (30)	查看题解	01背包，动态规划
1069	The Black Hole of Numbers (20)	查看题解	数学问题
1070	Mooncake (25)	查看题解	贪心算法
1071	Speech Patterns (25)	查看题解	map映射，STL的使用
1072	Gas Station (30)	查看题解	Dijkstra算法
1073	Scientific Notation (20)	查看题解	字符串处理
1074	Reversing Linked List (25)	查看题解	链表
1075	PAT Judge (25)	查看题解	排序
1076	Forwards on Weibo (30)	查看题解	图的遍历，BFS
1077	Kuchiguse (20)	查看题解	字符串处理
1078	Hashing (25)	查看题解	二次方探查法
1079	Total Sales of Supply Chain (25)	查看题解	DFS，BFS，树的遍历
1080	Graduate Admission (30)	查看题解	排序
1081	Rational Sum (20)	查看题解	分数的四则运算
1082	Read Number in Chinese (25)	查看题解	字符串处理
1083	List Grades (25)	查看题解	排序
1084	Broken Keyboard (20)	查看题解	Hash散列
1085	Perfect Sequence (25)	查看题解	二分，two pointers
1086	Tree Traversals Again (25)	查看题解	树的遍历
1087	All Roads Lead to Rome (30)	查看题解	Dijkstra算法 + DFS，最短路径
1088	Rational Arithmetic (20)	查看题解	分数的四则运算
1089	Insert or Merge (25)	查看题解	two pointers
1090	Highest Price in Supply Chain (25)	查看题解	树的遍历
1091	Acute Stroke (30)	查看题解	广度优先搜索BFS
1092	To Buy or Not to Buy (20)	查看题解	Hash散列
1093	Count PAT’s (25)	查看题解	逻辑题
1094	The Largest Generation (25)	查看题解	BFS，DFS，树的遍历
1095	Cars on Campus (30)	查看题解	map的用法，排序
1096	Consecutive Factors (20)	查看题解	逻辑题
1097	Deduplication on a Linked List (25)	查看题解	链表
1098	Insertion or Heap Sort (25)	查看题解	heap sort（堆排序）
1099	Build A Binary Search Tree (30)	查看题解	二叉查找树BST
1100	Mars Numbers (20)	查看题解	map映射，STL的使用
1101	Quick Sort (25)	查看题解	快速排序
1102	Invert a Binary Tree (25)	查看题解	树的遍历
1103	Integer Factorization (30)	查看题解	深度优先搜索DFS
1104	Sum of Number Segments (20)	查看题解	数学问题
1105	Spiral Matrix (25)	查看题解	模拟
1106	Lowest Price in Supply Chain (25)	查看题解	DFS，BFS，树的遍历
1107	Social Clusters (30)	查看题解	并查集
1108	Finding Average (20)	查看题解	字符串处理
1109	Group Photo (25)	查看题解	逻辑题
1110	Complete Binary Tree (25)	查看题解	完全二叉树
1111	Online Map (30)	查看题解	Dijkstra算法 + DFS
1112	Stucked Keyboard (20)	查看题解	map映射，STL的使用
1113	Integer Set Partition (25)	查看题解	排序
1114	Family Property (25)	查看题解	并查集
1115	Counting Nodes in a BST (30)	查看题解	二叉树的遍历，DFS
1116	Come on! Let’s C (20)	查看题解	简单逻辑题
1117	Eddington Number(25)	查看题解	简单逻辑题
1118	Birds in Forest (25)	查看题解	并查集
1119	Pre- and Post-order Traversals (30)	查看题解	前序后序转中序
1120	Friend Numbers (20)	查看题解	set的应用
1121	Damn Single (25)	查看题解	set的应用
1122	Hamiltonian Cycle (25)	查看题解	图论
1123	Is It a Complete AVL Tree (30)	查看题解	AVL树
1124	Raffle for Weibo Followers (20)	查看题解	map映射
1125	Chain the Ropes (25)	查看题解	排序，贪心
1126	Eulerian Path (25)	查看题解	连通图
1127	ZigZagging on a Tree (30)	查看题解	中序后序建树，层序遍历

PAT乙级题解

ID	Title	C/C++	Java	备注
1001	害死人不偿命的(3n+1)猜想(15)	查看题解	查看题解	模拟
1002	写出这个数 (20)	查看题解	查看题解	字符串处理
1003	我要通过！(20)	查看题解	查看题解	数学题
1004	成绩排名 (20)	查看题解		查找元素
1005	继续(3n+1)猜想 (25)	查看题解	查看题解	Hash散列
1006	换个格式输出整数 (15)	查看题解		字符串处理
1007	素数对猜想 (20)	查看题解	查看题解	素数
1008	数组元素循环右移问题 (20)	查看题解	查看题解	模拟
1009	说反话 (20)	查看题解	查看题解	字符串处理
1010	一元多项式求导 (25)	查看题解	查看题解	模拟
1011	A+B和C (15)	查看题解	查看题解	模拟
1012	数字分类 (20)	查看题解		模拟
1013	数素数 (20)	查看题解		素数
1014	福尔摩斯的约会 (20)	查看题解	查看题解	字符串处理
1015	德才论 (25)	查看题解	查看题解	排序
1016	部分A+B (15)	查看题解	查看题解	模拟
1017	A除以B (20)	查看题解	查看题解	大整数运算
1018	锤子剪刀布 (20)	查看题解	查看题解	模拟
1019	数字黑洞 (20)	查看题解	查看题解	数学问题
1020	月饼 (25)	查看题解	查看题解	贪心算法
1021	个位数统计 (15)	查看题解		字符串处理
1022	D进制的A+B (20)	查看题解	查看题解	进制转换
1023	组个最小数 (20)	查看题解	查看题解	贪心算法
1024	科学计数法 (20)	查看题解	查看题解	字符串处理
1025	反转链表 (25)	查看题解	查看题解	链表
1026	程序运行时间(15)	查看题解	查看题解	模拟
1027	打印沙漏(20)	查看题解	查看题解	图形打印
1028	人口普查(20)	查看题解	查看题解	查找元素
1029	旧键盘(20)	查看题解	查看题解	Hash散列
1030	完美数列(25)	查看题解	查看题解	two pointers
1031	查验身份证(15)	查看题解	查看题解	字符串处理
1032	挖掘机技术哪家强(20)	查看题解	查看题解	查找元素
1033	旧键盘打字(20)	查看题解	查看题解	Hash散列
1034	有理数四则运算(20)	查看题解	查看题解	分数的四则运算
1035	插入与归并(25)	查看题解		two pointers
1036	跟奥巴马一起编程(15)	查看题解	查看题解	图形打印
1037	在霍格沃茨找零钱（20)	查看题解	查看题解	进制转换
1038	统计同成绩学生(20)	查看题解	查看题解	Hash散列
1039	到底买不买 (20)	查看题解	查看题解	Hash散列
1040	有几个PAT（25)	查看题解	查看题解	逻辑题
1041	考试座位号(15)	查看题解	查看题解	查找元素
1042	字符统计(20)	查看题解	查看题解	Hash散列
1043	输出PATest(20)	查看题解	查看题解	Hash散列
1044	火星数字(20)	查看题解	查看题解	map映射，STL的使用
1045	快速排序(25)	查看题解	查看题解	快速排序
1046	划拳(15)	查看题解	查看题解	模拟
1047	编程团体赛(20)	查看题解	查看题解	Hash散列
1048	数字加密(20)	查看题解	查看题解	字符串处理
1049	数列的片段和(20)	查看题解	查看题解	数学问题
1050	螺旋矩阵(25)	查看题解	查看题解	模拟
1051	复数乘法 (15)	查看题解	查看题解	模拟
1052	卖个萌 (20)	查看题解	查看题解	字符串处理
1053	住房空置率 (20)	查看题解	查看题解	模拟
1054	求平均值 (20)	查看题解	查看题解	字符串处理
1055	集体照 (25)	查看题解	查看题解	排序
1056	组合数的和(15)	查看题解		数学问题
1057	数零壹(20)	查看题解		进制转换
1058	选择题(20)	查看题解		字符串处理
1059	C语言竞赛(20)	查看题解		逻辑题
1060	爱丁顿数(25)	查看题解		逻辑题
1061	判断题(15)	查看题解		逻辑题
1062	最简分数(20)	查看题解		分数化简
1063	计算谱半径(20)	查看题解		逻辑题
1064	朋友数(20)	查看题解	查看题解	set的使用
1065	单身狗(25)	查看题解		逻辑题，set的使用
1066	图像过滤(15)	查看题解		逻辑题
1067	试密码(20)	查看题解		字符串
1068	万绿丛中一点红(20)	查看题解		逻辑题
1069	微博转发抽奖(20)	查看题解		map映射
1070	结绳(25)	查看题解		排序，贪心

PAT团体程序设计天梯赛GPLT题解

ID	Title	C/C++（附分析）	备注
L1-001	Hello World	查看题解	水题
L1-002	打印沙漏	查看题解	图形打印
L1-003	个位数统计	查看题解	字符串处理
L1-004	计算摄氏温度	查看题解	数学问题
L1-005	考试座位号	查看题解	查找元素
L1-006	连续因子	查看题解	逻辑题
L1-007	念数字	查看题解	字符串处理
L1-008	求整数段和	查看题解	水题
L1-009	N个数求和	查看题解	分数的四则运算
L1-010	比较大小	查看题解	水题
L1-011	A-B	查看题解	字符串处理
L1-012	计算指数	查看题解	水题
L1-013	计算阶乘和	查看题解	水题
L1-014	简单题	查看题解	水题
L1-015	跟奥巴马一起画方块	查看题解	图形打印
L1-016	查验身份证	查看题解	字符串处理
L1-017	到底有多二	查看题解	数学问题
L1-018	大笨钟	查看题解	字符串处理
L1-019	谁先倒	查看题解	逻辑题
L1-020	帅到没朋友	查看题解	集合set，STL的使用
L1-021	重要的话说三遍	查看题解	水题
L1-022	奇偶分家	查看题解	逻辑判断
L1-023	输出GPLT	查看题解	水题
L1-024	后天	查看题解	日期处理
L1-025	正整数A+B	查看题解	字符串处理
L1-026	I Love GPLT	查看题解	水题
L1-027	出租	查看题解	不定长数组vector，STL的使用
L1-028	判断素数	查看题解	素数
L1-029	是不是太胖了	查看题解	简单逻辑
L1-030	一帮一	查看题解	排序
L1-031	到底是不是太胖了	查看题解	简单逻辑
L1-032	Left-pad	查看题解	字符串处理
L1-033	出生年	查看题解	STL，集合set
L1-034	点赞	查看题解	逻辑题
L1-035	情人节	查看题解	循环
L1-036	A乘以B	查看题解	水题
L1-037	A除以B	查看题解	逻辑题
L1-038	新世界	查看题解	水题
L1-039	古风排版	查看题解	逻辑题
L1-040	最佳情侣身高	查看题解	逻辑题
L2-001	紧急救援	查看题解	Dijkstra算法
L2-002	链表去重	查看题解	链表
L2-003	月饼	查看题解	贪心算法
L2-004	这是二叉搜索树吗？	查看题解	二叉搜索树BST
L2-005	集合相似度	查看题解	集合set，STL的使用
L2-006	树的遍历	查看题解	树的遍历
L2-007	家庭房产	查看题解	并查集
L2-008	最长对称子串	查看题解	字符串处理，动态规划
L2-009	抢红包	查看题解	简单逻辑
L2-010	排座位	查看题解	并查集
L2-011	玩转二叉树	查看题解	二叉树的遍历
L2-012	关于堆的判断	查看题解	heap sort（堆排序）
L2-013	红色警报	查看题解	图的连通分量个数统计
L2-014	列车调度	查看题解	集合set，STL的使用
L2-015	互评成绩	查看题解	排序
L2-016	愿天下有情人都是失散多年的兄妹	查看题解	广度优先搜索BFS
L2-017	人以群分	查看题解	排序
L2-019	悄悄关注	查看题解	集合set
L2-020	功夫传人	查看题解	深度优先搜索DFS
L3-001	凑零钱	查看题解	01背包，动态规划
L3-002	堆栈	查看题解	树状数组
L3-003	社交集群	查看题解	并查集
L3-004	肿瘤诊断	查看题解	广度优先搜索BFS
L3-005	垃圾箱分布	查看题解	Dijkstra算法
L3-007	天梯地图	查看题解	Dijkstra算法 + DFS，最短路径
L3-008	喊山	查看题解	广度优先搜索BFS
L3-010	是否完全二叉搜索树	查看题解	完全二叉树
L3-013	非常弹的球	查看题解	物理题
L3-015	球队“食物链”	查看题解	深度优先搜索DFS

致谢

• 感谢@JoyHwong提供的Java版本的题解