PAT考试大纲, 刷题方法, 模版

考试大纲

乙级（Basic Level）

考生应具备以下基本能力：
1· 基本的C/C++的代码设计能力，以及相关开发环境的基本调试技巧；
2· 理解并掌握最基本的数据存储结构，即：数组、链表；
3· 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等；
4· 能够分析算法的时间复杂度、空间复杂度和算法稳定性；
5· 具备问题抽象和建模的初步能力，并能够用所学方法解决实际问题。

甲级（Advanced Level）

在达到乙级要求的基础上，还要求：
1· 具有充分的英文阅读理解能力；
2· 理解并掌握基础数据结构，包括：线性表、树、图；
3· 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等；
4· 具备较强的问题抽象和建模能力，能实现对复杂实际问题的模拟求解。

顶级（Top Level）

在达到甲级要求的基础上，还要求：
1· 对高级、复杂数据结构掌握其用法并能够熟练使用，如后缀数组、树状数组、线段树、Treap、静态KDTree等；
2· 能够利用经典算法思想解决较难的算法问题，如动态规划、计算几何、图论高级应用（包括最大流/最小割，强连通分支、最近公共祖先、最小生成树、欧拉序列）等，并灵活运用；
3· 能够解决复杂的模拟问题，编写并调试代码量较大的程序；
4· 具有缜密的科学思维，考虑问题周全，能够正确应对复杂问题的边界情况。

---

刷题方法

想要在pat甲级拿80到90分？陈越姥姥给出的建议如下：
首先有十分钟拿下乙级15分题的本事。
然后要能在半小时内完成乙级20分题1道。
接下来训练自己45分钟完成乙级25分题。
这时你有了2.5小时满乙级的本事！
下面改做甲级英文题。
要有用十分钟读完4题的本事。
20分钟写完20分题并至少过样例。
1小时内写完2道25分题并至少过样例。
1小时写完最难题并至少过样例。
此时你应该有70分左右了，
最后半小时拚命过90吧！
最后补充一句：其实乙级60分就有很多企业要了，乙级90分都有接到BAT级企业电话的！所以不是非要甲级才有机会哈～

