notes_for_pat

前言：暑假几乎花了一整个月备考PAT，期间因为调代码调到过深夜，做模拟题也曾做的心态有点奔溃，但总的来说这一段时间过的是很充实的，感觉自己的代码能力确实有提高不少，今年秋季PAT出的题都比较常规，侥幸拿了个满分（感谢姥姥手下留情），不过拿了满分后也并没有想象中的那样激动，更多的是一种怅然若失的感觉和冥冥中一种遗憾，我也说不清这种遗憾究竟是什么，感觉PAT也只是自己学习的长途中一个小的结点，它从某个角度上证明了前期努力的成果，但是它远不能成为对自己能力的炫耀，因为我知道自己能力还是有很多不足之处的，我觉得可以做到更好，这无疑需要更长期的努力。我愿把这次PAT考试作为一个新的起点，以此出发开始一段新的旅途，因为我觉得后面的风景会更美……

这篇文章是备考PAT过程中的一些笔记，记录下来作为一个纪念吧哈哈哈哈

string相关

• substr(pos,len)函数返回从pos下标开始，长度为len的子串

• string类型的转换

  string str;
  int i;
  str.c_str();  //string转换成char[]
  to_string(i); //int转化为string
  stoi(str);  //string转int方法一 C++11
  atoi(str.c_str()); //string转int方法二

• 大小写转换，tolower()函数和toupper()函数，函数在头文件cctype中

• string相关函数总结

  • insert(pos, string) 在pos号位插入string字符串 （下标定位）

  • insert(it, it2, it3) it为与插入位置，it2，it3为待插入字符串首尾迭代器，将串[it2, it3)插入到it的位置上（迭代器定位）

  • erase(it) 删除it迭代器位置的元素（删除单个元素）

  • erase(first, second) 删除[first, second)区间元素，first和second为迭代器

  • erase(pos,length) pos为删除起始位置，length为删除的个数

  • substr(pos, lenth) pos位开始，长度为length的子串

  • string::npos 可以作为find函数失败时的返回值

  • str.find(str2,pos) 返回子串str2在str中第一次出现的位置，若没有子串str2返回string::npos, pos可以加也可以不加，加上后表示从pos号位开始查询

  • str.repalce(pos, len,str2) 将str从pos位开始长度为len的子串替换为str2

  • str.replace(it1,it2,str2) 将子串[it1,it2)替换为str2

• string读取一行 getline(cin, str);

• getline读取一行数据时一定要先把上一行的换行符去掉！！！

• cin.ignore() 默认可以跳过一个字符

map相关

• map<string,int>和unordered_map<string,int> int的默认值为0
• hash数组能将所有元素的查询降到O(1), 使用map虽然能节省一定的空间，但是查询不在map中的元素是需要一定时间的

字符串相关

• gets(char* )读取一行字符串

• scanf("%c", &a)是可以读入空格和换行的，输入的时候要注意

• sscanf(str,"%d",&n) 将字符串数组str中的内容以%d的格式写入n中

  sprintf(str,"%d",n) 将n以%d的格式写入str字符串数组中

• 处理字符数组的函数（均在头文件string.h中，string.h和string是不一样的头文件）

  strlen(字符数组) 返回字符串数组以一个’\0’前的字符个数，也即是字符串的长度

  strcmp(字符数组1，字符数组2) 返回数组字典序比较结果，str1>str2返回正整数，str1=str2返回0，str1<str2返回负整数

  strcpy(字符数组1，字符数组2) 将str2复制给str1

  strcat(字符数组1，字符数组2) 将str2接到str1后面

链表

• 链表节点结构体中可以添加address记录节点地址、num记录节点在链表中的次序、以及flag表示节点某种性质，一般的题可以通过num和flag的综合排序解决，当然也可以单独用一个vector容器存储特定性质的节点序列最后输出

DFS和BFS

