phoenix大佬的一轮刷题记录

本文转自超强zju大佬phoenix博客，mark以激励自己！向大佬学习！
2018年1月2日～2018年1月29日

以下是自己的学习记录：

PAT第四章

难题队列

A1075、A1080、A1095、B1033、A1033、A1089

4.1节排序（1月5日）

A1075（25）第五个测试点通不过得22分

A1080（30）第4个测试点通不过得26分

A1095 需要使用map的用法；将hh:mm:ss转换为秒的形式便于操作（学完6.4节后再做）

4.2节散列(1月6日）

A1084 注意空格键也要进行判断；

B1033 （20）第3测试点通不过 19分

4.3节递归（1月6日）

全排列问题

N皇后问题（递归暴力法，回溯法）

4.4节贪心（1月7日）

PATA1033 加油站问题（没思路）

PATA1037（25）优惠卷问题//加=测试点3显示运行超时，测试点6可以通过；不加=测试点3可以通过，测试点6显示答案错误 得22分

PATA1067 (25)第3、4测试点超时。得19分(寻找首个不相等的值每次都是从头开始找导致超时）

PATA1038(30)学习完6.3string 用法后再做

4.5节二分（1月8日）

PATA1010「 long long inf=((long long) 1<<63-1);」注意括号问题；未知进制数转化为long long时要判断是否溢出

4.6节 two pointer（1月8日）

PATA1089 将三类数组均置于全局；引入比较函数（bool型），输出函数（void型）；判断是否插入排序；归并排序使用非递归方法；

4.7节其他高效技巧与算法（1月8日）

打表、递推、随机选择算法

PATA1093、PATA1101添加辅助数组

PAT第五章

难题队列

PATB1003、PATA1049、

5.1节简单数学（1月8日）

PATB1003 （再做）使用数学方法找规律完成

PATA1104 浮点数与整数相乘浮点数应放在前边（ans+=v*(n-i+1)*i）（v为double型，v放在前边）（若为（n+1-i)iv. 则第2、3测试点答案错误）

PATA1049 能不开数组尽量不开数组，开数组的话把边界情况考虑到

5.2节最大公约数与最小公倍数（1月9日）

5.3节分数的四则运算（1月9日）

注意分数的乘除法int型会导致溢出

头文件要加#include using namespace std;

5.4节素数（1月9日）

PATA1078 二次探测法每次冲突都从头开始，并不是接着上一次探测的结果。

5.5节质因子分解（1月10日）

PATA1096 注意大质数时的输出情况。

5.6节大整数运算（1月10日）

熟记大整数的加减乘除运算，将字符串转化为大整数，输出函数

PATA1024 将大整数范围开得大一些d[1000]

PAT第六章

难题队列

PATA1022

6.1vector的常见用法详解（1月11日）

PATA1039 出现众多名字时，与查询相关时使用hash表示字符串，使用vector表示

PATA1047 如果排序时直接对字符串排序，那么会导致大量的字符串移动，应采用字符串下标来代替字符串本身进行排序。

6.2set的常见用法详解（1月11日）

Set最主要的作用是自动去重并按升序排序

Set只能通过迭代器（iterator）访问；insert（）；find（）；erase（）；size（）；clear（）；

6.3string的常见用法详解（1月11日）

区分cstring与string

c_str()将string类型转化为字符数组

6.4map的常见用法详解（1月11日）

Map主要用途：建立字符串与整数之间映射；判断大整数或其他类型数据是否存在；字符串与字符串之间的映射

find（）；erase（）；size（）；clear（）

PATA1022 数字图书馆，熟练掌握stl的语法

6.5queue的常见用法详解（1月12日）

q.push();q.front();q.back();q.pop();q.empty();q.size();

6.6priority_queue的常见用法详解（1月12日）

priority_queue name;

name.top()访问队首元素；name.push();name.pop();name.empty();name.size();

优先级设置

使用top()函数前，必须用empty()判断优先级队列是否为空，否则可能会因为队空而出现错误；

6.7stack的常见用法详解（1月12日）

st.push(); st.top(); st.pop(); st.empty(); st.size();

Stack用来模拟一些递归；

6.8pair的常见用法详解（1月12日）

#include 可以使用map的头文件代替

Pair的常见用途：用来代替二元结构体及其构造函数，可以节省编码时间；作为map的键值对来进行插入

6.9algorithm的常见用法详解（1月12日）

max();min();abs();

swap();reverse();

next_permutation();给出序列在全排列的下一个序列；

fill();可以把数组或容器中的某一段区间赋为某一个相同的值；

sort();

lower_bound(first, last,val);寻找在数组或容器的[first,last)范围内第一个值大于等于val的元素的位置；

upper_bound(first, last,val);寻找在数组或容器的[first,last)范围内第一个值大于val的元素的位置

PAT第七章

难题队列

7.1栈的应用(1月12日）

PATA1051 pop、top操作前面要判空；

7.2队列的应用（1月12日）

PATA1056 用队列存储比赛序号，没有必要存储整个结构体

7.3链表处理（1月13日-1月14日）

PATA1032 不使用flag标记，测试点4答案错误。。。本题可以使用flag进行标记，两次遍历即可完成。

PATA1052. 要将无效结点排除

PATA1097 注意结点均为有效的情况，remove序列个数为0；

PAT第八章

8.1DFS（1月14日）

PATA1103 注意超时问题

8.2BFS（1月14日）

队列中存放的元素最好不要是元素本身，而是它们的编号（下标）

PATA1091 注意T的作用

PAT第九章

难题队列

9.2二叉树的遍历（1月15日）

熟练写模版

9.3树的遍历（1月15日）

前五题均1A

9.4二叉查找树（1月16日）

三题均1A

9.5平衡二叉树（1月16日）

熟记模板

9.6并查集（1月17日）

1A

9.7堆（1月17日）

9.8哈夫曼树（1月17日）

PAT第十章

难题队列

A1018

10.1图的定义和相关术语（1月17日）

10.2图的存储（1月17日）

10.3图的遍历（1月17日）

10.4最短路径（1月19日）

dijkstra

Bellman-Ford

SPFA

A1018 审题，在运输过程中都要调整每经过的车站

PAT第十一章

动态规划（1月21日-1月22日）

PAT第十三章

13.1分块思想（1月22日）

13.2树状数组（1月22日）

统计序列中在元素左边比该元素小的个数。

13.3快乐模拟（1月23日）

A1017 23分，最后一个测试点通不过
1月24日-1月28日 完成1108～1139题目。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112094139