PAT甲级题型分类

按题型分类刷A1000-A1155

1. 入门模拟

题号	题目	分值
A1002	A+B for Polynomials 原题 解析	25
A1009	Product of Polynomials 原题 解析	25
A1042	Shuffling Machine 原题 解析	20
A1046	Shortest Distance 原题 解析	20
A1065	A+B and C (64bit) 原题 解析	20

2. 查找元素

题号	题目	分值
A1006	Sign In and Sign Out 原题 解析	25
A1011	World Cup Betting 原题 解析	20
A1036	Boys vs Girls 原题 解析	25

3. 图形输出

题号	题目	分值
A1031	Hello World for U 原题 解析	20

4. 进制转换

题号	题目	分值
A1019	General Palindromic Number 原题 解析	20
A1027	Colors in Mars 原题 解析	20
A1058	A+B in Hogwarts 原题 解析	20

5. 字符串处理

char str[]

#include<string>

题号	题目	分值
A1001	A+B Format 原题 解析	20
A1005	Spell it Right 原题 解析	20
A1035	Password 原题 解析	20
A1061	Dating 原题 解析	20
A1073	Scientific Notation 原题 解析	20
A1077	Kuchiguse 原题 解析	20
A1082	Read Number in Chinese 原题 解析	25

6. 排序

• 建立结构体
• #include<algorithm>用sort方法排序

题号	题目	分值
A1012	The Best Rank 原题 解析	25
A1016	Phone Bills 原题 解析	25
A1025	PAT Ranking 原题 解析	25
A1028	List Sorting 原题 解析	25
A1055	The World’s Richest 原题 解析	25
A1062	Talent and Virtue 原题 解析	25
A1075	PAT Judge 原题 解析	25
A1080	Graduate Admission 原题 解析	30
A1083	List Grades 原题 解析	25
A1095	Cars on Campus 原题 解析	30

7. 散列

• hashTable[x]=true 表示x出现过

• H(key)=key%mod Linear线性，Quadratic平方探测

• H(P) = x*range+y 表示(x,y)的存在性

• char可以直接用int表示，ASCII码[0,127]，故可以直接exist[str[i]]++；

题号	题目	分值
A1041	Be Unique 原题 解析	20
A1048	Find Coins 原题 解析	25
A1050	String Subtraction 原题 解析	20
A1084	Broken Keyboard 原题 解析	20
A1092	To Buy or Not to Buy 原题 解析	20

8. 递归

9. 贪心

题号	题目	分值
A1033	To Fill or Not to Fill 原题 解析	25
A1037	Magic Coupon 原题 解析	25
A1038	Recover the Smallest Number 原题 解析	30
A1067	Sort with Swap(0, i) 原题 解析	25
A1070	Mooncake 原题 解析	25

10. 二分

• [left,right] 内查找一个数

  while(left<=right) 返回A[mid]

  当left>right时，说明不存在，返回-1

• [left,right) 内查找>=x或<=x的数

  while(left<right)

  当left=right时，说明找到数应该所在的位置 return A[left]

• (left,right] 内查找一个数

  while(left+1<right)

  return A[right]

• 计算函数值

  while(right-left>eps){ if(f(mid)>0){right=mid;} else{left= mid;} return mid;}

题号	题目	分值
A1010	Radix 原题 解析	25
A1044	Shopping in Mars 原题 解析	25
A1048	Find Coins 原题 解析	25
A1085	Perfect Sequence 原题 解析	25

11. two points

题号	题目	分值
A1029	Median 原题 解析 中位数(n+m-1)/2	25
A1048	Find Coins 原题 解析	25
A1085	Perfect Sequence 原题 解析	25
A1089	Insert or Merge 原题 解析	25
A1098	Insertion or Heap Sort 原题 解析	25

12. 打表

空间换时间，预先存储所有结果

13. 递推

通过该位两侧结果计算得到

题号	题目	分值
A1093	Count PAT’s 原题 解析	25
A1101	Quick Sort 原题 解析	25

14. 简单数学

题号	题目	分值
A1008	Elevator 原题 解析	20
A1049	Counting Ones 原题 解析	30
A1069	The Black Hole of Numbers 原题 解析	20
A1104	Sum of Number Segments 原题 解析	20

15. 分数的四则运算

题号	题目	分值
A1081	Rational Sum 原题 解析	20
A1088	Rational Arithmetic 原题 解析	20

16. 素数

题号	题目	分值
A1015	Reversible Primes 原题 解析	20
A1078	Hashing 原题 解析	25

17. 质因子分解

题号	题目	分值
A1059	Prime Factors 原题 解析	25
A1096	Consecutive Factors 原题 解析	20

18. 大整数运算

高位存储高位

题号	题目	分值
A1023	Have Fun with Numbers 原题 解析	20
A1024	Palindromic Number 原题 解析	25

19. STL

• vector

  push_back, pop_back, insert(v.begin()+2,-1) => v[2]=-1, erase(v.begin()+2)->删除v[2], erase[first,right)

• set

  insert, size, erase(value), erase(it), erase[first,right), find(value), clear()

• string

  char[]->string.c_str(), insert(pos,string), insert(it,str2.begin(),str2.end()), erase[first,right), erase(pos,length), substr(pos,length)

• priority_queue

  top(), push(), pop()

  priority_queue<int,vector<int>,greater<int>> q; 从小到大排序priority_queue<int,vector<int>,less<int>> q; 从大到小排序

  friend bool operator < (const node &a, const node &b){ return a.id<b.id;}

• pair

  pair<string,int> p("haha",5), p=make_pair("haha",5), p.first,p.second

题号	题目	分值
A1022	Digital Library 原题 解析	30
A1039	Course List for Student 原题 解析 map会超时	25
A1047	Student List for Course 原题 解析	25
A1054	The Dominant Color 原题 解析	20
A1060	Are They Equal 原题 解析	25
A1063	Set Similarity 原题 解析	25
A1071	Speech Patterns 原题 解析	25
A1100	Mars Numbers 原题 解析	20

20. 数据结构

题号	题目	分值
A1051	Pop Sequence 原题 解析	25
A1056	Mice and Rice 原题 解析	25