• 剪枝的两种方式：

  ①在进入新的“分支”前进行判断，以决定是否进入新分支；

  ②直接判断当前的状态是否以及不合题意，直接return；

  这两种的区别在于第一种只产生所有合乎题意的“路径”，而第二种可能比合乎题意的“路径”多向下走了一层

• 从一个序列中枚举所有子列或是从N个数中选择K个数，枚举的一般思路是依次判断原序列中的所有数选还是不选

• BFS要点：①首元素出队的时候进行访问（所以只需将遍历的相关信息存在队列中就可以了）；②在元素入队时记录遍历层数；③inq数组记录结点是否入队

• 有一些贪心问题用DFS解决时，往往是不需要遍历的，除非涉及到一些比较复杂的指标，所以一般要根据贪心的策略去“剪枝”。

• 在“判断”是否要剪枝的时候最好不要改变该记录该递归状态下的状态量，因为改变后还需要重新复原后才能返回，否则状态量的记录就不对了，所以比较好的做法时，判断的时候不改变，确定需要向下递归时再去改变。

图

• 图的深度优先遍历需要vis[]数组记录结点是否访问过，广度优先遍历需要inq[]数组记录结点是否入队，迪杰斯特拉算法需要vis[]数组记录节点是否已被加入集合S中。
• 由于非连通图的存在，除了DFS()函数或BFS()函数外还需要DFSTrave()函数和BFSTrave()函数，保证遍历到图中所有结点。

数学问题

• 进制转换：将十进制数 y 转化为Q进制，每次将 y 除 Q 的余数保存到数组 z[] 中，最后将 z 数组逆序输出；注意，循环最好用do{}while() ，否则当 y 为0的时候可以会直接跳出，z[] 中将不会有元素

• 素数表的建立 int prime[maxn],num=0 表长maxn至少比n（要输出的最大范围）大1

  //素数筛
  const int maxn=101;
  int prime[maxn],num=0;
  bool p[maxn];
  void findPrime()
  {
      for(int i=2;i<maxn;i++){
          if(p[i]==false){
              prime[num++]=i;
              for(int j=i+i;j<maxn;j+=i)
              {
                  p[j]=true;
              }
          }
      }
  }

• 质因数分解

  //用结构体数组存储质因子
  struct factor{
      int x,cnt;
  }fac[10];
  //数组大小开到10就可以处理int范围内的值了
  //因为2*3*5*7*11*13*17*19*23*29已经超过int最大值

• 分数的计算，用一个结构体存储分数，注意分数的化简当分子为0时将分母置为1，方便作为整数输出，其他情形将分子分母约分就可以了

  struct fraction
  {
      int up,down;
  }

• 大整数

  ①大整数可以使用结构体存储，如下所示，但是由于运算时总是从整数低位到整数高位进行枚举，所以为了方便，结构体中数组低位存储整数高位，直观上看就是带过来存储。当然用string存储也是可以的，有时候做题显得更简单

  struct bign
  {
      int d[1000];
      int len;
  }

  ②大整数运算——将运算步骤转化为代码

  • 加法：从低位依次枚举，和的个位赋给结果的相应位，十位为下一位的进位，枚举完毕后若进位carry不为零，将其赋给结果最高位
  • 减法：进行减法前要判断，将较大的数作为被减数。从低位依次枚举，若不够减被减数高位减一，被减位加十后再减。结果高位可能有0，要将其删除。
  • 乘法：这里仅考虑高精度乘以低精度，将低精度（如int）作为整体，从低位枚举大整数，个位数为结果对应位，高位为进位（可能有多位）。最后进位若不为0，依次赋给高位（可能有多位）。
  • 除法：这里仅考虑高精度除低精度。除法的结果是高位先得出，从大整数高位开始枚举，不够除商0；够除得到相应的除数和余数，再将余数乘10加上下一位作为下一步临时的被除数，最后高位同样可能有0，要去除。

递归

