读研机试准备

经典入门

排序

// 所需头文件
#include <algorithm> // sort()
#include <string.h>  // strcmp()

// 对buf[n]升序排序
sort(buf, buf + n); 

// 对buf[n]采用比较函数cmp排序
bool cmp(T a, T b){
    return a.x < b.x;
}
sort(buf, buf + n, cmp);

// 结构体内重载运算符
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;
    }
}buf[100];
sort(buf, buf + 100);

日期

// 宏定义是否闰年
#define ISYEAR(x) ((x % 100 != 0 && x % 4 == 0 || x % 400 == 0)? 1: 0)

// 记录每个月天数
int dayOfMonth[13][2];

// 日期结构体
strut Date{
    int Day;
    int Month;
    int Year;
    void nextDay{
    	Day++;
    	if(Day > dayOfMonth[Month][ISYEAR(year)]){
    		Day = 1;
    		Month++;
    		if(Month > 12){
    			Month = 1;
    			Year++;
    		}
    	}
    }
}; 

// 保存预处理天数
int buf[5001][13][32];

查找

// 二分查找先排序
int buf[n];
sort(buf, buf + n);
int base = 0, top = n;
int ans = -1;
while(base <= top){
    int mid = (base + top) / 2;
    if(buf[mid] == target){
    	ans = mid;
    	break;
    }
    else if(buf[mid] < target)
    	base = mid + 1;
    else
    	top = mid - 1;
}
if(ans != -1){
    printf("%d",ans);
}

数据结构

// 所需头文件
#include <stack>

stack<int> S; // 定义栈元素类型

S.push(i); // 入栈

int x = S.top(); // 取栈顶元素

S.pop(); // 出栈

S.empty(); // 判断栈是否为空

S.size(); // 栈中元素个数
  • 利用堆栈对表达式进行求值
    • 1.设立两个堆栈,一个用来保存运算符,另一个用来保存数字
    • 2.在表达式首尾添加标记运算符,该运算符运算优先级最低
    • 3.从左到右依次遍历字符串,若遍历到运算符,则将其与运算符栈顶元素进行比较,若运算符栈栈顶运算符优先级小于运算符或者运算符栈为空,则将该运算符入栈。遍历字符串下一个元素
    • 4.若运算符栈顶运算符优先级大于该运算符,则弹出该栈顶运算符,再从数字栈中依次弹出两个栈顶元素,完成弹出的运算符对应的运算得到结果后,再将该结果入栈数字栈,重复比较此时栈顶运算符与当前遍历到的运算符优先级,视其优先级大小重复步骤3或步骤4
    • 5.若遍历到表达式中的数字,则直接压入数字栈
    • 6.若运算符堆栈中仅存有两个运算符且栈顶元素为我们人为添加的标记运算符,那么表达式运算结束,此时数字堆栈中唯一的数字即为表达式的值

哈夫曼树

// 所需头文件
#include <queue>
using namespace std;

priority_queue<int> Q; // 创建一个元素为int的堆Q,默认为大顶堆

priority_queue<int,vector<int>,greater<int>> Q; // 定义为小顶堆

Q.push(x); // 将x放入堆中

int a = Q.top(); // 取堆顶元素

Q.pop(); // 弹出堆顶元素,自动调整为一个新的小顶堆

Q.empty(); // 判断堆是否为空

Q.size(); // 堆中元素个数

// 自定义结构体
struct Node{
    int x, y;
    bool operator < (const Node& b)const{
        return y < b.y;
    }
}n[100];
priority_queue<Node> Q;
  • 哈夫曼树求法
    • 1.将所有结点放入集合K
    • 2.若集合K中剩余结点大于2个,则取出其中权值最小的两个结点,构造它们同时为某个新结点的左右子结点,该新结点是他们共同双亲结点,设定它的权值为其两个儿子结点的权值和。并将该父亲结点放入集合K。重复步骤2和步骤3
    • 3.若集合K中仅剩一个结点,该结点即为构造出的哈夫曼树的根节点,所有构造得到的中间结点的权值和即为该哈夫曼树的带权路径和

二叉树

// 树结点结构体
struct Node{
    Node *lchild;
    Node *rchild;
    char c;
} Tree[110];

// 申请一个结点空间,返回指向其的指针
int loc = 0;
Node *create(){
    Tree[loc].lchild = Tree[loc].rchild = NULL;
    return &Tree[loc++];
}

