/PAT

PAT AC代码及题解

Primary LanguageC++

PAT

浙大PAT考试的个人代码及题解，大部分使用C++解决（C++11），少数提供Python3代码

做题小结

大多数题目都不难，但是要做满分的话，需要学会的算法还是不少的，下面小结一下刷题中碰到的一些算法和数据结构

注意：排序部分和数据结构部分并不一定要求会编写完整实现的代码，可能会问部分的过程或者其他的形式，

可能考察的算法和题型

  • 进制转换
  • 大数
  • 模拟
  • 贪心
  • 最短路（BFS\DFS\Djistra\SPFA）、多关键字最短路、最短路的数目等
  • 排序（冒泡、快排、堆排、插入、归并等）、多关键字排序、可以同rank的排序等
  • 二分
  • 树的前序、中序、后序、层序遍历 | 根据遍历结果构造树
  • 树的重心
  • 图的遍历
  • 简单DP（这个类型就比较多了，不过目前碰到的都是很经典的DP，比如最长上升子序列、最大子序列和之类的）

可能考察的数据结构

  • 堆
  • 栈
  • 队列、优先队列
  • 链表、双向链表
  • 邻接表、邻接表
  • 并查集
  • 树状数组、线段树、平衡树