北邮机考可以带纸质材料,所以整理这篇「板子」以备不时之需。

Update: 今年政策,不允许带纸质材料,以后有需要再更新。

头文件模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 //#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#define For(i,m,n) for(int i=m;i< n;i++)
#define FFor(i,m,n) for(int i=m;i<=n;i++)
#define bug(x) cout<<#x<<"="<<x<<endl;
#define inf 0x3f3f3f3f
#define Pi acos(-1.0)
using namespace std;
typedef long long ll;

数学

素数

埃氏筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int SIZE = 1e7;
int prime[SIZE]; //第i个素数
bool is_prime[SIZE]; //true表示i是素数

int slove(int n){
int p=0;
for(int i=0; i<=n; i++)
is_prime[i] = true; //初始化
is_prime[0] = is_prime[1] = false; //0,1不是素数
for(int i=2; i<=n; i++){
if(is_prime[i]){
prime[p++] = i;
for(int j=2*i; j<=n; j+=i) //将i的倍数全部设为false
is_prime[j] = false;
}
}
return p;
}

快速幂

1
2
3
4
5
6
7
8
9
10
typedef long long ll;  
ll mod_pow(ll x, ll n, ll mod){
ll res = 1;
while( n > 0 ){
if( n & 1 ) res = res * x % mod; //n&1 即 n%2
x = x * x % mod;
n >>= 1; //n >>= 1 即 n/=2
}
return res;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct node
{
int mat[MAXN][MAXN]; //矩阵
int row, col;
void init(){ //初始化為單位矩陣
memset(mat, 0, sizeof(mat));
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
mat[i][j] = (i==j);
}
}
}
};

node mod_mul(node a, node b, int p) //矩阵乘法
{
node ans;
ans.row = a.row;
ans.col = b.col;
memset(ans.mat, 0, sizeof(ans.mat));
for (int i = 0; i < ans.row; i++)
for (int j = 0; j < ans.col; j++)
for (int k = 0; k < a.col; k++)
{
ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
ans.mat[i][j] %= p;
}
return ans;
}

node mod_pow(node a, int k, int p) //矩陣快速冪
{
node ans;
ans.row = a.row;
ans.col = a.col;
ans.init();
while (k){
if (k & 1) ans = mod_mul(ans, a, p);
a = mod_mul(a, a, p);
k >>= 1;
}
return ans;
}

图论

最短路

floyd

1
2
3
4
5
6
7
8
void floyd(){
int i,j,k;
FFor(k,1,n)
FFor(i,1,n)
FFor(j,1,n)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j] = dis[i][k]+dis[k][j];
}

并查集

  1. 初始化pre[]数组

    1
    2
    3
    4
    5
    int pre[1000];
    //初始化pre数组,让他们的前导点都记录为自己,即自己为根节点
    for(int i=1;i<=n;i++) {
    pre[i]=i;
    }
  2. find()函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int 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;
    }
  3. join()函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void join(int p1,int p2){
    int f1,f2;
    f1 = find(p1);
    f2 = find(p2); //分别查找根节点
    //如果是不连通的,那么把这两个分支连起来
    if(f1!=f2){
    pre[f1]=f2;
    }
    }

计算几何

二维几何

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct Point{
double x,y;
};

double getS(Point a,Point b,Point c){ //返回三角形面积
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x - a.x))/2;
}

double getPS(Point p[],int n){ //返回多边形面积。必须确保 n>=3,且多边形是凸多边形
double sumS=0;
FFor(i,2,n-1){
sumS+=getS(p[1],p[i],p[i+1]);
}
return sumS;
}

Point getPZ(Point p[],int n){ //返回多边形重心
Point z;
double sumx = 0,sumy = 0;
double sumS = 0;
FFor(i,2,n-1){
double S = getS(p[1],p[i],p[i+1]);
sumS += S;
sumx += (p[1].x+p[i].x+p[i+1].x)*S;
sumy += (p[1].y+p[i].y+p[i+1].y)*S;
}
if(sumS==0){
z.x = 0,z.y = 0;
return z;
}
z.x = sumx / (sumS );
z.y = sumy / (sumS );
return z;
}

其它

类型转换

1
2
3
int a = atoi(str.c_str()); 
char x[5]; strcpy(x, str.c_str());
string str = to_string(50);

字符串切割 strtok()

C 库函数 char *strtok(char *str, const char *delim) 分解字符串 str 为一组字符串,delim 为分隔符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main () {
char str[80] = "This is - hushhw.cn - website";
const char s[2] = "-";
char *token;
/* 获取第一个子字符串 */
token = strtok(str, s);
/* 继续获取其他的子字符串 */
while( token != NULL ) {
printf( "%s\n", token );
token = strtok(NULL, s);
}
return(0);
}
/*
This is
hushhw.cn
website
*/