// 前序和中序构建二叉树
char str1[30],str2[30];
Node *build(int s1,int e1,int s2,int e2){
    Node* ret = create();
    ret->c = str1[s1];
    int rootIdx;
    for(int i = s2; i <= e2; i++){
    	if(str2[i] == str1[s1]){
    		rootIdx = i;
    		break;
    	}
    }
    if(rootIdx != s2){
    	ret->lchild = build(s1+1, s1+(rootIdx-s2), s2, rootIdx-1);
    }
    if(rootIdx != e2){
    	ret->rchild = build(s1+(rootIdx-s2)+1, e1, rootIdx+1, e2);
    }
    return ret;
}

// 后序遍历
void postOrder(Node *T){
    if(T->lchild != NULL)
    	postOrder(T->lchild);
    if(T->rchild != NULL)
    	postOrder(T->rchild);
    printf("%c",T->c);
}

二叉排序树

// 插入数字
Node *Insert(Node *T,int x){
    if(T == NULL){
        T = create();
        T->c = x;
        return T;
    }
    else if(x < T->c){
        T->lchild = Insert(T->lchild, x);
    }
    else if(x > T->c){
        T->rchild = Insert(T->rchild, x);
    }
    return T;
}
  • 插入数字x

    • 1.若当前树为空,则x为其根节点
    • 2.若当前结点大于x,则x插入其左子树;若当前结点小于x,则x插入其右子树;若当前结点等于x,则根据具体情况选择插入左右子树或者直接忽略
  • 删除数字

    • 1.利用某种遍历找到该结点
    • 2.若该结点为叶子结点,则直接删除它,即将其双亲结点中指向其的指针改为NULL。释放该结点空间
    • 3.若该结点仅不存在右子树,则直接将其左子树的根节点代替其位置后,删除该结点。即将其双亲结点指向其的指针改为指向其左子树的树根
    • 4.若该结点存在右子树,则找到右子树上中序遍历第一个被遍历到的结点,将被删除结点的数值改为右子树上最左下的数值后,删除最左下结点

数学问题

一般问题