遇到不会的题或者交N次都过不了某个测试点，先自己尝试着解决，很长时间没有想法（比如一个小时）后，再去网上搜题解。并且不要直接看代码，看下人家的思路。自己再来做，再做不来就去看代码，也不要直接把代码copy下来改了就交，最好看懂代码自己写。我个人觉得这样才能把别人的东西变成自己的。(MOOC数据结构的题有问题的话，善用讨论区，姥姥都会很耐心地提供帮助

另外找个大腿抱还是挺重要的（比你强就行），N天AC不了一个题有时候也挺打击人的，问题也许超出了你的知识范围而你并不知道，这个时候就需要一个大腿来节约时间，避免信心受损严重了。

代码可以背，思维是突击不来的。强烈建议每天都敲一些代码。
举个例子，甲级练习题里的基础数据结构题。
题目有1004，1020，1021，1028，1032，1107等。
涉及到的有队列，栈，链表，二叉树，并查集。
如果你发现自己并不熟悉这些，那么应该花几天的时间学习c++STL相关操作，二叉树前中后遍历。
由于PAT考试不能够携带纸质资料，我假设你会针对结构体使用algorithm头文件的排序，对STL的向量，栈，队列，map，set相关操作和迭代器足够熟悉，否则强烈建议你花上一些时间学习。
然后可以试着做一些模拟题目。
模拟题范围较广，可以锻炼思维，增强码代码能力。
题目有但不限于这些：1005，1006，1008，1009，1011，1015，1024，1035，1042，1043，1048，1065。
你需要学会贪心思想，深度优先搜索和广度优先搜索，进制转换，筛素数，字符串处理，二分查找。
之后的题目涉及到一些算法，更高级一点的数据结构，数学，动态规划知识。
动态规划较为晦涩，初学者需要较多时间才能掌握。
例如1007，最大子串和就是经典的一题。
另外建议你学习LIS最长上升子序列的O(n^2)做法，LCS最长公共子序列，01背包，这些建议去hduoj，讨论版有详细解析。
数据结构方面学习优美的树状数组，AVL。
例如1057需要用到树状数组的快速求和进行二分查找，1066使用AVL进行模拟。
AVL的旋转思想对Splay这样飘逸数据结构的学习是必不可少的。
算法方面在题库里主要涉及到图论算法。
如1003，1046，1106，主要是最短路算法和深度优先搜索的应用。
1053有多叉树的储存和遍历。
图的储存学会使用矩阵和vector两种方式。
最短路算法较多，不建议全都学会，但一定要对其中一种足够熟悉，并且对矩阵图和vector图都会写。
数学方面主要是学会筛素数，求gcd，lcm，O(sqrt(n))的找约数，素因子，会用约数和定理，约数个数定理，c++的话还有大数的模拟。

---

技巧模版

买了本《算法笔记》来看

大数问题

https://blog.csdn.net/hacker00011000/article/details/51298294
https://blog.csdn.net/nk_test/article/details/48912763

algorithm中常用的现成算法

1.binary_search() 确定容器中是否存在某个元素

2.equal() 确定两个集合中的所有元素皆相同。

3.lower_bound() 从头到尾，查找第一个大于或者等于所列元素的值的位置
用法，参考下面的min_element()；

4.upper_bound() 从头到尾，查找第一个大于所列元素的值的位置

5.make_heap( ) 创建一个堆并以序列的形式输出

6.max() 返回两个元素间的较大者

7.max_element() 返回序列中的最大值

8.min() 返回两个元素中的较小者

9.min_element() 返回序列中的最小值

int a[]={1,4,66,43,2,56,443,23,234,4};

int b= min_element(a,a+7)-a;

int c= max_element(a,a+7)-a;

如果想取值的话，直接加 max_element(a,a+n)

10.mismatch() 查找两个序列中的第一个不相同的位置

11.pop_heap() 从一个堆中移除一个最大的元素

12.push_heap() 添加一个元素至堆

13.reverse() 将给定序列反转顺序，范围。

14.sort() 将序列升序排序

15.sort_heap() 将堆转变为有序序列

16.swap() 交换两个对象的值

17.unique() 移除连续的重复元素
注意连续两个字，也就是说明了要先进性排序操作
为什么呢？

因为unique函数并没有把重复的元素删掉，他只是把那些重复的元素移动到了本序列的末尾，返回值是不重复序列的位置指针。

所以如何显示不重复序列呢？

1.一种方法是直接将不重复序列指针 it 到 vector.end()
对此阶段进行 删除用erase()函数 erase(it,vector.end())

2.直接将vector.begin 到不重复序列尾的 位置指针 it 将元素输出来
即，

vector<int>::iterator it=a.begin();

while(it!=  unique(a.begin(),a.end())) {
  cout<<*it<<" ";
  it++;
}

int main() {
	VECTOR_STRING::iterator iNameTor;
	iNameTor = unique(vecNames.begin(), vecNames.end());
	cout << "after unique(), contents are:" << endl;
	printVec(vecNames);
	
	cout << "unique return a iterator, point to the first Duplicate element " << endl;
	cout << iNameTor - vecNames.begin() << endl << endl;  	
	vecNames.erase(iNameTor, vecNames.end()); //删除重复元素
	cout << "after erase(), contents are:" << endl;
}

18. 输入：多行数据：每行数据之间空格间隔，

输出：对应的行，每行输出对应行的所有数字之和。

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
  string line;
  while(getline(cin,line)) {
    int sum=0,x;
    stringstream ss(line);
    while(ss>>x) {
      sum+=x;
	}
	cout<<sum<<endl;
  }
  return 0;
}

参考算法竞赛104

19.
strlwr()将字符串变小写
strupr()将字符串变大写
strcmp()两个参数只能是c字符串，不能是string类型，也可以用s.data()

20. C++常用泛型函数总结

count()函数的一个例子

// ..

find()函数一个例子

// ..

find_first_of一个例子

// ..

find_of一个例子

// ..

