北邮机试打印资料

Posted on | Post modified: | In | Visitors:
Words count in article: 3,353 | Reading time ≈ 18分钟

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

机试导入头文件

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%