// 最大公约数
int gcd(int a, int b){
    return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
int lcm(int a, int b){
    return a * b / gcd(a, b);
}

// 素数筛法
#include <math.h>
bool judge(int x){
    if(x <= 1)
    	return false;

    int bound = (int) sqrt(x) + 1;

    for(int i = 2; i < bound ; i++)
    	if(x % i == 0)
    		return false;
    
    return true;
}

// 列举素数
#define num 10000
int prime[num];
int primeSize = 0;
bool mark[num + 1];
void init(){
    for(int i = 2; i <= num ; i++){
    	if(mark[i] == true)
    		continue;
    	prime[primeSize++] = i;
    	for(int j = i * i; j <= num ; j += i)
    		mark[j] = true;
    }
}

分解素因数

  • 分解n!的素因子
    • 1.计算器清零,该计数器表示n!中将有几个p因子,即n!分解质因数后素因子p对应的幂指数
    • 2.计算n/p,有n/p个整数可以向n!提供一个p因子,则计数器累加n/p。若n/p为0,表示没有一个整数能向n!提供一个或一个以上的p因子,分解结束
    • 3.计算n/(pp),有n/(pp)个整数可以向n!提供两个p因子,则计数器累加n/(pp)。若n/(pp)为0,表示没有一个整数能向n!提供两个或两个以上的p因子,分解结束
    • 4.……

二分求幂

int qpow(int a,int b){
  int r = 1, base = a;
  while(b){
    if(b & 1)
    	r *= base;
    base *= base;
    b >>= 1;
  }
  return r;
}

高精度整数

// 结构体
#include <string.h>
#define maxDigits 1000
struct bigInteger{
    int digit[maxDigits];
    int size;
    void init(){
    	for(int i = 0; i < maxDigits; i++)
    		digit[i] = 0;
    	size = 0;
    }
    void set(char str[]){
    	init();
    	int L = strlen(str);
    	for(int i = L - 1, j = 0, t = 0, c = 1; i >= 0; i--){
    		t += (str[i] - '0') * c;
    		j++;
    		c *= 10;
    		if(j == 4 || i == 0){
    			digit[size++] = t;
    			j = 0;
    			t = 0;
    			c = 1;
    		}
    	}
    }
    void output(){
    	for(int i = size - 1; i >= 0; i--){
    		if(i != size - 1)
    			pritf("%04d",digit[i]);
    		else
    			printf("%d",digit[i]);
    	}
    	printf("\n");
    }
    bigInteger operator + (const bigInteger &A) const{
    	bigInteger ret;
    	ret.init();
    	int carry = 0;
    	for(int i = 0; i < A.size || i < size; i++){
    		int tmp = A.digit[i] + digit[i] + carry;
    		carry = tmp / 10000;
    		tmp %= 10000;
    		ret.digit[ret.size++] = tmp;
    	}
    	if(carry != 0){
    		ret.digit[ret.size++] = carry;
    	}
    	return ret;
    }
};

图论

预备知识

// 头文件
#include <vector>
using namespace std;

// 结构体表示一条边
struct Edge{
    int nextNode;
    int cost;
};

// vector模拟单链表
vector<Edge> edge[N];

// 初始化,清空单链表
for(int i = 0; i < N; i++)
    edge[i].clear();

// 添加信息
Edge tmp;
tmp.nextNode = 3;
tmp.cost = 38;
edge[1].push_back(tmp);

// 查询
for(int i = 0; i < edge[2].size(); i++){
    int nextNode = edge[2][i].nextNode;
    int cost = edge[2][i].cost;
}

// 删除结点1的单链表中edge[1][i]所对应的边信息
edge[1].erase(edge[1].begin() + i, edge[1].begin() + i + 1);

并查集

// 双亲表示法来表示各棵树
int Tree[N];

// 查找根结点与路径压缩递归版
int findRoot(int x){
    if(Tree[x] == -1)
        return x;
    else{
        int tmp = findRoot(Tree[x]);
        Tree[x] = tmp;
        return tmp;
    }
}

// 查找根结点与路径压缩非递归版
int findRoot(int x){
    int ret;
    int tmp = x;
    while(Tree[x] != -1)
        x = Tree[x];
    ret = x;
    x = tmp;
    while(Tree[x] != -1){
        int t = Tree[x];
        Tree[x] = ret;
        x = t;
    }
    return ret;
}

// 运用
int a  = findRoot(Tree[a]);
int b  = findRoot(Tree[b]);
if(a != b) //若不属于一个集合
    Tree[a] = b;

最小生成树(MST)

  • 最小生成树Kruskal算法
    • 1.初始时所有结点属于孤立的集合
    • 2.按照边权递增顺序遍历所有的边,若遍历到的边两个顶点仍分属不同的集合(该边即为连通这两个集合的边中权值最小的那条),则确定该边为最小生成树上的一条边,并将这两个顶点分属的集合合并
    • 3.遍历完所有边后,原图上所有结点属于同一个集合,则被选取的边和原图中所有结点构成最小生成树;否则原图不连通,最小生成树不存在
// 边结构体
struct Edge{
    int a,b;
    int cost;
    bool operator < (const Edge &A) const{
        return cost < A.cost;
    }
}edge[6000];

最短路径

  • 全源最短路径 -- Floyd算法
    • 在图的邻接矩阵表示法中,edge[i][j]表示由结点i和结点j中间不经过任何结点时的最短距离,那么依次为中间允许经过的结点添加结点1、结点2、……直到结点N,当添加完这些结点后,从结点i到结点j允许经过所有结点的最短路径长度就可以确定了,该长度即为原图上由结点i到结点j的最短路径长度
/****
设ans[k][i][j]为从结点i到结点j允许经过编号小于等于k的结点时
其最短路径长度。如上文,ans[0][i][j]即等于图的邻接矩阵表示中
edge[i][j]的值。我们通过如下循环,完成所有k对应的ans[k][i][j]
****/
#define wuqiong -1
int ans[n+1][n+1][n+1]0; // 初始化为-1,自己到自己为0,无向图赋值两次
for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= n; j++){
    		if(ans[k-1][i][k] == wuqiong || ans[k-1][k][j] == wuqiong){
    			ans[k][i][j] = ans[k-1][i][j];
    			continue;
    		}

    		if(ans[k-1][i][j] == wuqiong || ans[k-1][i][k] + ans[k-1][k][j] < ans[k-1][i][j])
    			ans[k][i][j] = ans[k-1][i][k] + ans[k-1][k][j];
    		else
    			ans[k][i][j] = ans[k-1][i][j];
    	}
    }
}

// 上述代码简化
#define wuqiong -1
int ans[n+1][n+1]; // 初始化为-1,自己到自己为0,无向图赋值两次
for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= n; j++){
    		if(ans[i][k] == wuqiong || ans[k][j] == wuqiong)
    			continue;
    		if(ans[i][j] == wuqiong || ans[i][k] + ans[k][j] < ans[i][j])
    			ans[i][j] = ans[i][k] + ans[k][j];
    	}
    }
}
  • 单源最短路径 -- Dijkstra算法
    • 1.初始化,集合K中加入结点1,结点1到结点1最短距离为0,到其他结点为无穷
    • 2.遍历与集合K中结点直接相邻的边(U,V,C),其中U属于集合K,V不属于集合K,计算由结点1出发按照已经得到的最短路到达U,再由U经过该边到达V时的路径长度。比较所有与集合K中结点直接相邻的非集合K结点该路径长度,其中路径长度最小的结点被确定为下一个最短路径确定的结点,其最短路径长度即为这个路径长度,最后将该结点加入集合K
    • 3.若集合K中已经包含了所有的点,算法结束;否则重复步骤2