map容器的操作：

begin()返回指向第一个元素的迭代器
end()返回指向最后一个元素的迭代器
rbegin()返回指向最后一个元素的迭代器
rend()返回指向第一个元素的迭代器
empty()测试map容器是不是空的
size()返回容器的大小
max_size()返回容器最大的容量，这个是相对于内存来讲的
insert()向容器中插入元素
erase(it)删除容器当中it指向的元素，it为迭代器
erase('c')删除容器中键值为'c'的元素
eras(it, mymap.end())删除容器中it和mymap.end()之间的元素，它们两个都是迭代器
foo.swap(bar)交换容器foo和bar中的元素
clear()清空容器
find('b')返回指向键值为'b'的的迭代器，没有的话就指向end()
count('c')查找键值为'c'的元素，在map中返回0或者1,0表示没有这个键值，1表示有，但是在mutimap中就是这个键值出现的次数
lower_bound('b')返回指向键值为'b'的迭代器，当没有这个键值时就返回空的迭代器
upper_bound('b')返回指向键值为'b'的下一个元素的迭代器，没有的话就返回空的迭代器

vector容器的操作：

begin()返回指向第一个元素的迭代器
end()返回指向最后一个元素的迭代器
rbegin()返回指向最后一个元素的迭代器
rend()返回指向第一个元素的迭代器
size()返回容器的元素的个数
max_size()返回容器的最大的元素的个数
resize()重新调整容器的容量，无论原来的容量是大于还是小于后来的恶容量都可以
myvector.resize(5);将容器的容量调整为5，如果变短了就直接删除多余的元素，长了就用0将剩余的空间填满
myvector.resize(8,100);将容器的容量调整8，并将多出来的位置用100表示
myvector.resize(12);将容器的容量调整为12，多出的空间用0填充
capacity()返回这个容器在内存空间中最多的连续空间
empty()测试这个容器是不是空的
reserve()重新调整容器的capacity
at(i)返回位置为i处得元素的引用，当超出容器的最后一个位置就抛出一个异常
front()返回第一个元素的引用
back()返回最后一个元素的引用
void assign ( InputIterator first, InputIterator last );将迭代器first和迭代器last之间的元素付给调用这个方法的容器
void assign ( size_type n, const T& u );将n个u付给容器
push_back()在容器的末尾添加元素
pop_back()删除容器最后面的一个元素
iterator insert ( iterator position, const T& x );在迭代器position的前面插入元素x
void insert ( iterator position, size_type n, const T& x );在position的前面插入n个x
template <class InputIterator>
void insert ( iterator position, InputIterator first, InputIterator last );将迭代器first和last之间的元素插入到position前面
iterator erase ( iterator position );删除迭代器position指向的元素
iterator erase ( iterator first, iterator last );删除迭代器first和last之间的元素，不包括last指向的元素
void swap ( vector<T,Allocator>& vec );交换两个容器的元素
void clear ( );清空容器当中的元素

set容器操作

set容器(只存储值不相同的元素，并且按照从小到大的顺序排列)
iterator begin ();返回指向set容器第一个元素的迭代器
iterator end ();返回指向容器最后一个元素的迭代器
reverse_iterator rbegin();返回指向容器最后一个元素的迭代器
reverse_iterator rend();返回指向容器第一个元素的迭代器
bool empty ( ) const;测试容器是否为空
size_type size() const;计算容器当中元素的个数
size_type max_size () const;计算容器的最大容量
pair<iterator,bool> insert ( const value_type& x );将元素x插入到set容器中返回pair对象，first元素为指向插入的元素的迭代器，second元素为指示插入成功与否的bool值
iterator insert ( iterator position, const value_type& x );将x插入
template <class InputIterator>
void insert ( InputIterator first, InputIterator last );将first与last只见到恶元素插入到容器中
void erase ( iterator position );删除position位置处得元素
size_type erase ( const key_type& x );删除值为x的元素
void erase ( iterator first, iterator last );删除迭代器first和last之间的元素
void swap ( set<Key,Compare,Allocator>& st );交换两个set容器的元素
void clear ( );清空set容器

