今天整理电脑，发现了去年为了考研浙大计算机整理的PAT资料。现在考研已经尘埃落定。想到当时盲目刷题浪费了好多时间，在这里希望将整理的东西放到网上，方便后来者学习。

PAT的命题趋势

将PAT甲级中的题目从第一题刷到最后一题，可以明显感受到，PAT甲级的题目风格发生了很明显的变化。从早期的模拟型题目变成了后来以数据结构和算法为主的固定题型。如果时间紧迫的话，可以只刷后一般的题目，放弃前一半的题目，因为前一半题目的出题风格已经过时了。

PAT题目按分数和知识点分级

PAT按照分数分为20，25，30分。下面是将题目按照这3个分数段进行整理。
其中25分和30分的题目代码在这里：代码

20分段

20分的部分题目没有标注涉及的知识点，没有标注的这些题目说明非常简单，只是用来熟悉编程语言的，稍微有些基础的同学可以跳过，没有基础的同学可以先做这些题目。

题号 知识点 是否建议二刷
1001
1005
1008
1011
1015
1019
1023
1027
1031
1035
1041
1042
1046
1050
1054
1058
1061
1065
1069
1073
1088 分数处理
1092
1096
1100
1104
1108 字符串于浮点数间的转换 二刷
1112 字符串处理 可二刷
1116 还行,hash
1120
1124
1128 n皇后问题，但是简化了，只是让验证而已
1132
1136 字符串处理数字加减 可二刷
1140 字符串处理 二刷
1144
1148 狼人杀
1152 字符串处理(自己想麻烦了) 二刷

25分段

25分的题目比20分的题目多了解决方法和备注。没有标注解决方法的题目是因为比较简单或者涉及的解决方法已经在其他题目中使用。

题号 知识点 解决方法 是否建议二刷 备注
1002 模拟多项式加
1003 图 最短路径+点权+最短路径数量
1006 查找元素
1007 DP 最大连续子序列 可二刷
1009 时间处理
1010 二分法 基数数字转换 这里如果不使用二分法,只有一个测试点过不去
1012 排序 结构体排序 亮点在,对四门课同样的排序可以只写一个cmp,结构体中用数组即可
1013 图 无向图的连通分量
1016 排序
1017 模拟银行
1020 二叉树查找树
1021 图 无向图+连通分量+最深结点*2
1024 大整数
1025 排序
1028 排序
1029 two pointers
1032 链表
1033 贪心
1036 查找元素
1037 贪心
1039 STL应用
1040 DP
1043 二叉查找树
1044 二分查找
1047 STL应用
1048 散列
1051 栈 判断序列是否为出栈序列 二刷 这里可用这种最笨的方法来输出所有栈的结果
1052 链表 模拟静态链表,有点坑 二刷 里面有很多好的写法
1055 排序 结构体排序 有点水
1056 队列 可二刷 题目不是多难,就是开始想岔了,没读懂题目
1059 素数表建立 数的素数分解 二刷 这题变形可出关于正整数的因子个数
1060 科学计数法
1062 排序 排序,cmp+sort
1063 set,STL应用 set应用
1066 avi AVI的建立 可二刷 这次使用的是静态链表方法
1067 贪心 贪心+排序 二刷 挺绕的一题
1070 贪心 贪心 有一个测试用例没过,然后发现因为float的数据被我认为是int了
1071 map,STL 字符串处理 这里使用两个字符串统计单词，要比之前我只用索引来确定方便很多
1074 链表 静态链表反转 二刷 数据和地址分离，直接反转地址，太特么秀了
1078 hash Hash二次探测法
1079 树 树+找叶结点+深度
1082 字符串处理 数字的中国传统读法
1083 排序 排序 水题
1085 二分法
1086 树 先序中序转后序
1089 判断排序方法 二刷
1090 树 树+找叶结点+深度
1093 逻辑题
1094 树 树+最多结点层数
1097 链表 链表分割 可二刷 仍然是用那种无赖的方法，很爽
1098 判断排序方法 堆排序+插入排序 与1089一起二刷
1101 快排 快排特点
1102 树 树+层序+中序 indices:指数
1105 模拟 打印螺旋形矩阵 二刷
1106 树 树+DFS+叶子最小的层 可以二刷
1109 逻辑题 拍照站位 不知道为啥错
1110 完全二叉树 判断一个树是不是完全二叉树 可二刷
1113 排序+贪心 贪心 有点水
1115 二叉查找树 二叉查找树+静态构建 二刷(必须)
1114 并查集 并查集统计很多 二刷
1117 逻辑题 读懂题意就较为简单
1118 并查集 并查集统计集合和元素个数 二刷
1121 set应用 hash用法
1122 图 哈密顿环 二刷 可以再做,被自己写复杂了
1125 贪心 贪心,排序 题目不难，就是浮点数向整数舍入有点恶心
1126 图 欧拉图 这里需要判断图是否连通
1129 set应用，运算符重载
1130 树 表达式树+中序
1133 链表 模拟链表处理 链表处理不能忘了去不用的结点,并且有种非常无赖的方法
1134 hash hash_set 这题如果使用set,则200多毫秒，如果使用hash_set则快些
1137 map映射,排序 float转int 四舍五入:round 向上取整:ceil 向下取整:floor,强转
1138 树 二叉树先序+中序转后序 可二刷 这里需要剪枝,另外这种代码可以不建树，直接由建树代码改造
1141 map,排序 map,STL的应用 这里有个坑：浮点转整形时，计算sum时，将sum全计算完再做，若每次都转再相加，精度严重丢失 case insensitive:不区分大小写
1142 图 找完全图
1145 哈希 Hash二次探测法+查找 二刷
1146 图 topo排序 二刷 可以再做,被自己写复杂了
1149 STL应用 set应用 水题
1150 图 旅行商问题+哈密顿变体
1153 排序,模拟 排序 二刷 答案的结构体设置特别好
1154 hash 图 图+边两端结点颜色不同 注意如何存储一个一个的边