String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
cin>>str; //读入有效字符直到遇到空格
getline(cin, str); //读取字符直到遇到换行
getline(cin, str, 'a'); //直到遇到'a'结束,其中任何字符包括'\n'都可以读入
cout<<str<<endl;

s += str;
s.append(sh);
s.append(str, 5, 4);
s.append("hello STL", 5, 4);
s.append(5, 'x');
s.push_back('a');

s.insert(0, "hello");
s.insert(0, str, 0, 6);
s.insert(0, "that is cool",8);
s.insert(7, 1, ':');

s.erase(9, 18);

s.replace(15, 3, str, 0, 5);
s.replace(25, 3, "C++ Primer Plus", 4, 11);
cout << s << endl<<endl;

string hello = s.substr(9, 5);

if(s.find(hello) != string::npos){
cout<<"'hello' found at:"<<s.find(hello)<<endl;
}

STL

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> v;
vector<int> v2(10); //该容器暂有10个int元素,每个元素被赋初始值为0
vector<int> v3(5,99);//该容器有5个int元素,每个元素被赋值99
vector<int> v4(v2); //该容器拷贝v2,该容器具有10个值为0的元素。

v.push_back(10); //在v的尾部插入元素10
v.pop_back();//尾部删除元素

cout<<"在0位置的元素值为:"<<v.at(0)<<endl;
cout<<"在1位置的元素值为:"<<v[1]<<endl;

cout << "尾部数据的值为:" << v.back() << endl;
cout << "头部数据的值为:" << v.front() << endl;

cout << "vector中的元素个数为:" << v.size() << endl;
cout << "vector是否为空:" << v.empty() << endl;

swap(v[0],v[1]);
sort(v.begin(), v.end());
reverse(v.begin(), v.end());

vector<int>::iterator vItera = v.begin();
vItera = vItera + 2;
v.erase(vItera);

vector<int>::iterator vInsert = v.begin();
vInsert = vInsert + 2;
v.insert(vInsert, 777);

v.clear();

map

1
2
3
4
5
6
7
8
9
10
11
12
13
map<string, string> Smap;
Smap.insert(pair<string, string>("r000", "student_zero"));
Smap.insert(map<string, string>::value_type("r001", "student_one"));
Smap [ "r123" ] = "student_first" ;
int nsize = Smap.size();
for(iter = Smap.begin(); iter != Smap.end(); iter++)
cout<<iter->first<<" "<<iter->second<<endl;
iter = Smap.find("r123");
if(iter != Smap.end())
cout<<"Find, the value is "<<iter->second<<endl;
else
cout<<"Do not Find"<<endl;
int n = Smap.erase("r123");//如果删除了會返回1,否則返回0

set 和 multiset

set 和 multiset 的用法一样,就是 multiset 允许重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node{
int x,y;
};
struct classcomp{
bool operator()(const Node &a, const Node &b) const{
if(a.x != b.x) return a.x<b.x;
else return a.y>b.y;
}
};

set<Node, classcomp> st;
set<Node, classcomp>::iterator sit;
multiset<Node, classcomp> mt;
multiset<Node, classcomp> mit;

上面这段按照 x 从小到大排序,x 相同则按照 y 从大到小排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
set<int> v;		//创建一个int类型的set容器

int A[10]={9,5,8,6,4,2,3,7,0,1};
for(int i=0;i<10;i++){
v.insert(A[i]);
}
it=v.find(9);
if(v.find(c)!=v.end()){ //输出yes
printf("YES\n");
}else{
printf("NO\n");
}
v.erase (it); //输出 0 1 2 3 4 5 6 7 8
v.erase (v.find(0));//输出1 2 3 4 5 6 7 8

//lower_bound 返回指向首个不小于给定键的元素的迭代器
//upper_bound 返回指向首个大于给定键的元素的迭代器
set<int>::iterator itlower, itupper;
itlower = v.lower_bound(3);
itupper = v.upper_bound(6);
v.erase(itlower, itupper);//输出为 1 2 7 8,删除了3——6

v.count(i);//返回元素个数,0或1,可用来判断一个元素是否存在

priority_queue

1
2
3
4
5
q.size();//返回q里元素个数
q.empty();//返回q是否为空,空则返回1,否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素

在默认的优先队列中,优先级高的先出队;在默认的 int 型中先出队的为较大的数。

1
2
priority_queue<int> q1; //大的先出队
priority_queue<int, vector<int>, greater<int> > q2;//小的先出队
1
2
3
4
5
6
struct cmp{
bool operator() (int x, int y){
return x > y; //x小的优先级高
}
};
priority_queue<int, vector<int>, cmp> q;
1
2
3
4
5
6
7
8
9
10
struct node{
int x,y;
friend bool operator < (node a, node b){
return a.x > b.x; //结构体中,x 小的优先级高
//return a.x > b.x; //结构体中,x 大的优先级高
}
};
priority_queue<node> q;//定义方法
//在该结构中,y 为值,x 为优先级。
//通过自定义 operator< 操作符来比较元素中的优先级。