PAT练习题概览

时间:2023-02-27 14:56:19

PAT(pat.zju.edu.cn)是一个面向C/C++程序的Online Judge系统。相比ZOJ,HDOJ,POJ等ACM题库,PAT的题目非常基础,对于数据结构、算法的入门是比较有助益的。

本文按照自己的认识,给PAT advanced level做出了分类。由于很多题目实际上兼顾有多种解法和思路,我给每道题打上了tag,来应对分类的独占性局限,供大家参考。

简单题

这类题几乎不需要数据结构、算法基础,主要通过简单的逻辑流程和判断实现。

  • 1001 A+B
  • 1002 多项式相加
  • 1005 简单hash
  • 1006 选极值
  • 1008 模拟电梯
  • 1009 多项式乘法
  • 1011 选极值
  • 1019 数字/字符处理
  • 1024 数字/字符处理
  • 1027 数字/字符处理,简单hash
  • 1031 数字/字符处理
  • 1035 简单hash<!--more -->
  • 1036 选极值
  • 1037 简单模拟
  • 1040 数字/字符处理
  • 1046 数字/字符处理
  • 1050 数字/字符处理
  • 1058 数字/字符处理
  • 1060 数字/字符处理

模拟题

这类题也相对简单,需要使用到一些简单的数据结构或者相对复杂的逻辑流程实现。

  • 1022 倒排索引
  • 1023 数字/字符处理
  • 1032 链表
  • 1049 计算数字中的1
  • 1051 模拟栈
  • 1052 链表
  • 1054 dominant color
  • 1056 模拟分组淘汰赛

排队模拟

下面三道模拟题是针对排队模型处理的:

  • 1014 排队问题
  • 1017 排队问题
  • 1026 排队问题

排序模拟

这几道模拟题侧重在使用排序方法:

  • 1012 排序
  • 1016 排序,模拟电话账单计算
  • 1025 排序
  • 1028 排序
  • 1029 归并排序
  • 1038 递归,排序

时间优化

这几道题需要做好时间优化才能ac。

  • 1044 搜索,时间优化
  • 1039 倒排索引,hash,时间优化
  • 1047 倒排索引,hash,时间优化
  • 1055 排序,时间优化

素数判定

  • 1015 素数
  • 1059 素数

  • 1003 最短路径
  • 1018 最短路径
  • 1030 最短路径
  • 1034 dfs

搜索

  • 1010 二分搜索,优化剪枝
  • 1013 并查集/dfs
  • 1021 并查集,dfs,图的直径
  • 1054 dfs,优化剪枝

  • 1004 dfs,树遍历
  • 1020 二叉树遍历
  • 1043 二叉树遍历

Hash

  • 1041 hash
  • 1042 hash
  • 1048 hash

分治

  • 1007 最大子连续序列

贪心

  • 1033 贪心

动态规划

  • 1045 DP,最长递增子序列

树状数组

树状数组是一种神奇的数据结构,在1057题中其神奇的效果得到了很好的体现。

  • 1057 树状数组,模拟栈,二分搜索

题解

截止2013-08-03,PAT advanced level的60道题全部题解和代码已经发布在本博客中,链接如下:欢迎讨论大家;)

附博客的PAT专题区链接:请戳