简单复习整理了《计算机考研——机试指南》一书的知识点，内容比较简洁扼要。因为自己能力和精力有限，部分内容还待补充，希望大家可以和我一起整理，如有兴趣可在下方留言。
输入输出
- scanf函数有返回值的，返回的是成功赋值的变量个数。持续读写文件可以这么写：
while (scanf("%d", &n) != EOF){pass;
}
或者
while(gets(字符串变量))
- 可以使用%4d来获取输入中的前4位数字，使用%2d%2d来获后面4个数字。
排序
这个sort函数其实输入时排序的开始地址和结束地址。由于C++的数组名和指针等价，那么指针操作是以数组保存的变量大小为单位的，这么理解的话，buf + n就是要排序的结束位置在数组的终止地址。
#include <algorithm>sort(buf, buf + n); //buf是数组，n为排序元素个数
可以自定sort的排序规则，定义一个新的cmp函数，只要记得，当cmp返回true的时候，表示cmp第一个参数排在第二参数前面。
降序排列的写法：
#include <algorithm>bool cmp(int x, int y){return x > y;
}sort(buf, buf + n, cmp); //buf是数组，n为排序元素个数
结构体排序方法，可以定义cmp，也可重载<。
定义cmp：
struct E{char name[101];int age;int score;
}
int cmp(E a, E b){if(score != b.score) return score < b.score;int tmp = strcmp(name, b.name);if (tmp != 0): return tmp < 0;else return age < b.age;
}
重载<。
struct E{char name[101];int age;int score;bool operator < (const E &b) const{if(score != b.score) return score < b.score;int tmp = strcmp(name, b.name);if (tmp != 0): return tmp < 0;else return age < b.age;}
}数据结构
栈
#include <stack>stack<int> S;S.push(i);
int x = S.top();
S.pop();
优先级队列（堆）
#include <queue>priority_queue<int> Q; //默认是大根堆
priority_queue<int, vector<int>, greater<int>> Q; //小根堆Q.push(i);
int x = Q.top();
Q.pop();
字符串（string）
#include <string>string s;
cin >> s;
char str[] = "test";
s = str;s += 'c';
s += "string";
string b = "class";
s += b;string b = "class";
string a = "Two";
if (a <= b){cout << a;
}for (int i = 0; i < s.size(); i++){char c = s[i];
}s.erase(10, 8)string a = "asfasdfadfadfa"
string b = "dfs"int startPos = 0;
int pos = a.find(b, startPos);string a = "AAAA";
string b = "BBB";
a.insert(2, b);
cout << a << endl;
数学问题
% 运算符
(a * b) % c = (a%c * b%c) % c
(a + b) % c = (a%c + b%c) % c
最大公约数（GCD）
如果a,b全为0，gcd不存在；如果有一个0，那么gcd是非零的那个；如果都不为0，那么有：
gcd(a, b) = gcd(b, a % b);
求a,b的gcd代码：
int gcd(int a, int b){if (b == 0) return a;else return gcd(b, a % b);
}
最小公倍数（LCM）
a, b的最小公倍数为两数乘积除以它们最大公约数。
int lcm(int a, int b){return a * b / gcd(a, b);
}
求素数
基本解法是遍历。
#include <math.h>bool isPrime(int n) {for (int i = 2; i <= (int) sqrt(n) + 1; i++) {if (n % i == 0) {return false;}}return true;//是否为素数，别弄反
}
进阶一点的做法是素数筛法。使用下面的init()函数可以求前1000000中的前10000个素数，如果flag[i]==true，说明是素数。
int prime[1000001];
int flag[1000001];
int size;void init() {size = 0;for (int i = 1; i <= 1000000; i++) {flag[i] = false;}for (int i = 2; i <= 1000000; i++) {if (flag[i]) {continue;}prime[size++] = i;if(i >= 10000) continue;for (int j = i * i; j <= 1000000; j += i) {flag[j] = true;}}
}
二分求幂
快速的求a的b次幂。
long long pow(int a, int b){long long ans = 1;while(b != 0){if(b % 2){ans *= a;}b /= 2;a *= a;}return ans;
}
典型题目：
【九度OJ】题目1441：人见人爱 A ^ B
图论
并查集
并查集代码是通用的，背会就好。
#define size 1000int Tree[size];void init(){for (int i = 1; i <= n; i++) {Tree[i] = -1;//归位}
}int findRoot(int x) {if (Tree[x] == -1) {//如果找到了根元素return x;//返回的是当前的跟元素的数值，而不是-1} else {int temp = findRoot(Tree[x]);//找到根的值Tree[x] = temp;//把当前计算的这个值绑到根上return temp;}
}void union(int x, int y){int aRoot = findRoot(a);//找到根的值int bRoot = findRoot(b);if (aRoot != bRoot) {//不在同一棵树上Tree[aRoot] = bRoot;//添加到一起}
}
典型题目：
【九度OJ】题目1012：畅通工程
最小生成树（MST）
Kruskal算法：
- 初始时所有的节属于孤立的集合
- 按照边的权重递增遍历所有的边，若遍到的边两个顶点仍属于不同的集合，则确定该边为最小生成树上的一条边，并将这两个顶点分数的集合合并。
- 遍历完所有的边后，原图上所有节点属于同一集合则被选取的边和原图中所有节点构成最小生成树；否则原图不连通，最小生成树不存在。
#include<stdio.h>
#include<algorithm>using namespace std;
#define N 101
int Tree[N];struct Edge {int a, b;int cost;bool operator<(const Edge &A) const {return cost < A.cost;}
} edge[6000];int findRoot(int x) {if (Tree[x] == -1) {return x;} else {int temp = findRoot(Tree[x]);Tree[x] = temp;return temp;}
}int main() {int n;while (scanf("%d", &n) != EOF && n != 0) {int m = n * (n - 1) / 2;for (int i = 1; i <= m; i++) {//等号scanf("%d%d%d", &edge[i].a,&edge[i].b, &edge[i].cost);}sort(edge + 1, edge + m + 1);for (int i = 1; i <= N; i++) {//等号Tree[i] = -1;}int count = 0;for (int i = 1; i <= m; i++) {//等号int aRoot = findRoot(edge[i].a);int bRoot = findRoot(edge[i].b);if (aRoot != bRoot) {Tree[aRoot] = bRoot;count += edge[i].cost;}}printf("%d\n", count);}return 0;
}
典型题目：
【九度OJ】题目1017：还是畅通工程
最短路问题
Floyd算法
待补
Dijkstra算法
待补
拓扑排序
是对有向无环图（DAG）而言的，对其进行拓扑排序即求其中节点的一个拓扑序列，对于所有的有向边（U, V）（由U指向V），在该序列中节点U都排在节点V之前。
方法是每次选择入度为0的节点，作为序列的下一个节点，然后移除该节点和以从节点出发的所有边。
无论合适，当需要判断某个图是否属于有向无环图时，我们都需要立刻联想到拓扑排序。
搜索
广度优先搜索（BFS）
深度优先搜索（DFS）
递归
动态规划
最长递增子序列（LIS）
最长公共子序列（LCS）
背包
数据类型
- long long
long long使用64位二进来表示一个整数，可防止整数的溢出。
使用scanf, printf对long long操作的时候，要使用%lld。
技巧
-
如果需开辟大量内存空间的情况，都必须在函数外定义，即定义全局变量。
-
位运算。求模运算是运算符中比较耗时的一类，用位运算代替模2操作会大大提高该语句的执行效率。
如果你觉得内容还不错的话，可以关注我的公众号：「负雪明烛」，是我内容首发平台，后续会有更多精彩内容呈现。