// 链表元素结构体
struct E
{
    int next;
    int c;
};

// 邻接链表
vector<E> edge[101];

// 若为true则代表已加入集合K
bool mark[101]; 

//若mark[i]为true,则Dis[i]为已得的最短路径长度
int Dis[101]; 

// 大致流程
while(m--){
    int a, b, c;
    scanf("%d %d %d",&a,&b,&c);
    E tmp;
    tmp.c = c;
    tmp.next = b;
    edge[a].push_back(tmp);
    tmp.next = a;
    edge[b].push_back(tmp); // 由于这里是无向图,所以两边都添加进单链表中
}
for(int i = 1; i <= n; i++){ // 初始化
    Dis[i] = -1; // 所有结点为不可达
    mark[i] = false; // 所有结点都不属于集合K
}
Dis[1] = 0; // 得到最近的点为结点1,长度为0
mark[1] = true; // 将结点1加入集合K
int newP = 1; // 当前集合k中加入的新结点为newP,即其值1
for(int i = 1; i < n; i++){ // 循环n-1次
    for(int j = 0; j < edge[newP].size(); j++){
    	int t = edge[newP][j].next;
    	int c = edge[newP][j].c;
    	if(mark[t] == true)
    		continue;
    	if(Dis[t] == -1 || Dis[t] > Dis[newP] + c)
    		Dis[t] = Dis[newP] + c;
    }
    int min = 0x7fffffff;  //最小值初始化为一个大整数,为找最小值做准备
    for(int j = 1; j <= n; j++){
    	if(mark[j] == true)
    		continue;
    	if(Dis[j] == -1)
    		continue;
    	if(Dis[j] < min){
    		min = Dis[j];
    		newP = j;
    	}
    }
    mark[newP] = true;
}

拓扑排序

  • 条件:有向无环图
  • 首先,所有有入度的结点均不可能排在第一个。那么,选择一个入度为0的结点,作为序列的第一个结点。当该结点被选为序列的第一个顶点后,将该点从图中删去,同时删除以该结点为弧尾的所有边,得到一个新图。那么这个新图的拓扑序列即为原图的拓扑序列中除去第一个结点后剩余的序列。同样,在新图上选择一个入度为0的结点,将其作为原图的第二个结点,并在新图中删去该点以及以点为弧尾的边。这样又得到了一张新图,重复同样的方法,直到所有的结点和边都从原图中删去。若在所有结点尚未被删去时即出现了找不到入度为0的结点的情况,则说明剩余的结点形成一个环路,拓扑排序失败,原图不存在拓扑序列。
// 头文件
#include <queue>

// 建立一个队列
queue<int> Q;

// 入队
Q.push(x);

// 读取队头元素
x = Q.front();

// 队头元素弹出
Q.pop();

// 判断队列是否为空
Q.empty();

搜索

广度优先搜索(BFS)

  • 关键字:
    • 1.状态。我们确定求解问题中的状态。通过状态的转移扩展,查找遍历所有的状态,从而从中寻找我们需要的答案
    • 2.状态扩展方式。在广度优先搜索中,我们总是尽可能扩展状态,并将先扩展得出的状态先进行下一次扩展。在解答树上变现为按层次遍历所有状态
    • 3.有效状态。对有些状态我们并不对其进行再一次扩展,而是直接舍弃它。因为根据问题分析可知,目标状态不会由这些状态经过若干次扩展得到,即目标状态不可能存在其在解答树上的子树上,所以直接舍弃
    • 4.队列。为了实现先得出的状态先进行扩展,我们使用队列,将得到的状态依次放入队尾,每次取队头元素进行扩展
    • 5.标记。为了判断哪些状态是有效的,哪些是无效的,我们往往使用标记
    • 6.有效状态数。问题中的有效状态数与算法的时间复杂度同数量级,所以在进行搜索之前必须估算其是否在我们可以接受的范围内
    • 7.最优。广度优先搜索常被用来解决最优值问题,因为其搜索到的状态总是按照某个关键字递增,这个特性非常适合求解最优值问题