• 分治是一种算法思想，其核心在于将问题分解成与原问题相同和相似的子问题，缩小问题规模直到能求解，递归只是它的一种实现方式，两者并不等同
• 递归是一种程序实现方式，其特点在于反复调用自身函数，如果求解问题中有反复出现的相同相似求解过程，那么递归是一种很好的实现方式。分治之所以可以用递归实现是因为有结构相同或相似的子问题，但是递归能解决的问题会更广泛，凡是有反复出现类似的求解过程都可以考虑使用递归函数。
• 递归函数的参数表用来记录当前递归解决的问题或是递归状态。

二分法

• 二分法的实现很简单，给定查询区间[left,right]，每次根据中心点mid=(left+right)处的值与查询值的大小关系更新left和right就可以了，循环的条件是left<=right，即left>right时跳出，此时查询失败

• 寻找第一个大于等于x的元素A[y]，A[y]一定满足：A[y]>=x>A[y-1]，故A[mid]>=x时 A[mid]>=x>A[y-1]⇨ mid>y-1⇨mid>=y⇨向区间[left,mid]查询；当A[mid]<x同理可得到向区间[mid+1,right]查询。

  并且还要注意：①循环条件为left<right，因为即使查询失败也要返回“假设它存在，它应该在的位置”；②由于查询元素可能比序列中所有元素要大，故传入函数的初值right应该比序列上界大1，即传入[left,right]=[0,n]。

归并排序

• 归并排序递归实现：对一个序列进行递归排序，只需要分别对其左右两个区间分别进行递归排序，然后将其合并，注意左右两个区间是[left, mid]，[mid+1, right]，其中mid=(left+right)/2，递归边界为left=right，即为一个元素时，或者可以写left<right时继续向下递归
• 归并排序非递归实现：设置step初始值为2，每次循环将step个元素分为一组，将前step/2个元素和后step/2个元素合并，注意组内元素少于step/2时不需要合并，每次循环完成后step乘2。循环的条件是当前step/2<n(n为序列元素个数)。

树

• 若给定BST所有结点的值（均不相同）和BST的结构是可以唯一建立一颗BST的，有两种思想可以考虑：①二叉搜索树的中序遍历序列是递增序列，所以可以中序遍历树结构，将要输出中序遍历序列的语句改成给相应根节点赋值，这样就建立了这棵树。②先遍历一遍树，求以每个节点为根节点的子树的结点数，在过程中将每个结点的左子树的结点树记录下来；若某个结点左子树结点树为numLeft, 则它对应的值为序列中第numLeft+1大的那个数
• 由于AVL数需要计算平衡因子，方便起见在结点结构体中加入height，记录以某个结点为根节点的子树的高度，对树的结构进行改变时要更新高度。左旋右旋操作均需要有更新高度的操作。

并查集

• 并查集是一种维护集合的数据结构，很好地表示了集合这种抽象概念，所以可以运用到涉及划分群体和分类的题中，其中最重要的就是合并操作，就是将属于同一个集合的元素合并，题目中最核心的往往在于如何判断两个元素属于同一集合，有的题目会直接给出属于同一集合的条件，但有些则需要判断再合并。
• 对于将某个性质相同的元素进行合并的题目，可以记录第一个出现该性质的元素下标，将后序所有该性质的元素直接与记录的元素合并就可以了，这样可以避免反复遍历查询。

最短路径

