北邮机试打印资料

北邮复试的机试环节是可以带资料的。我整理了当时机试我准备的资料给需要的同学做参考。以下代码均可在机试环境中运行。

机试导入头文件

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
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<cstdio>
#include<vector>
#include<iterator>
#include<map>
#include<stack>
#include<queue>
#include<stdlib.h>
using namespace std;
```
## 结构体
``` c++
struct student
{
float score;
int id;
}a[101];
int comp(const student &a,const student &b)
{
return a.score>b.score;
}
int main()
{
int n,k;//n个人,求第k名的成绩
cin>>n>>k;
for (int i=1;i<=n;++i)
cin>>a[i].id>>a[i].score;
sort(a+1,a+n+1,comp);
cout<<a[k].id<<' '<<a[k].score<<endl;
return 0;
}

scanf & cin

  • 浮点数判定相等

    1
    fabs(a-b)<0.000001
  • 带逗号分隔的输入形式:

    1
    scanf("%d, %d",&a, &b);
  • getchar();用来吃进空格,有奇用!

补充:二维数组传参:尽量少用指针!

  • 合法形式:

    1
    2
    void Foo1(int array[30][30]);
    void Foo2(int array[][30]);
  • 不能省略高维的大小!不合法形式:

    1
    2
    void Foo3(int array[][]);
    void Foo4(int **array);//这种方式也是错误的

树与图

二叉链表建树套路

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//根据二叉排序树
struct node{
char letter;
node *lchild,*rchild;//
};
node *create(char c){
node *p = (node *)malloc(sizeof(node));
(*p).letter = c;
(*p).lchild = (*p).rchild = NULL;
}
node *insert(node *t,char x){//递归建树
if(t==NULL){//若树为空
t = create(x);
return t;
}
else if(x-'0' < t->letter-'0'){//插入左子树
t->lchild = insert(t->lchild, x);
}
else if(x-'0' > t->letter-'0'){
t->rchild = insert(t->rchild, x);
}
return t;
}
//根据中序后序建树
node *rebuild(char* post,char* in,int n){
if(n==0) return NULL;
char ch = post[n-1];
node *p = create(ch);
int i = 0;
while(i < n && in[i] != ch) i++;
int l_len = i;
int r_len = n-i-1;
if(l_len>0) (*p).lchild = rebuild(post,in,l_len);
if(r_len>0) (*p).rchild = rebuild(post+l_len,in+l_len+1,r_len);
return p;
}
//前序、后序遍历
void preorder(node *t)
{
if (ptr) {
printf("\t%d", ptr->data);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
//后序遍历
void postorder(node *t)
{
if (ptr) {
postorder(ptr->left_child);
postorder(ptr->right_child);
printf("\t%d", ptr->data);
}
}
//
int main(){
char tree[30];
while(scanf("%s",tree)!=EOF){
node *t = NULL;
for(int i = 0;i < strlen(tree);i++){
t = insert(t,in[i]);
}
preorder(t);
}
return 0;
}

图套路之建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Edge{
int nextNode;//下一个节点编号
int cost;//该边得权重
};
vector<Edge> edge[N];//vector模拟单链表
for(int i = 0;i < N;i++){
edge[i].clear();//清空单链表
}
//向单链表添加信息
Edge tmp;
tmp.nextNode = 3;
tmp.cost = 38;
edge[1].push_back(tmp)
//查询某个节点的所有邻接信息,对vector进行遍历
for(int i = 0;i < edge[2].size();i++){//对edge[2]进行遍历
int nextNode = edge[2][i].nextNode;
int cost = edge[2][i].cost;
}
//删除边
edge[1].erase(edge[1].begin()+i,edge.begin()+i+1)

floyd算法

1
2
3
4
5
6
7
8
for(int k = 1;k <=  N;k++){//每次我们选取的中间节点,Floyd算法的核心。
for(int i = 1;i <= N;i++){
for(int j = 1;j <= N;j++){
if(a[i][k] == N || a[k][j] == N) continue;
if(a[i][k]+a[k][j] < a[i][j]) a[i][j] = a[i][k] + a[k][j];
}
}
}

dijstra算法

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct E{
int next;// 临街的节点
int c;
};
vector<E> edge[1005];//邻接链表
int Dis[1005];
bool mark[1005];

int main(){
int n,m,a,b,c;

while(cin>>n>>m){//n个节点,m条边
for(int i = 1;i <= n;i++){
edge[i].clear();//邻接链表的初始化
}
for(int i = 1;i <= n;i++){
Dis[i] = -1;
mark[i] = false;
}
while(m--){
cin>>a>>b>>c;//a到b有一条权值c的路径
E tmp;
tmp.c = c;
tmp.next = b;
edge[a].push_back(tmp);//把b加入a的邻接链表, 针对无向图
tmp.next = a;
edge[b].push_back(tmp);//把a加入b的邻接链表
}

int newP = 1;//起点
Dis[1] = 0;
mark[1] = true;//求节点1到其他节点的最短路径 访问到了mark就要变为true.
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 cost = edge[newP][j].c;
if(mark[t]==true) continue;
if(Dis[t] == -1 || Dis[t] > Dis[newP] + cost){
Dis[t] = Dis[newP]+cost;
}
}
int min = 1000000;
for(int j = 1;j <= n;j++){//找到Dis数组中的最小值
if(mark[j]==true) continue;
if(Dis[j]==-1) continue;
if(Dis[j]<min){
min = Dis[j];
newP = j;//起点的更新 每次选完最小节点后 起点都要进行更新。
}
}
mark[newP] = true;
}
for(int i = 1;i <= n;i++){
cout<<Dis[i]<<" "<<endl;
}
}
}

