考试类精品--计算机保研考研上机考试复习整理，制作不易，还请给个star噢~.zip

# 复习目录 - 常用函数：STL等常用数据结构（树、栈、队列、优先队列、向量、散列表、集合、字符串）和函数 - 数学问题（最小公倍数、最大公因数、快速幂、进制转换、质因数、大数） - #### 搜索（BFS & DFS） - 图论（并查集、最小生成树、最短路径、拓扑排序、关键路径） - #### 动态规划 # 常用函数 ## memset-对数组中每个元素赋值0/-1 ```c++ #include <string.h> int a[5]; memset(a,0,sizeof(a)); ``` ## getchar/putchar && gets/puts ```c++ #include <stdio.h> getchar(); //输入单个字符 有时候还可以用来吸收换行符 putchar(); //输出单个字符 gets(); //输入一行字符串，识别\n作为输入结束 puts(); //输出一行字符串，并输出\n 若是字符串末尾没有\0则会乱码 ``` ## string.h ```c++ #include <string.h> strlen(str); strcmp(str1,str2); //比较字典序，小于返回负整数，等于返回0，大于返回正整数 strcpy(str1,str2); //把str2复制给str1 strcat(str1,str2); //把str2接到str1后面 ``` ## math.h ```c++ #include <math.h> fabs(-12.56); //12.56 floor(-5.2); //-6 向下（小）取整 ceil(-5.2); //5 向上（大）取整 double db = pow(2.0,3.0); //8.000000 sqrt(2.0); //1.414214 log(1.0); //0.000000 以自然对数为底的对数 //log(a)b=logb/loga 必须用换底公式 const double pi = acos(-1.0); sin(pi*45/180); cos(pi*45/180); tan(pi*45/180); //弧度制！！ asin(1); acos(-1.0); atan(0); round(3.5); //4 四舍五入 ``` ## printf ```c++ #include <iostream> #include <cstdio> %5d; //宽为5的整数，超过5位按实际输出，不够5位右对齐输出 %05d; //宽为5的整数，超过5位按实际输出，不够5位前置补0右对齐 %5.2f; //宽为5的浮点数，小数点有2位，小数点占一位, 不够5位右对齐输出 %6.9s; //表示显示一个长度不小于6且不大于9的字符串。若大于9, 则第9个字符以后的内容将被删除。 %ld; //表示输出long整数 %lf; //表示输出double浮点数 %-7d; //表示输出7位整数左对齐 空位补齐 %-10s; //表示输出10个字符左对齐 /*按整型输出，默认右对齐*/ printf("%d\n",PrintVal); /*按整型输出，补齐4位的宽度，补齐位为空格，默认右对齐*/ printf("%4d\n",PrintVal); /*按整形输出，补齐4位的宽度，补齐位为0，默认右对齐*/ printf("%04d\n",PrintVal); /*按16进制输出，默认右对齐*/ printf("%x\n",PrintVal); /*按16进制输出，补齐4位的宽度，补齐位为空格，默认右对齐*/ printf("%4x\n",PrintVal); /*按照16进制输出，补齐4位的宽度，补齐位为0，默认右对齐*/ printf("%04x\n",PrintVal); /*按8进制输出，默认右对齐*/ printf("%o\n",PrintVal); /*按8进制输出，补齐4位的宽度，补齐位为空格，默认右对齐*/ printf("%4o\n",PrintVal); /*按照8进制输出，补齐4位的宽度，补齐位为0，默认右对齐*/ printf("%04o\n",PrintVal); ``` # 常用模板代码 ## 日期转换 闰年判断 ```c++ bool IsLeapYear(int year){ return (year%4==0 && year%100!=0) || (year%400==0); } ``` ## 反序数 ```c++ int Reverse(int x){ int revx=0; while(x != 0){ revx*=10; revx+=x%10; x/=10; } return revx; } ``` ## 最大公约数 & 最小公倍数 ```c++ //最大公约数求法 int GCD(int a,int b){ //辗转相除法 a大b小 if(b==0){ return a; }else{ return GCD(b,a%b); } } //最小公倍数求法 a * b / GCD(a,b); ``` ## 质数和分解质因数 ### 1. 质数判定：若到sqrt(n)的整数，所有正整数均不能整除n，则可以判断n为素数（小于2必定不是素数） ### 2. 某范围内的素数筛法 ```c++ const int MAXN = 10001; vector<int> prime; //保存质数 bool isPrime[MAXN]; //标记数组 void Initial(){ //初始化 for(int i=0;i<MAXN;++i){ isPrime[i] = true; } isPrime[0]=false; isPrime[1]=false; //素数筛法 for(int i = 2;i<MAXN;++i){ if(!isPrime[i]){ //非质数跳过 continue; } prime.push_back(i); for(int j=i*i;j<MAXN;j+=i){ //注意从i*i开始！！！ isPrime[j]=false; //质数的倍数必为非质数 } } } ``` ### 3. 分解质因数：先用素数筛法,然后不断试除 ## 快速幂 1) 求指数的二进制数 2) 求底数幂然后累乘 3) 矩阵快速幂，初始化为单位矩阵 ```c++ int FastExp(int a,int b,int mod){ int answer = 1; //初始化为1 while(b!=0){ //不断将b转换为二进制数 if (b%2==1){ //若位为1，累乘a的2^k次幂 answer *= a; //answer %= mod; //求后三位，依题目而定 } b/=2; //b不断转换 a*=a; //a不断平方 //a%=mod; //求后三位，依题目而定 } return a ``` ## 同余模定理 ```c++ (a*b)%c=((a%c)*(b%c))%c; (a+b)%c=((a%c)+(b%c))%c; ``` ## BFS ```c++ #include <iostream> #include <queue> #define SIZE 1000 using namespace std; queue<int> q_x, q_y, q_pos; int step[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }; int m, n, board[SIZE][SIZE], start_x, start_y, target_x, target_y; bool vis[SIZE][SIZE]; void bfs() { bool flag = false; //判断是否成功的标志 while (!q_x.empty() && !q_y.empty()) { //判断队是否为空 for (int k = 0; k < 4; ++k) { //先遍历 int tx = q_x.front() + step[k][0]; //状态转移 int ty = q_y.front() + step[k][1]; if (tx < 1 || ty < 1 || tx > n || ty > m) //判断边界 continue; if (!board[tx][ty] && !vis[tx][ty]) { vis[tx][ty] = true; //标记 q_x.push(tx); //入队 q_y.push(ty); q_pos.push(q_pos.front() + 1); } if (tx == target_x&&ty == target_y) { //判断到达目标的条件 flag = true; break; } } if (flag) break; q_x.pop(); //队首出队 q_y.pop(); q_pos.pop(); } return; } int main() { while (cin >> m >> n) { for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { cin >> board[i][j]; } } cin >> start_x >> start_y >> target_x >> target_y; q_x.push(start_x); q_y.push(start_y); //初始入队 q_pos.push(0); vis[start_x][start_y] = true; bfs(); cout << q_pos.back() << endl; } return 0; } ``` ## DFS ```c++ int check(参数) { if(满足条件) return 1; return 0; } void dfs(int step) { 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 标记 继续下一步dfs(step+1) 恢复初始状态（回溯的时候要用到） } } ``` ## 并查集 1. 用于判断图是否为连通图 2. 求图的连通分量 ```c++ #include <iostream> #include <cstdio> using namespace std; const int MAXN = 1000; int father[MAXN]; //父亲结点 int height[MAXN]; //结点高度 void Initial(int n){ //初始化 for(int i=0;i<=n;i++){ father[i]=i; //每个结点的父亲为自己 height[i]=0; //每个结点初始高度为0 } } int Find(int x){ //查找根节点 if(x!=father[x]){ //路径压缩 father[x]=Find(father[x]); } return father[x]; } void Union(int x,int y){ //合并集合 x=Find(x); y=Find(y); if(x!=y){ //矮树作为高数的子树 if(height[x]<height[y]){ father[x]=y; }else if (height[y]<height[x]){ father[y]=x; }else{ father[y]=x; height[x]++; } } return ; } //先Initial 再 一个一个输入 Union //Find(i)==i; 说明有一个集合，即连通分量 ``` ## 最小生