北邮复试机考模板
条评论北邮机考可以带纸质材料,所以整理这篇「板子」以备不时之需。
Update: 今年政策,不允许带纸质材料,以后有需要再更新。
头文件模板
1 | //#include <bits/stdc++.h> |
数学
素数
埃氏筛法
1 | const int SIZE = 1e7; |
快速幂
1 | typedef long long ll; |
矩阵快速幂
1 | struct node |
图论
最短路
floyd
1 | void floyd(){ |
并查集
初始化pre[]数组
1
2
3
4
5int pre[1000];
//初始化pre数组,让他们的前导点都记录为自己,即自己为根节点
for(int i=1;i<=n;i++) {
pre[i]=i;
}find()函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14int find(int x){
int r=x;
while(pre[r]!=r)//如果r的上级不是自己
r=pre[r];//那么r等于它的前导点,继续寻找,直到找到根节点
//下面这段起到路径压缩的作用
int i=x; int j;
while(i!=r){//如果当前查找的不是根结点(pre指向自己)
j=pre[i];//在改变上级之前用临时变量j记录下他的值
pre[i]=r;//更新前导点直接指向根节点
i=j;//让i指向其前导点,在下一次循环里面就会更新其前导点指向根节点
}
return r;
}join()函数
1
2
3
4
5
6
7
8
9void join(int p1,int p2){
int f1,f2;
f1 = find(p1);
f2 = find(p2); //分别查找根节点
//如果是不连通的,那么把这两个分支连起来
if(f1!=f2){
pre[f1]=f2;
}
}
计算几何
二维几何
1 | struct Point{ |
其它
类型转换
1 | int a = atoi(str.c_str()); |
字符串切割 strtok()
C 库函数 char *strtok(char *str, const char *delim) 分解字符串 str 为一组字符串,delim 为分隔符。
1 | int main () { |
String
1 | cin>>str; //读入有效字符直到遇到空格 |
STL
vector
1 | vector<int> v; |
map
1 | map<string, string> Smap; |
set 和 multiset
set 和 multiset 的用法一样,就是 multiset 允许重复元素。
1 | struct Node{ |
上面这段按照 x 从小到大排序,x 相同则按照 y 从大到小排序。
1 | set<int> v; //创建一个int类型的set容器 |
priority_queue
1 | q.size();//返回q里元素个数 |
在默认的优先队列中,优先级高的先出队;在默认的 int 型中先出队的为较大的数。
1 | priority_queue<int> q1; //大的先出队 |
1 | struct cmp{ |
1 | struct node{ |
- 本文链接:北邮复试机考模板
- 发布时间:2019年03月15日 - 9:01:26
- 更新时间:2021年02月03日 - 6:56:56
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享