| 题目 | 答案 | 解题关键 | 题型 |
|---|---|---|---|
| 1001 A+B Format | C++ | 从数字高位(字符串低位)开始，需要添加,的位置满足(i + 1) % 3 == len % 3 且 不是最后一位
|
|
| 1002 A+B for Polynomials | C++ | 非零系数项个数的统计 | |
| 1003 Emergency | C++ | 最短路径(Dijkstra) | |
| 1004 Counting Leaves | C++ | 1. 利用数组存储每层的叶结点个数 2. 根据出队结点的层数，获取最大层数，遍历输出每层叶结点个数 |
树的遍历（BFS） |
| 1005 Spell It Right | C++ | \ | |
| 1006 Sign In and Sign Out | C++ | 方法类似 乙级1028 人口普查 | |
| 1009 Product of Polynomials | C++ | 第二个多项式可边读边处理 | |
| 1010 Radix | C++ | 1. 基数上界为 已确认数字的十进制大小 + 1 与 下界中的较大值（确保不会出现多个解(而且基数不确定的数，只有一位数的时候才可能多个解) ) 2. 基数过大时，数值转换为十进制会发生上溢，存储结果为负数 |
二分 |
| 1011 World Cup Betting | C++ | \ | |
| 1012 The Best Rank | C++ | 1. 利用全局变量设计cmp函数 2. 通过记录所有科目的排名，最后选出最好的排名以及对应科目 3. 相同分数者排名相同，下一不同分数者排名为数组下标+1 |
|
| 1013 Battle Over Cities | C++ | 1. 问题等价于求 一个无向图去掉一个结点后，连通分量的数量 2. cin会超时，需要改为scanf，邻接矩阵和邻接表都可存储图3. 每次输入被占领的城市之前，要重置城市的访问状态为未访问 4. 将失去的城市标记为已访问，即可达到失去的效果(没有公路可以到达) |
图的遍历（DFS/BFS/并查集） |
| 1016 Phone Bills | C++ |
（待优化） 1. 通话记录统一先排序后处理 2. 连续的两个通话记录，判断是否为 同一用户 且 为先通话后挂断的状态 3. 通话时长的统计方法 4. 单位美分cents 要转换为 美元$ |
|
| 1019 General Palindromic Number | C++ | \ | |
| 1020 Tree Traversals | C++ | \ | 二叉树的遍历(后序遍历序列 + 中序遍历序列 确定二叉树；层序遍历) |
| 1025 PAT Ranking | C++ | \ | |
| 1027 Colors in Mars | C++ | \ | |
| 1028 List Sorting | C++ | \ | |
| 1030 Travel Plan | C++ | 最短路径(Dijkstra + DFS) | |
| 1031 Hello World for U | C++ | 根据 n1和n3为 |
|
| 1032 Sharing | C++ | \ | 静态链表(基于散列) |
| 1033 To Fill or Not to Fill | C++ |
能到达的距离内，由近到远遍历，有三种情况： 1. 最近距离的加油站都到不了 2. 出现油价比目前低的加油站，就直接去 2.1 油不够，只加能刚好到达的油量 2.2 不用加油 3. 没有更低价的加油站，就加满油(能尽量少加更贵的油)，去价格相对 最低的加油站 |
|
| 1034 Head of a Gang | C++ | 1. 相同人员之间可能多次通话 2. map<type1, type2>自动按type1从小到大输出，使用map<string, int>建立头目姓名与成员数量的关系，便于输出结果3. 图中可能有环，为了边权不被漏加，需要先累加边权再递归；同时为了防止边权被重复计算，累加后删除这条边，以免走回头路、重复计算边权 |
图的遍历(DFS) |
| 1035 Password | C++ | (待优化) | |
| 1036 Boys vs Girls | C++ | \ | |
| 1042 Shuffling Machine | C++ | 将扑克顺序号转为实际牌号的方式 | |
| 1043 Is It a Binary Search Tree | C++ | 1. 变长数组存储输入序列，表示二叉树 2. 根据BST左子树所有结点的数据域 < 根结点的数据域，右子树所有结点的数据域 ≥ 根结点的数据域(由输入样例得出大小关系，镜像则相反)，按照先序序列的特点(第一个结点为根结点)，获取左右子树的边界，判断是否符合先序序列，若符合，则按照左右根的顺序递归，将符合的根结点存入 vector(获取后序序列)3. 若vecotr中元素数量 = 输入序列的元素数量(能顺利转换为BST的后序序列)，说明输入序列为先序序列 |
二叉搜索树(BST) |
| 1046 Shortest Distance | C++ | 便于计算距离的方式 | |
| 1051 Pop Sequence | C++ | 1. 可能会发生堆栈溢出 2. 栈顶元素和当前需要出栈的元素相同时，出栈。该判断之前必须先判断栈是否不为空(否则会报错) 3. 标记出栈序列中待出栈元素下标，最终标记只有超出序列下标，才可能是出栈序列 |
栈 |
| 1052 Linked List Sorting | C++ | 存在无有效结点的情况 | 静态链表(基于散列) |
| 1053 Path of Equal Weight | C++ | 1. 输出的路径序列要求降序，因此在读入结点时就将孩子节点按权重降序排序，这样，之后遍历时得到的路径即为降序 2. 利用 vector的begin和end函数获得vector的首元素地址和尾后地址，用于sort函数排序3. 利用 vector存储路径，在递归子结点之前，用push_back函数将子结点加入路径，递归回溯后，用pop_back将先前加入的子结点移出路径
|
树的遍历(DFS) |
| 1055 The World's Richest | C++ | 超时问题。要求输出的人数$\leq$100，通过筛去每个年龄多余的人解决 | |
| 1056 Mice and Rice | C++ | 1. 输入的第二行是按老鼠的序号给出的重量。第三行给出的是老鼠的序号，而不是按序号给出的比赛序号 2. 用队列记录老鼠的序号(而不是记录老鼠的结构体，有利于减少内存的占用)，晋级的老鼠重新入队 3. 最后的分组中，老鼠数量可能不足(利用<cmath>中的 ceil函数向上取整) |
队列 |
| 1058 A+B in Hogwarts | C++ | 题型同 乙级1037 在霍格沃茨找零钱 单位转换过程可能会超过int范围 |
|
| 1062 Talent and Virtue | C++ | 设置flag作为考生的分类，便于所有考生统一排序 | |
| 1064 Complete Binary Search Tree | C++ | 1. 输入的元素升序排序，即为二叉树的中序遍历序列。 2. 静态写法(变长数组)按照层序存储完全二叉排序树 3. 对二叉树进行中序遍历，依次填入中序遍历序列的元素即可得到层序存储的二叉树。注意：中序遍历时，二叉树数组根结点的下标： 若设为1，则左右孩子结点下标为 root * 2和root * 2 + 2；若设为0，则左右孩子结点下标为 root * 2 + 1和root * 2 + 24. 顺序输出二叉树数组元素即为层序遍历序列 |
二叉搜索树BST |
| 1065 A+B and C (64bit) | C++ |
乙级1011 A+B 和 C 进阶版 负数相加若溢出，可能得到0 |
|
| 1066 Root of AVL Tree | C++ | 即写出平衡二叉树的代码模板 1. 新建结点的初始高度为1 2. 获取树高时，注意递归到空结点时，返回0 3. 插入结点，递归过程中从系统栈出栈后： 1) 平衡因子为2时，树型可能为LR型或LL型，LR型需要先对当前结点的左子树进行右旋；之后，LR型和LL型都需要对当前结点进行右旋 2) 平衡因子为-2时，树型可能为RL型或RR型，RL型需要先对当前结点的右子树进行左旋；之后，RL型和RR型都需要对当前结点进行左旋 4. 左旋和右旋过程中要及时更新树高 |
平衡二叉树 |
| 1070 Mooncake | C++ | 库存量和售价都应该定义为double类型 | |
| 1073 Scientific Notation | C++ | 1. 利用正则表达式，分开读取 数字部分 和 指数部分 2. 指数 < 0：整数部分必然为 0 3. 指数 >= 0： - 仍有小数点，何时输出小数点 - 没有小数点，后续输出0 |
|
| 1074 Reversing Linked List | C++ | 1. 通过数组下标来表示地址，便于链接各个节点 2. 可能存在无效结点 3. 只根据 链表顺序的地址 进行反转，有利于节约开销 |
静态链表(基于散列) |
| 1075 PAT Judge | C++ |
(待优化) 1. 不能编译的提交得分为0 2. 没有提交过的答案需要输出为 -，利用<cstring>中的memset函数，为 得分数组 赋值 -1，表示没有提交过答案3. 没有任何一题通过编译 或 没有提交过答案的人不记录排名，设置 是否有通过编译的标识，进行筛选 4. 排序以 是否有通过编译 为 第一排序条件 |
|
| 1076 Forwards on Weibo | C++ | 1. 转发是粉丝转发博主的信息，因此要根据用户的关注情况建立从博主到粉丝(即反向)的有向图 2. DFS记录访问过的结点数量比较麻烦，BFS比较方便 3. 可能形成环 ，必须控制每个用户只能转发一次(遍历时只能访问一次) |
图的遍历 |
| 1077 Kuchiguse | C++ | 1. 通过反转字符串，将后缀转换为前缀，便于比较 2. getline()之前注意读取换行符。 |
|
| 1079 Total Sales of Supply Chain | C++ | 1. 静态写法表示树，即用数组下标指代结点 2. 结点的结构体中设有货物量变量，用来判断是否为零售商（本题采用了BFS；也可DFS） |
树的遍历（BFS/DFS） |
| 1082 Read Number in Chinese | C++ | 1. 四位数字分为一节，单位为个、万、亿 2. 一节中数字全为0，则不输出节的单位 3. 节中第一个非零数之前有0，则输出1个0 |
|
| 1084 Broken Keyboard | C++ | 待优化 | |
| 1085 Perfect Sequence | C++ | \ | two pointers |
| 1086 Tree Traversals Again | C++ | 先序序列相当于入栈次序；中序序列相当于出栈次序 | 二叉树的遍历(先序遍历序列 + 中序遍历序列 确定二叉树；后序遍历) |
| 1089 Insert or Merge | C++ | 1. 插入排序：未排序部分和初始序列一定相同 2. 归并排序：末尾不足数量的子序列同样需要排序 3. 插入排序 更容易判断，将其作为判断排序类型的切入点 4. 插入和归并排序的**实际操作由排序函数 sort/qsort**代替 |
归并排序 |
| 1090 Highest Price in Supply Chain | C++ | 由于不涉及结点的数据域，可以直接用vector<int> child[maxn]存放树
|
树的遍历（BFS/DFS） |
| 1091 Acute Stroke | C++ | 1. 设定相对当前位置的前后左右上下6个方向的增量，便于枚举 2. 设置数组 inq记录当前位置是否入过队3. 越界、当前位置为0、已入过队的位置无需再判断。 4. 在BFS函数中，利用队列进行BFS，使用STL的 queue，push函数只将所选元素的副本入队，后续对原元素的操作不改变队列中的副本。 |
广度优先搜索 |
| 1092 To Buy or Not to Buy | C++ | \ | |
| 1093 Count PAT's | C++ | 1. A前有P，后有T才能形成PAT； 2. 当前A能构成的PAT数量 = 之前P的数量 * 之后T的数量 3. 突破口：先遍历一遍，获取T的数量 |
递推 |
| 1098 Insertion or Heap Sort | C++ | 1. 用于表示树的数组，注意下标从 0或1 开始，孩子结点表示的区别 2. 插入排序：未排序部分和初始序列一定相同 3. 堆排序：后面的元素有序，前面无规律 4. 插入排序 更容易判断，将其作为判断排序类型的切入点 4. 插入排序的实际操作可由排序函数 sort实现5. 要用堆排序得到递增序列，则需要建立大根堆 6. 堆排序从后往前找到第一个 |
堆排序 |
| 1099 Build A Binary Search Tree | C++ | 静态写法表示树，解题方法和 A1064 基本一致 | 二叉搜索树BST |
| 1101 Quick Sort | C++ | 1. 可能的主元：左侧的最大值比自身小；右侧的最小值比自身大 2. 输出即使没有主元，也得换行 |
递推 |
| 1102 Invert a Binary Tree | C++ | 1. 题目给的是结点编号的关系，故采用静态链表存储二叉树 2. 反转二叉树即每个结点的左右子树对换，选择后序遍历 |
二叉树的遍历(静态链表；后序遍历；先序遍历；层序遍历) |
| 1103 Integer Factorization | C++ | 1. 利用vector(可根据size函数确认符合要求的元素个数)，预先存储所有 ≤ N的 元素(整数的P次幂值)2. 为了保证底数最大的序列被选中，从大到小遍历 3. DFS函数的参数：当前元素下标，已选元素数量，已选元素之和，已选元素的底数之和 4. DFS函数的递归边界：已选元素数量为K且和为N 5. DFS函数的递归调用：选择当前元素和不选择当前元素 6. 剪枝：和超过N 或 已选元素数量超过K 或 遍历完底数序列时，不必再递归 |
深度优先搜索DFS + 剪枝 |
| 1107 Social Clusters | C++ | 1. 根据共同(包括潜在的→有共同爱好的人另外的爱好)爱好来确定潜在朋友的集合，利用hobby[1001]记录 任意一个 拥有对应爱好的结点，便于合并操作2. 遍历各用户，根据根结点统计各集合的人数 3. 将集合按包含人数降序排序，再遍历即可筛选统计出集合个数 4. 路径压缩可选 |
并查集 |