stack栈的操作：

bool empty ( ) const;测试栈是不是空的返回1表示空0表示非空
size_type size ( ) const;返回当前栈的元素的个数
value_type top ( );返回当前的栈顶元素，不删除这个元素
const value_type top ( ) const;返回栈顶元素的const引用
void push ( const T& x );将当前的元素x入栈
void pop ( );删除栈顶元素

queue队列的操作：

bool empty ( ) const;测试当前队列是不是空，0表示空，1表示非空
size_type size ( ) const;队列的元素的个数
value_type& front ( );返回队首元素的引用
const value_type front ( ) const;返回队首元素的const值
value_type& back ( );返回队尾元素的引用
const value_type& back ( ) const;返回队尾元素的const值
void push ( const T& x );将x入队列
void pop ( );删除队首元素

string类型的应用

string.c_str() 返回的是const char*而非char *，如果想返回char *的话可以这样写：char * a = (char*)string.c_str();
strtok()函数很好用，分割字符串 
应该还有其他

字符大小写转换函数:

tolower(char c)函数，tolower()函数的参数是字符类型。	
toupper(char c)函数，toupper()函数的参数也是字符类型。

字符串大小写转换：

c中，包含ctype.h头文件
strlwr()将字符串变小写
strupr()将字符串变大写
strcmp()两个参数只能是c字符串，不能是string类型，也可以用s.data()   	
c++,中,tolower()、toupper()配合transform()函数

编程：

1.下面的编程 是改变发生在原字符串S上。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
	
using namespace std;

int main() {
  string s="Hello worLD";
  transform(s.begin(),s.end(),s.begin(),::toupper);
  cout<<s<<endl;
  transform(s.begin(),s.end(),s.begin(),::tolower);
  cout<<s<<endl;  
  return 0;
}

2.下面的编程是 改变发生在新建字符串c上，不过有一条语句十分的重要

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
	
using namespace std;
	
int main() {
  string s="Hello worLD";
  string c;
  
  c.resize(s.size());
  
  transform(s.begin(),s.end(),c.begin(),::toupper);
	  
  cout<<c<<endl;
  transform(s.begin(),s.end(),c.begin(),::tolower);
  
  cout<<c<<endl;
  return 0;
}

有权图的单源最短路径问题：

迪杰斯特拉 算法：

    针对常见问题、疑惑给出的结论：
        若路径是按照递增（非递减）的
        顺序生成的，则：
            1.真正的最短路必须只经过S中的顶点
            2.每次从未收录的顶点中选一个dist值最小的收录（贪心）
            3.增加一个v进入S，可能影响另外一个w的dist值。
                而且针对第3点，还有一个重要的说明就是v如果能够改变w
                    也有一个必要条件，就是v和w一定是邻接点。
                    这样编程就好编了。
                    dist[w] = min{dist[w],dist[v]+<v,w>的权重}。

另外一些注意的

数据输入范围：

int 记住绝对值在10^9 范围以内的整数都可以定义为  int 。
	
long long  记住 在10^10 ~10^18 范围以内的整数都可以定义为 long long 。
	
long long bignum = 123456789012345LL;
	
需要 加 LL 。


见 《算法笔记》 P8.、



如果数组大小较大，大概10^6 级别，则需要将其定义在主函数的外面，
否则会使程序异常退出。

**不使用 float ,都使用 double .**

无穷大INF的定义:

const int INF = (1<<30)-1;
const int INF = 0x3fffffff;

常用数学函数：

fabs(double x)
  ：对double类型变量取绝对值。

floor(double x)
  : 对double 类型变量向下取整

ceil(double x)
  : 对double 类型变量向上取整

pow(double x,double y)
  : 求 x^y 


sqrt(double x)
  : 对double 类型变量求算术平方根。

log(double x)
  : 对double 类型变量求以自然对数为底的对数。


round(double x)
  : 对double 类型变量x进行四舍五入。

对冒泡排序的简单思考：

从数组 前到后 遍历，交换  -》》》沉底算法;
从数组 后到前 遍历，交换 -》》》冒泡算法。