30分段

30分的题目多了解决方法和备注。没有标注解决方法的题目是因为比较简单或者涉及的解决方法已经在其他题目中使用。

题号 知识点 解决方法 是否建议二刷 备注
1004 树遍历
1014 队列
1018 图 DFS+Dijkstra+三value 二刷
1022 map映射,STL使用
1026 模拟，排序
1030 图 Dijkstra+二value
1034 图 DFS+连通分量+分量所有边权和
1038 贪心
1045 DP
1049 数学
1053 树遍历 DFS找路 可二刷
1057 树状数组 使用树状数组求序列中第k大数据 二刷
1064 二叉查找树 在构建好的完全二叉树上先序遍历+层序遍历 可二刷(较水)
1068 01背包,DP
1072 图 Dijkstra+三value 二刷 atoi需要stdlib包
1076 图 BFS+统计多少层以内结点数目 可二刷
1080 排序
1087 图 Dijkstra+DFS+三value 可二刷 比较耗时间
1091 三维bfs
1095 map,排序
1099 二叉查找树 静态二叉查找树构建 二刷
1103 深度优先搜索DFS
1107 并查集 使用并查集即可 可二刷
1111 图 Dijkstra+DFS+四value,两次Dijkstra 可二刷 这题理解错题意，浪费了时间
1119 二叉查找树 先序后序->中序 二刷
1123 avi树 avi树构建+BFS+CBT 二刷
1127 树 后序中序->层序) 可二刷 常规
1131 图 打印最短路径的格式太难了
1135 红黑树 判断一棵树是不是红黑树 二刷 里面有求树高和判断左右子树是否等高的代码
1139 图 题目时间改了,用DFS最后一个用例超时，可以直接暴力法，终点和起点同时遍历一个结点
1143 二叉查找树 LCA+数据排好序就是查找树的中序遍历 可二刷
1147 堆 判断堆是大根小根还是不是堆 可二刷
1151 树 LCA 二刷
1155 堆 判断是大根堆小根堆还是不是堆 二刷

知识点整理

知识点整理是考前临时抱佛脚看的，有两份，第一份较为详细，第二份较为精简。主要是一些样板代码和一些做题的注意点。
下面放的是详细版本的,PDF版本可以点击这里详细版本pdf。同时精简版本的PDF可以查看这里精简版本pdf