• Bellman-Ford算法不需要vis[]数组，它总共进行V-1轮操作，每一轮操作都遍历所有的边，判断是否有能被更新的距离，时间复杂度为O(VE)。唯一与dijkstra算法不同的一点在于统计最短路径条数的做法，因为DF算法会多次访问已经访问过的结点，为了解决这个问题可以设置一个set\ pre[maxn] 来存储前驱节点，当遇到与已有最短路径相同长度的路径是需要重新计算最短路径条数。
• SPFA算法是使用队列优化了BF算法，因为只有某个顶点u的d[u]改变时，从它出发的边的邻接点v的d[v]值才有可能被改变，所以每次都将改变过的结点入队，去看看以这些点为中介点能否优化其他路径。实现过程中有几点要注意，①要设置一个inq[]数组，记录“当前状态”在队列中结点，因为如果结点已经在队列中的话就不需要反复入队了；②设置num[]数组，记录结点入队次数，如果某个结点入队次数超过n-1次说明图中有负环
• 另外SPFA算法和BF算法最好用邻接表实现，这样效率更好。SPFA算法也比朴素dijkstra算法快很多，据算法笔记上说，它甚至经常性优于堆优化的dijkstra算法。
• Floyd算法的流程：枚举所有的顶点，如果以它为中介点能让其他两点间的距离缩小则更新这个最短距离。Floyd算法实现很简单只需要一个二维数组dis[maxn][maxn]即可。

拓扑排序

• 拓扑排序的实现：首先需要一个记录入度的数组inDegree[]，先将所有入度为0的结点入队，只要队列不为空，每次取出队首元素，将其能到达的结点入度减一，如果入度变为0，则将其也入队。拓扑排序也可以用于判断图是否为有向无环图，只需要记录入过队的结点总数num，当队列为空时，如果num等于结点总数

关键路径

• 一个活动最早开始时间等于左端点事件最早发生事件，最迟发生事件等于右端点事件最迟发生时间减边权
• ve[]初始化为0，vl初始化为ve[]最大最
• 最后遍历所有边（活动）确定关键路径

怎么写循环

在考试中循环语句往往是比较容易写错或是比较难写的，这里专门用一个小节来总结一下程序里面“循环怎么写”

• 循环是对一系列不同对象进行相同或相似操作的结构。
• 循环条件不好写的可以用while(1)和break控制
• 循环只能解决一个状态向下转变为另一个状态的搜索，如果对应多个状态，请用DFS！！！
• 要写的循环是什么，怎么更新变量进入下一个循环，循环什么时候跳出。
• 对于要枚举一系列值直接用for循环

PAT考试

• 考试中遇到bug是很正常的事，要知道bug的出现都是有缘由的，通过调试观察程序执行的效果和预想的有没有差异，找到出错点改正就可以了。bug也没那么可怕，不要被自己的心态打败了！
• 找不到原因的时候看看是否由输出错误，这是OJ特有的错误！
• 分析问题，先确定整体的问题解决思路，明确具体的解决步骤，然后将其转化为程序语言去执行

杂项

• 变量名最好有一定的意义，这样在代码编写过程中不容易出现张冠李戴的情况

• 至少循环一次的写法:

  1.do{}while()语句

  2.while(1){}在循环体中加入break语句控制什么时候跳出

• while(scanf("%d",&n) != EOF){}表示直到没有输入为止停止循环，另外在终端中输入和回车键表示EOF

• 不要用循环中会改变的量初始某个变量，最好在循环外面将初始值单独存下来

  使用while循环的时候注意更新变量

  注意循环中有些变量每次循环开始时要初始化

• 编写程序过程中，一定要清楚变量的含义和存储的数据情况，要不然也会出现弄错下标的情况；另外数据的类型也很重要

  :star2:编程的逻辑（思路）清晰是第一步，然后如何把它转化成程序语言也很重要——其中要注意的是①语句的顺序很重要，程序是顺序执行的，一定要考虑顺序对执行效果的影响，以及顺序执行的效果与解决问题的方法是不是对应的:star2:

• 质数判断不要漏掉0和1，要单独判断

• 注意题目的编号，是1~n还是0~n-1, 最好把相应的数组也与编号对应起来，这样不容易出错！！

• 段错误的原因是跟内存相关的，往往出错的原因是数组开的长度过小或是指针越界等

• 部分测试点的错误要考虑边界情况，即使觉得不太可能也要试一试，可能就是老师挖的坑！！！