memset():

--对数组中的每一个元素赋一个相同的值。
包含头文件 #include <cstring>
	
注意：
   **对于初学者，只建议使用memset赋 0 或 -1；
  如果要对数组赋其他数字，比如1，使用 fill()函数。

  这里已经试过了，的确赋其他值，比如 34 的时候，出错了。
  这里一定要注意一下。**

判断字符是字母，数字，还是字母数字，以及大写，小写：

2.cctype中还有其他函数，如：

isdigit() 用来判断一个字符是否是数字。
isalnum() 用来判断一个字符是否为英文字母或数字，相当于 isalpha(c) || isdigit(c)
isalpha() 用来判断一个字符是否是英文字母，相当于 isupper(c)||islower(c)

构造函数有什么用呢？

初始化，就记住初始化就可以了。
**永远保持有一个默认的空的构造函数，这样我们在声明一个
自定义类型变量的时候，就可以不必初始化**。详见 算法笔记》P73.

sscanf()和sprintf()

:流输入输出函数，这个东西很有用，尤其是sscanf,可以实现一次性的多个分割：

	
比如：
将字符数组str中的内容按 "%d:%lf,%s"的格式
写到int型变量n、double型变量db、char型数组变量str2中。
	
sscanf(str,"%d:%lf,%s",&n,&db,&str2);
	
相对应的反操作：

sprintf(str,"%d:%lf,%s",n,db,str2);

补充内容：

1.cin、cout P74
2.浮点数的比较 P75
   const double eps=1e-8;
   #define Equ(a,b) (  (fabs( (a)-(b) )) <(eps)  )

3.圆周率
  const double PI=acos(-1.0);

4.复杂度  P78

25.进制转换：

**其他进制转换为 10 进制，用while()循环；
10 进制转换为 其他k进制，就是除k取余法，用do {}while;**

26.单点测试的技巧：

巧妙地利用EOF , 算法笔记 P97
PAT B 的经典说反话 。

27.基本的排序算法：

1.选择排序：

每次从未排序的序列中选择最小的数，然后将其与未排序的序列第一个元素交换，
并与之前已经排好序的序列，自动形成有序序列。
贴到已排序的序列屁股后面。

2.归并排序：

过程就是从2人小组/1人小组，N/2个小组，到四人小组，N/4个小组，一直到N人小组，1个小组。
归并就是把两个有序的序列合并为一个有序的序列的过程。
总之算是分治与归并的结合就是归并排序，可以看下面的代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <vector>


using namespace std;



const int maxn=100;


void merge(int a[],int L1,int R1,int L2,int R2)
{
    int i=L1,j=L2;

    int temp[maxn];
    int index=0;

    while(i<=R1 && j<=R2)
    {
        if(a[i]<=a[j])
        {
            temp[index++]=a[i++];

        }
        else
        {
            temp[index++]=a[j++];
        }



    }


    while(i<=R1)
    {
        temp[index++]=a[i++];
    }


    while(j<=R2)
    {
        temp[index++]=a[j++];
    }



    for(int i=0;i<index;i++)
    {
        a[L1+i]=temp[i];

    }






}


void merge_sort(int a[],int left,int right)
{
    if(left<right)
    {

        int mid= (left+right)/2;


        merge_sort(a,left,mid);
        merge_sort(a,mid+1,right);
        merge(a,left,mid,mid+1,right);


    }
}

int main()
{

    int a[]={4,5,3,3,2,3,7,8,2,1};



    for(int i=0;i<sizeof(a)/sizeof(int);i++)
    {
        cout<<a[i]<<" ";

    }

    cout<<endl;

    merge_sort(a,0,9);

    for(int i=0;i<sizeof(a)/sizeof(int);i++)
    {
        cout<<a[i]<<" ";

    }

    cout<<endl; 

    return 0;
}

3.快速排序