详细版知识点整理

树状数组

1
2
3
4
5
6
7
8
9
10
int getSum(int x){ 求 c[1,x]的 sum
    int sum = 0;
    for(int i = x;i >= 1;i -=lowbit(i))
    sum+=c[i];
    return sum;
}
void update(int x,int v){
    for(int i = x;i < MAXN;i+=lowbit(i))
    c[i]+=v;
}

DP(动态规划)

  1. 最大连续子序列:dp[i] = max(A[i],dp[i]+A[i]);
  2. 最长不下降子序列:dp[i] = max(1,dp[j]+1) (j=1,2,……,i-1, A[j]<=A[i])
  3. 最长回文库： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    for(int i = 0;i < n;i++){
        dp[i][i] = 1;
        if(i>0&&A[i-1]==A[i]){
        dp[i-1][i] = 1;
        ans = 2;
        }
    }
    for(int L = 3;L <= len;L++){
        for(int i = 0;i + len - 1 < len;i++){
            int j = i+len-1;
            if(dp[i+1][j-1]==1&&A[i]==A[j]){
                dp[i][j]=1;ans = L;
            }
        }
    }
  4. 最长公共子序列： 
    1
    2
    3
    4
    dp[i][j] = {
        dp[i-1][j-1]+1; A[i]=B[j];
        max(dp[i-1][j],dp[i][j-1]);
    }
  5. DAG
  6. 背包问题 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void beibao(){
        for(int i = 1;i <= n;i++){
            for(int v = V;v >= w[i];v--){ 这是 01 背包问题
            for(int v = w[i];v<=V;v++){ 这是完全背包问题
                dp[v] = max(dp[v],dp[v-w[i]]+c[i]);
            }
        }
    }

图

  1. 最短路径

    • Dijkstra

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      void Dijkstra(int s){
          fill(dis,dis+MAXN,inf);
          fill(vis,vis+MAXN,false);
          dis[s] = 0;
          for(int i = 0;i < n;i++){
              int u =-1,MIN = inf;
              for(int j= 0;j < n;j++){
                  if(!vis[j]&&dis[j]<MIN){
                      u = j,MIN = dis[j];
                  }
              }
              if(u==-1)return;vis[u]=true;
              for(int v = 0;v < n;v++){
                  if(!vis[[v]&&G[u][v]!=inf){
                      if(G[u][v]+dis[u] < dis[v]){
                          //处理语句
                      }else if(G[u][v]+dis[u]==dis[v] && 其他条件){
                          //处理语句
                      }
                  }
              }
           }
      }
      void getPath(int s){
          if(s==start){
              tempPath.push_back(s);
              1.在这里计算对应的值
              2.计算完后进行相应的更新
              3.达到条件时 path = tempPath;
              tempPath.pop_back();
          }
          tempPath.push_back(s);
          for(int i = 0;i < pre[s].size();i++){
              getPath(pre[s][i]);
          }
          tempPath.pop_back();
      }

    • SPFA

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      bool SPFA(int s){
          memset(inq,false,sizeof(inq)); inq 记录顶点是否在队列中
          memset(num,0,sizeof(num)); num 数组记录顶点的入队次数
          fill(d,d+MAXN,INF);
          queue<int> q;
          q.push(s);
          while(!q.empty()){
              int u = q.front();q.pop();
              inq[u] = false; u 不在队列中
              for(int j = 0;j < Adj[u].size();j++){
                  int v = Adj[u][j].v;
                  int dis = Adj[u][j].dis;
                  if(d[u]+dis < d[v]){
                      d[v] = d[u]+dis;
                      if(!inq[v]){
                          q.push(v);
                          inq[v] = true;
                          num[v]++;
                          if(num[v]>=n)return false;
                      }
                  }
              }
          }
          return true;
      }

  2. 最小生成树(Prim算法)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int prim(){
        fill(d,d+MAXN,inf);
        d[0] = 0;
        int ans = 0;
        for(int i = 0;i < n;i++){
            int u = -1,MIN = inf;
            for(int j = 0;j < n;j++){
                if(vis[j]==false && d[j]<MIN){
                    u = j;MIN = d[j];
                }
            }
            if(u==-1)return false;
            vis[u]=true;
            ans += d[u];
            for(int v= 0;v < n;v++){
                if(!vis[v]&&G[u][v]!=inf){
                    if(G[u][v] < d[v]){
                        d[v] = G[u][v];
                }
                }
            }
        }
        return ans;
    }

  3. 树的遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    (1).DFS
    void DFS(int s){
        vis[s] = true;
        这里是一些操作,包括剪枝之类的
        for(int v = 0;v < n;v++){
            if(!vis[v]&&G[s][v]!=inf){
                DFS(v);
            }
        }
    }
    void DFSTravel(){
        for(int i = 0;i < n;i++){
            if(!vis[i])DFS(i);
        }
    }

    (2).BFS
    void BFS(int s){
        queue<int> q;
        q.push(s);inq[s]=true;
        while(!q.empty()){
            int u = q.front();q.pop();
            for(int v = 0; v< n;v++){
                //计层，用结构体的话，放在这里
                if(!vis[v]&&G[u][v]!=inf){
                    q.push(v);
                    inq[v] = true;
                    //计层的话,开数组放在这里，否则会被覆盖
                }
            }
        }
    }
    void BFSTravel(){
        for(int i = 0;i < n;i++){
            if(!inq[i])BFS(i);
        }
    }

  4. 图论的题
    这种题只能根据题目要求进行判断，另外判断成环，可以用 set 元素个数和读入结点个数是
    否相等来判断

  5. 拓扑排序
    较为简单，使用队列进行模拟就行，使用stl中的优先队列更方便。

栈,队列,哈希,链表

  1. 链表：数据与 next 分离，剔除无用结点，长度为 0 单独考虑
  2. 栈：如果考一个序列的所有出栈情况,最笨的方法是排列后分别判断;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    判断一个序列是否是出栈顺序:
    bool is(){
        for(int i = 1;i <= n;i++){
            s.push(i);
            if(q.front()==i){
                while(!s.empty()&&q.front()==s.top()){
                q.pop();s.pop();
            }
        }
        if(!s.empty())return false;
        else return true;
        }
    }

3.队列:容易题不常见,难的就是银行排队的题目,见机行事吧
4.hash(二次探测法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool insert(int x){ 二次探测法插入
    for(int i = 0;i < size;i++){
        int index = (x+i*i)%size; 这里有的把 i*i 放在外面,根据题意判断
        if(hash[index]==-1){
            hash[index] = x;
            return true;
        }
    }
    return false;
}
int search(int x){
    int cnt = 0;
    for(int i = 0;i <= size;i++){ 与插入不同,这里带等号
        int index = (x+i*i)%size;
        if(hash[index]!=x && hash[index]!=-1){
            cnt++:
        }
    }
 return cnt;
}

树

红黑树

判断方法：根为黑色，所有红结点的儿子都是黑节点，所有结点左右子树的(黑节点)高度相
等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool judge1(int s){ 判断所有红节点的儿子都是黑节点
    if(s == -1)return true;
    if(red[s]){
        if(T[s].l!=-1&&red[T[s].l])return false;
        if(T[s].r!=-1&&red[T[s.r]])return false;
    }
    return judge1(T[s].l)&&judge1(T[s].r);
}
bool judge2(int s){ 判断所有结点左右子树的(黑结点)高度相等
    if(s == -1)return false;
    int L = getH(T[s].l);
    int R = getH(T[s].r);
    if(L!=R)return false;
    return judge2(T[s].l)&&judge2(T[s].r);
}
int getH(int s){
    if(s == -1)return 0;
    int L = getH(T[s].l);
    int R = getH(T[s].r);
    return max(L,R)+1; 这是正常求树高
    return black[s]?max(L,R)+1:max(L,R); 这是求(黑结点)高度
}

平衡二叉树

四种旋法：
* 插在左子树的左子树:树右旋
* 插在左子树的右子树:左子树左旋，然后树右旋
* 插在右子树的右子树:树左旋
* 插在右子树的左子树:右子树右旋，然后树左旋
实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int leftRotate(int s){ 左旋
    int temp = T[s].r;
    T[s].r = T[temp].l;
    T[temp].l = s;
    return temp;
}
int rightRotate(int s){ 右旋
    int temp = T[s].l;
    T[s].l = T[temp].r;
    T[temp}.r = s;
    return temp;
}
int leftRightRoate(int s){ 左右旋
    T[s].l = leftRotate(T[s].l);
    return rightRotate(s);
}
int rightLeftRotate(int s){ 右左旋
    T[s].r = rightRotate(T[s].r);
    return leftRotate(s);
}

int insertT(int& s,int k){
    if(s == -1) return newnode(k);
    else if(k < T[s].k){
        T[s].l = insertT(T[s].l,k);
        int L = getH(T[s].l),R = getH(T[s].r);
        if(L - R > 1){
            if(k < T[T[s].l].k){
                s = rightRotate(s);
            }else{
                s = leftRightRotate(s);
            }
        }
    }else{
        T[s].r = insertT(T[s].r,k);
        int L = getH(T[s].l),R = getH(T[s].r);
        if(R-L > 1){
            if(k > T[T[s].r].k)
                s = leftRotate(s);
        else
            s = rightLeftRotate(s);
        }
    }
    return s;
}

堆

堆首先必须是一个完全二叉树。

  1. 判断是大根堆还是小根堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void judge(){
        for(int i = 2;i <= n;i++){
            if(T[i/2]>T[i])small = false;
            if(T[i/2]<T[i])big = false;
        }
        if(!small&&!big)不是堆
        else if(small) 小根堆
        else if(big) 大根堆
    }

  2. 堆排序：堆排序的特点是后面有 k 个数是排好序的且,这 k 个数都 >= 第一个数每次从后向前找到第一个 >= T[1]的数 T[p]，交换 T[p]和 T[1]后执行下面的调整算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void adjust(int low,int high){
        int i = low,j = 2*i;
        while(i <= high){
            if(j+1<=high && T[j+1]>T[j])j+=1;
            if(T[i]>=T[j])break;
            swap(T[i],T[j]);
            i = j,j = 2*i;
        }
    }

完全二叉树(判断是否是完全二叉树或者建树)

  1. 建树：直接用数组模拟
  2. 判断
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    void bfs(int s){ 用 bfs 判断否是完全二叉树,如果遇到了非内结点后又遇到内结点则不是
        queue<int> q;
        q.push(s);
        int flag = 0;
        bool isCom = true;;
        while(!q.empty()){
            int u = q.front();q.pop();
            if(T[u].l!=-1){
                if(flag==1) isCom = false;
                q.push(T[u].l);
            }else flag = 1; 遇到叶子结点
            if(T[u].r!=-1){
                if(flag==1) isCom = false;
                q.push(T[u].r)；
            }else flag = 1;
        }
    }
    bool check(){ 直接检测
        int half = len/2;
        for(int i= 1;i < half;i++){ 所有内结点
            if(T[i].l==-1)return false;
            if(T[i].r==-1)return false;
        }
        for(int i = half+1;i <= n;i++){ 所有叶子结点
            if(T[i].l!=-1)return false;
            if(T[i].r!=-1)return false;
        }
        if(T[half].l==-1&&T[half].r!=-1)return false;
        return true;
    }

    哈夫曼树

  3. 如果不用建树,就用优先队列:priority_queue
  4. 如果需要建树,是从下向上建,就要在结点中添加一个指向父节点的值

普通二叉树

  1. 构建
    先序+中序：
    后序+中序：
    先序+后序：如果有只有一个儿子的结点，则会有歧义
    中序+层序：这个暂时还未考
  2. LCA(与上面构建类似)
    五种情况：
    u 是根
    v 是根
    u,v 在根的左侧
    u,v 在根的右侧
    u,v 在根的两侧
  3. 遍历,先序遍历,后序遍历,中序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void BFS(int s){
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();q.pop();
            for(int i = 0;i < T[u].size();i++){
                int v = T[u][i];
                q.push(v);
            }
        }
     }
    void DFS(int s){
        if(s == -1)return;
        for(int i = 0;i < T[s].size();i++){
            int v = T[s][i];
            DFS(v);
        }
    }

并查集:一定要记得初始化

对于并查集的题目，在统计时要使用 findFa(x)来查找 father，因为 father[x]里面存的可能不
是祖先而是直系父亲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findFa(int x){
    if(x == father[x])return x;
    else {
        int Fa = findFa(father[x]);
        father[x] = Fa;
        return Fa;
    }
}
int union(int x,int y){
    int Fx = findFa(x);
    int Fy = findFa(y);
    father[Fx] = Fy;
    return Fy;
}

排序

  1. 快速排序：特点：每次排完,排好的元素在最终结果对应的位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int quick(int low,int high){
        int temp = arr[low];//基准数据
        while(low < high){
            //当队尾元素大于等于基准元素,向前挪动 high 指针
            while(low < high && arr[high] >= temp)
                high--;
            arr[low] = arr[high];
            //当队首指针小于等于基准元素,向后挪动 low 指针
            while(low < high && arr[low] <= temp)
                low++;
            arr[high] = arr[low];
        }
        //将 temp 放在该在的位置
        arr[low] = temp;
        return low;
    }

  2. 堆排序：前面说了

  3. 插入排序：开始 k 个元素排好,后面的与输入序列一样

其他

  1. 数字转string
    sprintf(chs,"%d",sum,',');//先将数字存在 char 数组中
    string str = chs; //将 char 数组转为 string
  2. 对时间进行排序,可以使用 std 的字符串直接对字符串的时间进行比较。
  3. 对于中序，后序先序等互相获得的题目,递归条件可以改成通用
    1
    2
    3
    4
    5
    if(preL>preR)return;
    else if(preL == preR){
        post.push_back(pre[preL]);
        return;
    }
  4. 对于AVL树,注意：左旋右旋一定要写对，如果结果不对很可能是因为左旋右旋插入函数中,插入结点后对树进行调整时 要记得将旋后的返回值赋值给s,如: s = rightRotate(s)
  5. 除了只涉及完全二叉树和图，一定要建结点，不要浪费时间，有时候用到子树T[T[s].l],一定要先检查是否为-1
  6. 对于数1-n中有多少个num(1<= num <=9 )的题目，对第i位进行分离即可,即 ai = num,ai<num,ai>num;分别得出左右数的大小，然后乘在一起等操作即可。
  7. 有些数据可能是float,结果当int处理
  8. 取整:四舍五入:round向上取整:ceil向下取整:floor,强转
  9. 浮点转整形时，计算 sum 时，将 sum 全计算完再做，若每次都转再相加，精度严重丢
    失
  10. hash_set用法：加上下面两句#include <hash_set> using namespace __gnu_cxx;
    (11). string.rbegin(),rend()是从右向左遍历
    (12). atoi(str.c_str())需要用到stdlib.h库, cctype库里有一些用到的函数
    (13). cin >> int;后面跟getline，getline会得到一个\n

其他

在这里说一些自己当时犯的错，供后来人吸取教训：

  1. 平时做题练习的时候一定不要在意题目的对错，刚开始刷题的时候因为在意对错和得分，甚至去网上抄袭别人的代码，一知半解的。然后就得到了报应。第一次考试的时候才考79。不得已二刷，然后耽误了考研的复习。
  2. 晴神的书中涉及的知识点太多太杂，很多是以前命题的知识点，一定要把后一半的题目做完，PAT的命题风格变化还是很明显的。有些知识点已经很久没有出了，或者出在20分的题中。把精力多放在与数据结构知识点结合的方面。
  3. 对于知识点方面，可以看看这篇博客，总结的很详细。宇宙无敌PAT考纲。这个博客的PDF版本我整理下来了，可以在这里查看:考纲PDF版本。代码方面，建议看柳神的博客，所有题目的PDF版本建议去柳神博客上购买订阅，几块钱不贵。
  4. 祝看到这篇博客的同学PAT满分，考研顺利进浙大。