拓扑排序

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
vector<int> edge[501];
queue<int> Q;

int main(){
int degree[501];//存储入度,拓扑排序判断的就是入度
int n,m;
while(cin>>n>>m){//n是节点个数,m是边的个数
for(int i = 0;i < 501;i++){//
degree[i] = 0;
edge[i].clear();//链表初始化
}
while(Q.empty()==false){//初始化,弹出队列中的元素知道Q为空。
Q.pop();
}
while(m--){//输入数据
int a,b;
cin>>a>>b;//输入a->b的一条边
degree[b]++;//入度加一
edge[a].push_back(b);//链表存b
}
for(int i = 1;i <= n;i++){//拓扑排序,找入度为0的节点。
if(degree[i]==0){
Q.push(i);
}
}
while(Q.empty()==false){
int now = Q.front();//访问队头元素
Q.pop();
cout<<now<<" ";
for(int k = 0;k < edge[now].size();k++){
degree[edge[now][k]]--;//类似二维数组的访问 因此now节点已经入队,所以入度要减去1
if(degree[edge[now][k][==0) Q.push(edge[now][k]);
}
}
cout<<endl;
}
}

动态规划

最长公共子序列与最长公共子串

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//最长公共子序列:输出最长序列长度
int lcse(string str1,string str2,vector<vector<int> >& vec){
int len1 = str1.size();
int len2 = str2.size();
vector<vector<int> > c(len1 + 1, vector<int>(len2 + 1,0));
for(int i = 0;i <= len1;i++){
for(int j = 0;j <= len2;j++){
if(i==0 || j==0){
c[i][j] = 0;
}
else if(str1[i-1] == str2[j-1]){
c[i][j] = c[i-1][j-1] + 1;
vec[i][j] = 0;
}
else if(c[i-1][j] >= c[i][j-1]){
c[i][j] = c[i-1][j];
vec[i][j] = 1;
}
else{
c[i][j] = c[i][j-1];
vec[i][j] = 2;
}
}
}
return c[len1][len2];
}
//最长公共子串:输出最长子串长度
int lcst(string str1,string str2,vector<vector<int > >& vec){
int len1 = str1.size();
int len2 = str2.size();
vector<vector<int> > c(len1+1,vector<int>(len2+1,0));
int result = 0;
for(int i = 0;i <= len1;i++){
for(int j = 0;j <= len2;j++){
if(i==0 || j==0){
c[i][j] = 0;
}
else if(str1[i-1] == str2[j-1]){
c[i][j] = c[i-1][j-1] + 1;
vec[i][j] = 0;
result = max(c[i][j],result);
}
else{
c[i][j] = 0;
}
}
}
return result;
}

//打印公共子序列/子串
void print_lcs(vector<vector<int> >& vec,string str,int i,int j){
if(i== 0 || j == 0){
return ;
}
if(vec[i][j] == 0){
print_lcs(vec,str,i-1,j-1);
printf("%c",str[i-1]);
}
else if(vec[i][j] == 1){
print_lcs(vec,str,i-1,j);
}
else{
print_lcs(vec,str,i,j-1);
}
}

int main(){
string str1,str2;
cin>>str1>>str2;
vector<vector<int> > vec(str1.size()+1,vector<int>(str2.size() +1, -1));
int ans = lcse(str1, str2, vec);
cout<<ans<<endl;
print_lcs(vec, str1, str1.size(), str2.size());
return 0;
}

模板类和库函数

模板类vector

  • 定义二维向量

    1
    vector<vector<int> > p(m, vector<int>(n,0)); //m*n的二维向量,注意空格 所有元素初始化为0
  • 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
// 定义一维向量
vector<type> v;
// 末尾插入一个元素
v.push_back(s);
// 任意位置插入元素
vector<int>::iterator it = v.begin()
v.insert(it+pos,elem);//插入一个
v.insert(it+pos,4,elem);//插入四个
v.insert(it+pos,起始,终止);

// 删除一个元素
v.erase(positon)
v.erase(v.end()-1)/v.erase(v.back());//删除最后一个元素
// 求和:将vector中所有元素加到0上
accumulate(v.begin(),v.end(),0)
// 反转:
reverse(v.begin(),v.end());
// 排序:
sort(data.begin(),data.end(),::greater<int>());
// iterator遍历
for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
// 清空vector
v.clear();
// 交换元素
swap(sentence[0],sentence[4]);

模板类algrithom

  • 不修改内容的序列操作

    • 统计返回值个数

      1
      count(v.begin(),v.end(),num)//统计6的个数
    • 统计符合调剂返回值个数

      1
      2
      bool BigThan5(int &n){ return n > 5; }
      count(v.begin(),v.end(),BigThan5)
    • 查找值/符合条件的值

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
              find(v.begin(),v.end(),num)
      find_if(v.begin(),v.end(),foo)
      ```

      ### 模板类stack&queue&map

      - stack&queue

      ``` c
      # 定义
      stack<int> s;
      queue<int> q;
      # 访问栈顶
      s.top()/s.front()/s.back()
      # 判断栈空/返回有效个数
      s.empty()/s.size()
      # 插入、删除、交换
      s.push()/s.pop()/s.swap()
  • map

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #初始化
    map<string,double> m
    #声明即插入
    m["Li"] = 123.4;
    #查找
    data_x = m.find(key);
    data_y = m[key];
    if(m.find(key)==maplive.end())//查找失败
    #遍历
    for(map<string,double>::iterator it = m.begin(); it != m.end(); ++it)
    {
    cout << it->first << ":" << it->second << endl;
    }
    #逆序遍历
    for(map<int,int>::reverse_iterator it = bag.rbegin();it!=bag.rend();it++)
    #删除
    m.erase(key);
  • multimap和multimap的排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #初始化
    multimap<int,int> bag;
    #插入数据
    bag.insert(make_pair(v,w));
    #排序
    vector<pair<int,int> > BAG(bag.begin(),bag.end())
    //按键升序
    sort(BAG.begin(),BAG.end());
    //按值升序
    sort(BAG.begin(),BAG.end(),cmp_by_value);

    bool cmp_by_value(const pair<int,int> a,const pair<int,int> b){
    if(a.first == b.first){
    return a.second<b.second;
    }
    else{
    return a.first>b.first;
    }
    }
    //遍历
    for(int i = 0;i < BAG.size();i++){
    cout<<BAG[i].first<<" "<<BAG[i].second<<endl;
    }

数学问题

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//浮点数判定相等
fabs(a-b)<0.000001
//将M进制的大数X转换为N进制
int M,N;
string X;
while(cin>>M>>N){
cin>>X;
int data[1010];//保存M进制下的各个位数
int output[1010];//保存N进制下的各个位数
memset(output,0,sizeof(output));
for(int i = 0;i < X.length();i++){
if(isalpha(X[i])){ data[i] = X[i]-'A'+10;}
else{ data[i] = X[i] - '0';}
int sum = 1,d = 0,len = X.length(),k = 0;
while(sum){
sum = 0;
for(int i = 0;i < len;i++){
d = data[i] / N;
sum += d;
if(i == len - 1){ output[k++] = data[i] % N;}
else{ data[i+1] += (data[i] % N) * M;}
data[i] = d;
}
}
if(k == 0){ output[k] = 0;k--;}
if(k == -1){ cout<<0<<endl;}
else{
for(int i = 0;i < k;i++){
if(output[k-i-1] > 9){ cout<<(char)(output[k-i-1]+'a'-10);}
else{ cout<<output[k-i-1];}
}
}
cout<<endl;
}
return 0;
}
//大数阶乘
int a[20001];//存储每一位的数字
int temp,digit,n,i,j = 0;
cin>>n;
a[0] = 1;//从1开始阶乘
digit = 1;//位数从第一位开始
for(int i = 2;i <= n;i++){
int num = 0;
for(j = 0;j < digit;j++){
temp = a[j]*i+num;//将一个数字的每一位数都乘i
a[j] = temp % 10;
num = temp/10;
}
while(num){
a[digit] = num%10;
num = num/10;
digit++;
}
}
for(int i = digit-1;i>=0;i--){
printf("%d",a[i]);
}
//判定素数
bool judge(int x){
if(x <= 1) return false;
for(int i = 2; i<(int)sqrt(x)+1;i++){
if(x % i == 0) return false;
}
return true;
}
//求两个数字的公约数
int gcd(int a,int b){
if(b==0) return a;// 递归的跳出条件是a mod b =5 ;0
else return gcd(b, a % b);
}

库函数 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#获取带空格的字符串
getchar();//专门吃回车
getline(cin,mystr);
#插入字符串
string s = "BUPT";
s.insert(position,string);
#尾部插入字符串
s.append(string);
s+=string;
#删除字符串
s.erase(position,length);
#比较字符串
strcmp(s1,s2);//相同返回0,不相同返回1;
#提取字符串
s.substr(position,length);
#查找字符串:str表示待查找的子串,position表示开始查找的下标/结束查找的下标
res_pos = s.find(str,positon);
res_pos = s.rfind(str,position)
//查找所有的bupt变成大写
while ((pos = s.find("bupt",pos)) != string::npos){
s.replace(pos, 4, "BUPT");
}
#字符串转换成其他类型
string str = "12345.67";
**atoi(str.c_str())**/atof(str)/atol(str)这个特别牛逼
#将整形转换为字符串
char(101)//输出e
//另外一种形式的
char str[100];
itoa(num, str, 10)//10为进制数
#代替:第19个字符串以及后面的5个字符用str的第7个字符以及后面的5个字符代替
s.replace(19,6,str3,7,6);//7&6可以选择
#比较:s1&s2是否相同
string s1="123",s2="123";
cout<<s1.compare(s2)<<endl;//0
#大小写转换
string s = "Hello world";
transform(s.begin(),s.end(),s.begin(),::toupper);
或者s[i] = toupper(s[i]);
#翻转字符串
string str = "song";
reverse(str.begin(),str.end());
  • 判定字符串是否结束

    1
    a[i] == '\0';//字符串最后一位的后面还有'\0'结束符
  • 字符串逆序套路:

    1
    2
    3
    4
    5
    6
    7
    while(left < right){
    temp = a[left];
    a[left] = a[right];
    a[right] = temp;
    left++;
    right--;
    }

ascii码对照表

请zzy824喝杯咖啡
0%