• string使用+=更快一些

• 能模拟到底就尽量模拟到底，这样能省去很多推理的过程，也减少了出错的可能。

• set的主要作用有自动去重和按升序排列，在某些情况下查找的效率是比较高的（可以解决一些超时问题），涉及排序的题可以考虑使用

  另外对于结构体，可以通过通过重载小于号<使得set中元素按照需要的顺序排列，一种实现方式是使用友元函数，如下所示：

  struct Node
  {
      //其他部分省略
      friend bool operator <(Node a,Node b)
      {
          //....
      }
  };

• vector的最后一个元素下标是vector.size()-1，不要访问越界了！

• 判断是不是完全⼆叉树，就看在出现了⼀个孩⼦为空的结点之后是否还会出现孩⼦结点不为空的结点，如果出现了就不是完全⼆叉树。

• 在涉及“图”的题目中，若结点标识为字符串需要用hash的方法或是使用map<string,int>将其转化为int型的数字，这样才能构建邻接矩阵或是邻接表

• 要计算某个连通图的总边权时，在DFS中要判断该节点与其他所有节点之间是否有通路，有的话就累加起来，然后删掉这条边避免重复计算。

• 审题很重要！很重要！很重要！ 明确题目中字母的含义(n,k,…), 不要因为做题惯性就把它当作其他值了，例如并不是所有的n都是图的节点个数的；开始写代码之前最好有将实际问题抽象成数据结构的过程，这样可以减少编码是的错误

• 初始化邻接矩阵使用fill函数时，首地址是G[0]

• 检查代码错误的时候，也要时刻提醒自己代码是顺序执行的，前面的语句时会对后面语句的执行效果或是某些变量的值造成改变的，所以初始化是很重要的

  :star2:迪杰斯特拉最短路径问题记得初始化G[maxn][maxn]!!!!!:star2:

• 对于某些问题不要想当然，最好去一步步模拟一遍

• 有些空格的输出可以单独输出，可能会比连带其他内容一起输入时更好控制

• int型变量不赋初值可能是一个很大的数，有时候会直接超出数组范围引起段错误

• 对于一些稍复杂的题，先理清思路，明确要处理数据的情况以及相应的处理方式，确定算法步骤再转化成程序语言就可以了！

• 写程序是尽量做到对各种数据处理的全面性，不要认为测试数据就都是正常的，对不正常的数据要做判断或是筛除，确保程序是正确的，要不然可能就正好遇到老师挖好的坑了

  怎么debug：①第一个层次：检查每条语句是否与实现的方法相符；②第二个层次：明确要解决什么问题以及要怎么实现，由此代码该怎么写（逻辑层面）③一些tips，注意一些边界情况能不能同样得到处理，全面考虑所有的情况，特别是有一些边界情况因为与大多数不同而没法满足判断条件进入相应的代码块导致逻辑错误 ④如果始终找不到错误可以重新审题考虑是不是忽略了一些隐含条件。⑤考试中要检查是否有打错的情况！！！

• bool型数组如果这样赋值bool vis[maxn]={true}只有第一个元素被赋值成true！！！ 但是false可以赋给每一个值

• 遍历可以一次遍历所有的”连通块“，计算遍历的次数可以知道连通块的数量。

• 随机数生成

  //要包含stdlib和time头文件
  #include<stdlib.h>   //可以替换成cstdlib
  #include<time.h>    //可以替换成ctime
  int main()
  {
      srand((unsigned)time(NULL));  //生成随机数种子
      rand(); //生成随机数 范围[0,RAND_MAX]
      rand()%(a-b+1)+b; //[a,b]范围随机数
      
      //当要生成的随机数范围长度超过RAND_MAX时可以这样写
      round((rand()*1.0/RAND_MAX*(a-b)+b));
  }

• vector\作为元素本身也是可以用sort函数直接排序的，排序默认是按照vector\序列的“字典序”