PAT

Solutions for PAT

熟练掌握知识点

• 字符串
  • 模拟 熟练string相关方法的使用
    • 字符串与数字的相互准换 A1069 (sprintf()和sscanf()、c++ stringstream、c++11函数 stoi、to_string)
    • 大小写转换 tolower(), toupper() A1071
    • 模拟科学计数法 A1073
    • 对比较复杂转换规则的模拟 数字转中文读法 A1082
    • stringstream帮助分隔输入 A1100
    • sscanf和sprintf的使用
    • 思维 A1112
  • 求公共前/后缀 A1077
  • • KMP
  • 回文串Manacher
  • • 字典树
• 数学
  • 大整数模拟（推荐用Java解决）
    • 大整数加法
      • A1136
    • 大整数减法
    • 大整数乘法
    • 大整数除法
    • 对整数运算溢出的处理 A1065
  • 素数
    • 素数筛
    • 区间筛
  • 最大公约数 gcd
  • 最小公倍数
  • 合数分解 A1051
  • * 逆元
  • 快速幂
  • 矩阵快速幂
  • 蔡勒公式 随便给一个日期，就能用这个公式推算出是星期几
  • Lucas 定理 用来求C(n,m) mod p的值
  • 找规律
    • A1049 给一个数N，统计从1到N的所有数字中1出现的次数
    • A1104
  • 实现某种运算
    • 模拟科学计数法 A1060
    • 分数四则运算
      • 分数加 A1081
      • 分数四则运算 A1088 模板
• 数据结构
  • 线性表
    • 链表模拟
      • 逆转 A1074
      • 合并 A1133
      • 排序 A1052
      • 增删改查 A1133 A1097
      • A1032
      • tips:根据pat考察的惯用格式，并不需要完全模拟实现链表，只需要在功能上模拟其作用即可，可以利用vector储存链表结点，然后直接对vector进行操作，最后按照链表格式输出处理后的vector即可
      • * 使用指针模拟
  • 栈
    • 中缀转后缀表达式
    • 后缀表达式运算
    • 模拟栈，实现较高级应用 A1057
    • 单调栈
  • 队列
    • 模拟排队
    • A1056
  • 堆
    • 最大堆, 最小堆 实现，概念，性质
      • A1147（注意边界）
      • A1155
    • 主要是下滤操作, 需要重点注意 percDown
    • priority_queue
    • heapsort A1098
  • 集合set, unordered_set
    • A1063
    • 重构set中的"<"运算符，以达到自动排序效果 A1129
    • A1134
  • 哈希散列
    • 平方探测法 A1078
    • 平均搜索时间 A1145
• 图论
  • 最短路问题
    • Dijkstra 单源最短路 -[x] A1111
    • Dijkstra+ 堆优化
    • 单源最短路 bellman ford 算法 可以处理负边权图
    • SPFA
    • 多源最短路 Floyd Warshall 算法
  • 判断拓扑排序 A1146
  • 拓扑排序
  • 欧拉通路、回路，哈密顿通路、回路
    • 判断所给的点是否构成哈密顿图 A1122 概念
    • 判断这个图是否含有欧拉路,欧拉回路 A1126 注意判断连通性
      • 如果有0个或者2个点的度数为奇数，那么一定含有欧拉路。如果有0个点度数为奇数，那么一定含有欧拉回路
  • 关键路径
  • 树
    • 遍历
      • 先序遍历 递归、非递归实现
      • 后序遍历
        • 递归实现
        • 非递归实现 可用于求树中一个结点的所有祖先
      • 中序遍历 递归、非递归实现
      • 给出先序中序求后序 A1138
      • 给出后序中序求先序、层序 A1020
      • 给出先序后序求可能的中序(重要)
        • tips: 只要父亲节点只包含一个子节点，那么这个答案是不唯一的
        • A1119
      • 基础层序遍历
      • Z字形遍历 挺重要的感觉 A1127
      • 多叉树遍历
        • A1079
        • A1090
        • A1094
      • 遍历，同时记录结点重要信息 2019年春季考试 7-4 Structure of a Binary Tree（30分）
    • LCA
      • A1151
      • A1143
      • 根据最近公共祖先的概念判断的题，不考虑复杂LCA算法
    • 表达式树 2019年秋季考试 7-3 Postfix Expression (25分)
    • 给定一个表达式的二叉树形式，求中序表达式，并加括号 A1130
    • 哈夫曼树
    • 判断完全二叉树 A1123
  • 平衡树
    • 判断平衡性
      • A1123
    • 建立平衡树
      • A1066
  • 并查集
    • 基础模板
      • A1118
      • A1114
      • A1107
      • 2019年春季考试 7-3 Telefraud Detection (25分)
    • 路径优化
• 排序
  • 插入排序 A1089, A1098
  • 归并排序 A1089
  • 快速排序
    • A1101
  • 堆排序 A1098
  • 拓扑排序 基于入度的判断
    • 判断拓扑排序 A1146
• 暴力
  • 搜索
    • DFS + 剪枝优化
      • A1103
      • A1131
    • BFS
      • A1076
      • A1091
    • 多源BFS
    • Dijkstra+DFS
      • A1087
  • 经典问题
    • N皇后
      • A1128
    • 汉诺塔
    • 装载问题
    • 全排列
• 模拟题
  • 模拟科学计数法 A1060
  • A1061, A1062, A1075, A1080, A1095, A1105, A1109, A1141, A1148, A1153
• 贪心
  • A1067
  • A1070
  • A1125
• 分治
  • 二分查找系列
    • 等于
    • 大于、大于等于
    • 小于、小于等于
    • 相关stl
      • binary_search
      • lower_bound(num, num+size, x)-num:大于等于x的第一个数的下标
      • upper_bound(num, num+size, x)-num:大于x的第一个数的下标
    • A1085
    • A1121
• dp
  • 背包问题
    • 01背包+构造最优解 A1068
    • 完全背包
    • 多重背包
  • LIS 最长递增子序列
  • LCS 最长公共子序列LCS
  • 整数拆分
• STL
  • string
    • find
    • 字符串结尾 string::npos
  • vector
  • List
  • set
  • map
  • stack
  • queue
  • priority_queue 最大堆、最小堆
  • algorithm
    • max, max_element
    • min, min_element
    • lower_bound, lower_bound(begin,end,num,greater())
    • upper_bound, upper_bound(begin,end,num,greater())
    • binary_search
    • sort, stable_sort
    • fill
    • swap
    • reverse
    • next_permutation
  • numeric
    • accumulate
• C++11
  • Lambda
  • auto
  • std::to_string
  • stoi，stod，stof，stol，stold，stoll，stoul，stoull
• 优化
  • IO优化