其实也没什么，就是每次挑出一个数（通常选相对第一个数），作为中间的“裁判”，划分左右部分的过程。
具体的细节可能需要注意。
比如元素的序号是从1~N的，存放在A[]中。 我们首先把A[1]元素值提取出，存放在临时变量temp
中，这样，
所以利用two pointers 思想，left指针指向A[1]位置，right指针指向A[N],然后我们注意，先动的，是right指针。
只能向左移动了，但是动之前需要先判断**。

首先判断A[N]是否小于等于temp变量，如果满足条件，就把A[N]元素与A[1]元素交换，还是注意，
A[1]元素的值是无关紧要的，因为我们早已经用temp变量保存了下来。但是交换之后，也就意味着A[N]元素的值变成无关紧要的，
我们不能对A[1]随便修改了，
因为此时保存 原来A[N]元素的关键人物，只有A[1]了，如果我们再对它一不小心进行了别样的修改，也就是讲一个没有额外备份的元素销毁，它将灰飞烟灭。
所以接下来该怎么办呢？继续移动指针并进行判断。
那么移动left还是right呢？判断什么呢？
并将其原来的位置作为下一个可以继续我们“蹂躏”的位置。
而A[N]的位置显然是在最右边的。移动什么呢？
只能是移动left指针了。
将left指针向右移动，直到出现A[i]元素大于temp的时候，就将A[i]元素与A[N]元素互换，此时，无关紧要的位置又变成了A[i]，就这样循环下去。直到left指针和right指针相遇。
也就是
所以这只是一次，以A[1]作为裁判划分出了“大致有序”的左半部分和右半部分。我们还需要分别对左右两边继续实行同样的策略。

我这里所谓的“大致有序”，就是以“裁判”为准，左边部分都是小于裁判的元素，右边部分都是大于裁判的元素，但是左边部分不保证有序，右边部分也不保证有序。
这也是还需要对左边部分和右边部分分别进行同样的以上操作的必要原因。

总结一下，关键点：
1.two pointers;
2.分治，递归；
3.其实我觉得很关键的，反倒是一个临时变量temp,保存“裁判”元素，也就是意味着，
原来的数组A[]多出了一个“无关紧要”的，我们可以任意移动的元素位置，利用这一点，就好像踢皮球一样，左一脚右一脚。
直到裁判元素的位置最终确定。

28.容器的排序

在STL容器中，只有vector 、string 、deque是可以使用sort的。

30.C++中容器遍历的5种方式：

std::vector是我在标准库中实用最频繁的容器。总结一下在遍历和创建vector时需要注意的一些地方。
在不考虑线程安全问题的前提下，在C++11中有五种遍历方式。

方式一

for (size_t i =0; i < vec.size(); i ++) { int d = vec[i]; }

方式二

size_t len = vec.size();
for (size_t i =0; i < len; i ++) { int d = vec[i];}

方式三：

for (auto it = vec.begin(); it != vec.end(); it ++) { int d = *it;}

方式四:

for (int i:vec) {int d = i;}

方式五

for_each(vec.begin(), vec.end(), [](int i){ int d = i;});

31.但是要注意

vector<int> vec;
for (auto i:vec) {printf("%d ",i);}

简便写法，这里实际上是进行了值传递，就是一份拷贝，如果是需要更改
原来的数据，需要改成引用的形式，

vector<int> vec;
int d=0;

for (auto& i:vec) {i= d;}

32. string的小技巧

string a="abcdeffdfsfsd";

string b=string(a,5);

cout<<b;

最终输出的是：ffdfsfsd
自己截取了。

33. 读取一行字符串的时候，如何不掺杂其他的‘，’等符号时，可以直接利用EOF:

比如： HELLO WORLD I AM HERE

char s[90][90];
int num=0;
while( scanf("%s",s[num])!=EOF) { num++; }

但是如果还有其他混淆字符等时，就需要过滤：

比如：

string line;

getline(cin,line);

while(!isalnum(line[i])) { i++;}

然后就是对非空字符进行判断处理，比如说进MAP容器中，等。

 string word="";

while(isalnum(line[i])) {
  word+=line[i];
  i++;
}

if(word!="") {
	...
}

ref:
https://blog.csdn.net/yinghuoai/article/details/78510094