PAT甲级目录&刷题记录
PAT的官网甲级题目https://pintia.cn/problem-sets/994805342720868352/problems/type/7
日沉云起的PAT题解(https://blog.csdn.net/richenyunqi/article/details/84981078)
2020年复旦上机复试题解
北大算法设计-屈婉玲
计算机调剂院校信息
郑大复试考数据库、C语言上机
广工考C语言笔试
PS:图像方面:tensorflow.org里有介绍一个手写字符体识别的实现,深度学习框架,无脑点的keras试下一个模型也行,复试吹原理。
蓝桥项目
@离散数学刷题
全域关系、恒等关系、集合法、关系图,关系的性质(自反、反自反、对称、反对称、传递)(3月3日)
关系的基本运算、符合/逆/幂/闭包运算,等价关系&等价类,及其对应课后题(3月4日)
商集、划分,相容关系&偏序关系,即完成第二章剩下课后习题(3月5日)
第3章函数,单射、满射、双射,复合运算、逆运算及其课后题(3月6日)
第4章命题逻辑析取式、合取式,主析取范式、主合取范式简单证明推理,构造证明推理(3月7日)
第5章谓词逻辑(3月8日)
谓词公式的自由变元、约束变元,变元替换、前束范式、永真蕴含式,推理证明(3月9日)
代数系统(唯一性、全域性、封闭性)等幂元、幺元、零元、逆元、可消去元,同构、(满)同态映射(3月10日)
半群定义性质、含幺半群、群的同态映射,群的生成元&非平凡子群(3月11日)
完成离散数学的学习(3月20日)
@软件工程刷题
@数据库刷题
左联结(3月5日)
@上机编程刷题
特殊题1(动规/模拟):1007(动规,最大连续子序列和)、1014(queue的应用)、1017(模拟)、1026(模拟)、1040(动规)、1045(动规)、1068(01背包)。
特殊题2(有时间再做):1010(二分)、1016(排序)、1033(贪心)、1056(queue)、1057(数状数组)、1066(AVL树)、1123(AVL树)。
A1126(连通图)第三个测试点不过得20分(1月3日)
B1009康康还有没有其他方法,用getline(1月4日)
A1025,排序题(1月5日)
A1084,哈希散列(1月6日)
全排列,n皇后,A1037贪心(1月7日)
A1010二分法,第一个测试点不过22分,(1月8日)
——边界处理:N2进制的下界为所有数位中最大的那个加1,上界=max{下界,N2的十进制}+1—假设已知的是N1的进制。可以举栗子:N1=6(10进制),N2=110(求是多少进制时和N1的十进制相同),按照上面的上下界则是2~7,2=1+1,7=max{2,6}+1,上界相当于在N1的最大的数位的基础上加1(毕竟题目问的是满足条件的最小进制)。
A1089,two pointers,模拟归并&插入排序,归并用非递归即可(merge也改为sort),A1093,递推&逻辑题(1月9日)
A1101,快排的找主元(1月10日)
A1039、A1047,用了vector,A1022用了map(1月11日)
STL的queue、priority_queue、stack、pair、algorithm的常见用法(1月12日)
A1051模拟入栈出栈合法stack、A1032最早公共结点,用flag标记第一链表, A1052根据data排序链表,不用修改next而直接输出[i+1].address,第四个测试点错即得22/25(1月13日)
DFS和BFS(1月14日)
A1103 DFS求平方和,保证字典序大的序列优先被选中,让index从大到小递减来遍历;A1091 BFS三维;二叉树的递归定义、存储结构、查找插入结点、创建二叉树、完全二叉树的存储结构 、二叉树的先中后序&层次遍历——熟悉模板(1月15日)
熟悉(静态)二叉树/树的层次遍历&统计layer模板(1月16日)
A1079,A1090,A1094,树的DFS,前两题到达根结点要“更新”,1094计算每层的结点个数,有几题类似的题没做:A1106求最小深度、A1004求每层的叶结点数。(1月17日)
A1053、二叉查找树1题、并查集&堆的模板、图定义&存储(1月18日)
要学10.2图的存储、10.3图的遍历 A1034 DFS(1月19日)
A1076 图的BFS,下标一定要细心,另外要会用结构体内构造函数&在外部初始化(1月20日)
Floyd算法+Prim算法模板+prim的上机题,dp开头,leetcode 322找零钱DP(1月21日)
01背包问题,力扣62-不同路径(1月22日)
听完侯卫东视频,做简单题呜呜呜(1月23日)
ubuntu崩了最后重启网络服务,配置固定IP后终于能上网了(1月24日)
学习socket编程的select和epoll(1月25日)
闲置队列——2020排队打饭题、【1053】Path of Equal Weight。
1.按题型分类
题型分类 | 对应题号 |
---|---|
简单排序 | 1012、1025、1026、1028、1055、1062、1075、1080、1083、1095、1098、1101、1113、1125、1146、1153 |
树的遍历 | 1053、1086、1090、1102、1106、1115、1119、1038、1147、1151(LCA算法) |
字符串的处理 | 1001、1005、1035、1061、1073、1077、1082、1108、1140、1152 |
map、STL | 1022、1054、1071、1095、1100、1154、1112、1124、1037、1141、1144、1153 |
set、STL | 1063、1120、1121、1129、1149 |
vector、STL | 1039、1047 |
DFS、BFS、层序遍历 | 1004、1018、1021、1076、1079、1087、1091、1094、1103、1106、1127、1130、1131 |
简单模拟题 | 1002、1009、1042、1046、1065、 1105 |
链表操作 | 1032、1052、1074、1097、1133 |
Dijikstra算法题 | 1003、1018、1030、1072、1087、1111 |
Hash表 | 1041、1048、1050、1084、1092、1134、1145 |
逻辑题 | 1093、1096、1109、1116、1117、1128 |
贪心算法 | 1037、1038、1067、1070、1125 |
图的遍历 | 1013、1021、1034 |
简单图论 | 1122、1142、1150 |
二叉排序树BST | 1043、1064、1099 |
并查集 | 1107、1114 、1118 |
Two pointers | 1029、1085、1089 |
查找元素 | 1006、1011、1036 |
二分法 | 1044、1085 |
回文数 | 1019 |
栈的模拟 | 1051 |
进制的转化 | 1027、1058 |
图形打印 | 1031 |
二次方探查法 | 1078 |
完全二叉树 | 1110 |
二叉树遍历,后序+中序转层序 | 1020 |
连通图 | 1126(20/25) |
红黑树 | 1135 |
回溯 | 1155 |
非常规题 | 1136、1139、1143、1148 |
纯数学问题(及以下) | 1008、1049、1069、1104、1132 |
素数 | 1015 |
素数表的建立 | 1059 |
科学计数法 | 1060 |
分数四则运算 | 1081、1088 |
大整数运算 | 1023、1024 |
2.按题号顺序
编号 |
标题 | 题解 | 分类 | 备注 |
1001 | A+B Format | C++ | 字符串处理 | |
1002 | A+B for Polynomials | C++ | 中级模拟+散列 | 多项式求和问题 |
1003 | Emergency | C++ | 图 | 最短路径问题 |
1004 | Counting Leaves | C++ | 树 | 树的遍历问题 |
1005 | Spell It Right | C++ | 字符串处理 | |
1006 | Sign In and Sign Out | C++ | 查找元素 | |
1007 | Maximum Subsequence Sum | C++ | 动态规划 | 最大连续子序列和问题 |
1008 | Elevator | C++ | 简单模拟 | |
1009 | Product of Polynomials | C++ | 简单模拟 | 多项式乘法问题 |
1010 | Radix | C++ | 进制转换+二分查找 | |
1011 | World Cup Betting | C++ | 查找元素 | |
1012 | The Best Rank | C++ | 排序、常用stl | |
1013 | Battle Over Cities | C++ | 图、并查集 | 连通分量问题 |
1014 | Waiting in Line | C++ | 复杂模拟 | |
1015 | Reversible Primes | C++ | 素数+进制转换 | |
1016 | Phone Bills | C++ | 复杂模拟 | |
1017 | Queueing at Bank | C++ | 复杂模拟 | |
1018 | Public Bike Management | C++ | 图 | 最短路径问题 |
1019 | General Palindromic Number | C++ | 进制转换 | 回文问题 |
1020 | Tree Traversals | C++ | 树 | 根据遍历序列重建树问题 |
1021 | Deepest Root | C++ | 图+树、并查集 | 连通分量问题 |
1022 | Digital Library | C++ | 常用stl | map的用法 |
1023 | Have Fun with Numbers | C++ | 大整数运算 | |
1024 | Palindromic Number | C++ | 大整数运算 | 回文问题 |
1025 | PAT Ranking | C++ | 排序 | |
1026 | Table Tennis | C++ | 复杂模拟 | |
1027 | Colors in Mars | C++ | 进制转换 | |
1028 | List Sorting | C++ | 排序 | |
1029 | Median | C++ | 排序、two pointers | |
1030 | Travel Plan | C++ | 图 | 最短路径问题 |
1031 | Hello World for U | C++ | 图形输出 | |
1032 | Sharing | C++ | 链表 | |
1033 | To Fill or Not to Fill | C++ | 贪心 | |
1034 | Head of a Gang | C++ | 图、并查集 | 连通分量问题 |
1035 | Password | C++ | 字符串处理 | |
1036 | Boys vs Girls | C++ | 查找元素 | |
1037 | Magic Coupon | C++ | 贪心 | |
1038 | Recover the Smallest Number | C++ | 字符串处理 | |
1039 | Course List for Student | C++ | 散列+常用stl | vector+sort |
1040 | Longest Symmetric String | C++ | 字符串处理 | 回文子串 |
1041 | Be Unique | C++ | 散列 | |
1042 | Shuffling Machine | C++ | 简单模拟 | |
1043 | Is It a Binary Search Tree | C++ | 树 | 根据遍历序列重建树问题 |
1044 | Shopping in Mars | C++ | 二分查找、two pointers | |
1045 | Favorite Color Stripe | C++ | 动态规划 | LIS、LCS |
1046 | Shortest Distance | C++ | 简单模拟 | |
1047 | Student List for Course | C++ | 常用stl | |
1048 | Find Coins | C++ | 二分查找、two pointers、散列 | |
1049 | Counting Ones | C++ | 数学 | 找规律 |
1050 | String Subtraction | C++ | 散列 | |
1051 | Pop Sequence | C++ | 简单模拟 | |
1052 | Linked List Sorting | C++ | 链表 | |
1053 | Path of Equal Weight | C++ | 树 | |
1054 | The Dominant Color | C++ | 简单模拟 | |
1055 | The World’s Richest | C++ | 排序 | |
1056 | Mice and Rice | C++ | 中级模拟+常用stl | 队列的应用 |
1057 | Stack | C++ | 树状数组 | |
1058 | A+B in Hogwarts | C++ | 进制转换 | |
1059 | Prime Factors | C++ | 素数 | |
1060 | Are They Equal | C++ | 字符串处理 | |
1061 | Dating | C++ | 字符串处理 | |
1062 | Talent and Virtue | C++ | 排序 | |
1063 | Set Similarity | C++ | 常用stl | set的用法 |
1064 | Complete Binary Search Tree | C++ | 树 | 根据遍历序列重建树问题 |
1065 | A+B and C (64bit) | C++ | 简单模拟 | |
1066 | Root of AVL Tree | C++ | 树 | AVL树 |
1067 | Sort with Swap(0,*) | C++ | 贪心 | |
1068 | Find More Coins | C++ | 动态规划 | 0-1背包问题 |
1069 | The Black Hole of Numbers | C++ | 数学 | |
1070 | Mooncake | C++ | 贪心 | |
1071 | Speech Patterns | C++ | 字符串处理 | |
1072 | Gas Station | C++ | 图 | 最短路径问题 |
1073 | Scientific Notation | C++ | 字符串处理 | |
1074 | Reversing Linked List | C++ | 链表 | |
1075 | PAT Judge | C++ | 排序 | |
1076 | Forwards on Weibo | C++ | 图 | 图的遍历 |
1077 | Kuchiguse | C++ | 字符串处理 | |
1078 | Hashing | C++ | 散列 | |
1079 | Total Sales of Supply Chain | C++ | 树 | 树的遍历 |
1080 | Graduate Admission | C++ | 排序 | |
1081 | Rational Sum | C++ | 分数 | |
1082 | Read Number in Chinese | C++ | 字符串处理 | |
1083 | List Grades | C++ | 排序 | |
1084 | Broken Keyboard | C++ | 散列 | |
1085 | Perfect Sequence | C++ | 二分查找、two pointers | |
1086 | Tree Traversals Again | C++ | 树 | 根据遍历序列重建树问题 |
1087 | All Roads Lead to Rome | C++ | 图 | 最短路径问题 |
1088 | Rational Arithmetic | C++ | 分数 | |
1089 | Insert or Merge | C++ | 排序算法 | |
1090 | Highest Price in Supply Chain | C++ | 树 | 树的遍历 |
1091 | Acute Stroke | C++ | 图 | 连通分量问题 |
1092 | To Buy or Not to Buy | C++ | 散列 | |
1093 | Count PAT’s | C++ | 动态规划 | |
1094 | The Largest Generation | C++ | 树 | 树的遍历 |
1095 | Cars on Campus | C++ | 复杂模拟 | 应用了多种stl |
1096 | Consecutive Factors | C++ | 数学 | |
1097 | Deduplication on a Linked List | C++ | 链表 | |
1098 | Insertion or Heap Sort | C++ | 排序算法 | |
1099 | Build A Binary Search Tree | C++ | 树 | 根据遍历序列重建树问题 |
1100 | Mars Numbers | C++ | 进制转换+字符串处理 | |
1101 | Quick Sort | C++ | 动态规划 | |
1102 | Invert a Binary Tree | C++ | 树 | 树的遍历 |
1103 | Integer Factorization | C++ | 搜索 | DFS搜索 |
1104 | Sum of Number Segments | C++ | 数学 | |
1105 | Spiral Matrix | C++ | 中级模拟 | |
1106 | Lowest Price in Supply Chain | C++ | 树 | 树的遍历 |
1107 | Social Clusters | C++ | 并查集 | |
1108 | Finding Average | C++ | 字符串处理 | |
1109 | Group Photo | C++ | 排序+中级模拟 | |
1110 | Complete Binary Tree | C++ | 树 | 判断是否是完全二叉树 |
1111 | Online Map | C++ | 图 | 最短路径问题 |
1112 | Stucked Keyboard | C++ | 散列 | |
1113 | Integer Set Partition | C++ | 数学 | |
1114 | Family Property | C++ | 并查集 | |
1115 | Counting Nodes in a BST | C++ | 树 | 构建二叉查找树+树的遍历 |
1116 | Come on! Let’s C | C++ | 散列 | |
1117 | Eddington Number | C++ | 中级模拟 | |
1118 | Birds in Forest | C++ | 并查集 | |
1119 | Pre- and Post-order Traversals | C++ | 树 | 根据遍历序列重建树问题 |
1120 | Friend Numbers | C++ | 常用stl | |
1121 | Damn Single | C++ | 散列+常用stl | |
1122 | Hamiltonian Cycle | C++ | 图 | 哈密顿环 |
1123 | Is It a Complete AVL Tree | C++ | 树 | AVL树 |
1124 | Raffle for Weibo Followers | C++ | 中级模拟 | |
1125 | Chain the Ropes | C++ | 贪心 | |
1126 | Eulerian Path | C++ | 图 | 欧拉回路、欧拉环游 |
1127 | ZigZagging on a Tree | C++ | 树 | 根据遍历序列重建树问题 |
1128 | N Queens Puzzle | C++ | 简单模拟 | |
1129 | Recommendation System | C++ | 中级模拟 | set应用 |
1130 | Infix Expression | C++ | 树 | 中缀表达式 |
1131 | Subway Map | C++ | 图 | 最短路径问题 |
1132 | Cut Integer | C++ | 字符串处理 | |
1133 | Splitting A Linked List | C++ | 链表 | |
1134 | Vertex Cover | C++ | 散列 | |
1135 | Is It A Red-Black Tree | C++ | 树 | 红黑树 |
1136 | A Delayed Palindrome | C++ | 大整数运算 | 回文问题 |
1137 | Final Grading | C++ | 排序 | |
1138 | Postorder Traversal | C++ | 树 | 树的遍历问题 |
1139 | First Contact | C++ | 图 | 图的遍历 |
1140 | Look-and-say Sequence | C++ | 字符串处理 | |
1141 | PAT Ranking of Institutions | C++ | 排序 | |
1142 | Maximal Clique | C++ | 图 | |
1143 | Lowest Common Ancestor | C++ | 树 | 最近公共祖先(LCA)问题 |
1144 | The Missing Number | C++ | 常用stl | unordered_set |
1145 | Hashing - Average Search Time | C++ | 散列 | |
1146 | Topological Order | C++ | 图 | 拓扑排序 |
1147 | Heaps | C++ | 树 | 堆 |
1148 | Werewolf - Simple Version | C++ | 简单模拟 | 暴力枚举 |
1149 | Dangerous Goods Packaging | C++ | 常用stl | |
1150 | Travelling Salesman Problem | C++ | 图 | 巡回售货商问题 |
1151 | LCA in a Binary Tree | C++ | 树 | 最近公共祖先(LCA)问题 |
1152 | Google Recruitment | C++ | 素数 | |
1153 | Decode Registration Card of PAT | C++ | 排序 | |
1154 | Vertex Coloring | C++ | 排序 | |
1155 | Heap Paths | C++ | 树、二叉堆 |
文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。
原文链接:andyguo.blog.csdn.net/article/details/104437710
- 点赞
- 收藏
- 关注作者
评论(0)