目录

数据结构实验

第一次作业

第二次作业

第三次作业

第四次作业

数据结构课程作业

第一次作业

第二次作业

第三次作业

数据结构实验

第一次作业

T1

题目描述

新年快到了，天勤准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。
输入
第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。
输出
对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

样例输入

2
25608
24027

样例输出

7680
16016

代码

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
#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            res = res - res / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        res = res - res / n;
    return res;
}
int main()
{
    int CN;
    cin >> CN;
    for (int i = 0; i < CN;i++){
        int n;
        cin >> n;
        cout << f(n) << endl;
    }
        return 0;
}

T2

题目描述

给你一个正整数n，请问有多少个比n小的且与n互质的正整数？
输入
输入包含多组测试数据。每组输入是一个正整数n（n<=1000000000）。当n=0时，输入结束。
输出
对于每组输入，输出比n小的且与n互质的正整数个数。

样例输入

7
12
0

样例输出

6
4

代码

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
#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            res = res - res / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        res = res - res / n;
    return res;
}
int main()
{
    while(1){
        int n;
        cin >> n;
        if(n==0)
            break;
        cout << f(n)<<endl;
    }
        return 0;
}

T3

题目描述

n个人围成一圈，按1到n的顺序编号。从第一个人开始报数（从1到m报数），凡报到m的人退出圈子，问最后留下的是原来的第几号。
输入
首先输入两个正整数n和m，n表示n个人围一个圈子（n>=2），m表示从1报数到m的人退出圈子（1=<m）。
输出
最后剩下的人的编号。

样例输入

2 3

样例输出

2

代码

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
#include<bits/stdc++.h>
using namespace std;
struct node{
    int id;
    node* next;
    node(int n):id(n),next(nullptr){}
};
void josephus(int n,int m){
    node* tail= new node(1);
    node* head=tail;
    for(int i=2;i<=n;i++){
        tail->next= new node(i);
        tail=tail->next;
    }
    tail->next=head;
    node* pre=tail;
    node* p=pre->next;
    while(p!=pre){
        for(int i=1;i<m;i++){
            pre=p;
            p=p->next;
        }
        pre->next=p->next;
        delete p;
        p=pre->next;
    }
    cout<<p->id;
}
int main()
{
    int n,m;
    cin>>n>>m;
    josephus(n,m);
    return 0;
}

T4

题目描述

编写程序演示把一个10进制整数转换为R进制的转换结果。
输入
正整数N和R，空格分隔
N是输入的十进制数，R需要转换的进制数，2<=R<=20
输出
将10进制整数转换为R进制的转换结果，超过9的数字符号显示为A、B、C……Z等字母。

样例输入

10 16

样例输出

A

代码

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
#include<bits/stdc++.h>
using namespace std;
string f(int n,int R)
{
    if(n==0)
        return "0";
    string res = "";
    while(n>0){
        int yu = n % R;
        if(yu<=9){
            res += to_string(yu);
        }
        else{
            yu -= 10;
            res += static_cast<char>('A' + yu);
        }
        n /= R;
    }
    reverse(res.begin(), res.end());
    return res;
}
int main()
{
    int n,R;
    cin >> n >> R;
    cout << f(n, R);
}

T5

题目描述

输入两个整数的求和式，比如1+2=，输出求和式和对应结果。请编程实现。
输入
一个求和式，形如a+b=。
输出
求和式及对应结果。

样例输入

1+2=

样例输出

1+2=3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
long long f(string str){
    int a;
    for (int i = 0; i < str.size();i++){
        if(str[i]=='+'){
            a = i;
            break;
        }
    }
    long long num1 = stoll(str.substr(0,a));
    long long num2 = stoll(str.substr(a + 1, str.size() - 2 - a));
    return num1 + num2;
}
int main()
{
    string str;
    cin >> str;
    cout << str << f(str);
    return 0;
}

T6

题目描述

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值(保留6位小数)。

样例输入

* + 11.0 12.0 + 24.0 35.0

样例输出

1357.000000

代码

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
#include <bits/stdc++.h>
using namespace std;
bool isOperator(const string &token)
{
    return token == "+" || token == "-" || token == "*" || token == "/";
}
double calculate(const string &op, double a, double b)
{
    if (op == "+")
        return a + b;
    if (op == "-")
        return a - b;
    if (op == "*")
        return a * b;
    if (op == "/")
        return a / b;
    return 0;
}
int main()
{
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<string> tokens;
    string token;
    while (ss >> token)
    {
        tokens.push_back(token);
    }
    stack<double> st;
    for (int i = tokens.size() - 1; i >= 0; --i)
    {
        if (!isOperator(tokens[i]))
        {
            st.push(stod(tokens[i]));
        }
        else
        {
            double a = st.top();
            st.pop();
            double b = st.top();
            st.pop();
            double result = calculate(tokens[i], a, b);
            st.push(result);
        }
    }
    cout << fixed << setprecision(6) << st.top() << endl;
    return 0;
}

T7

题目描述

上体育课的时候，老师已经把班级同学排成了两个队列，而且每个队列都是按照从低到高排好队，现在需要把两个队列合并，合并后需要保证还是从低到高排列。合并队列，你能编程实现吗？
输入
第1行为n，表示开始排成的每个队列的长度。第2、3行是代表从小到大的n个整数，每行的整数间有一个空格间隔。
输出
输出占一行，为从小到大的整数，每个整数间间隔一个空格。

样例输入

5
1 3 5 8 15
2 3 4 6 9

样例输出

1 2 3 3 4 5 6 8 9 15

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> vec1(n);
    vector<int> vec2(n);
    vector<int> vec3(2*n);
    for (int i = 0; i < n;i++){
        cin >> vec1[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> vec2[i];
    }
    int p = 0, q = 0,r=0;
    while(p<n&&q<n){
        if(vec1[p]<vec2[q]){
            vec3[r++] = vec1[p++];
        }
        else{
            vec3[r++] = vec2[q++];
        }
    }
    while(p<n){
        vec3[r++] = vec1[p++];
    }
    while (q < n)
    {
        vec3[r++] = vec2[q++];
    }
    for (int i = 0; i < 2 * n;i++){
        cout << vec3[i] << " ";
    }
    return 0;
}

第二次作业

T1

题目描述

给你若干个字符串，请编程输出每个字符串的子串个数。
输入
若干个字符串，每个字符串占一行，字符串中不含空格，长度最大为1000。
输出
对应每一行的字符串，输出该字符串子串的个数。

样例输入

abc
apple
software

样例输出

7
16
37

代码

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    while(cin>>str){
        int n = str.size();
        cout << n * (n + 1) / 2+1<<endl;
    }
    return 0;
}

T2

题目描述

给你一个目标串，请查找在给目标串中是否存在模式串，存在就输出第一个模式串在目标串中出现的位置。
输入
占两行，第一行是目标串（长度小于1000），第二行为模式串（长度小于100）。
输出
输出模式串在目标串中出现的位置，即模式串匹配到目标串时第一个字符在目标串的位置（注意从1开始描述字符开始位置），不能匹配时输出0.

样例输入

appleorange
orange

样例输出

6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int f(string x,string y){
    for (int i = 0; i <= x.size() - y.size(); i++)
    {
        if (x.substr(i, y.size()) == y)
        {
            return i+1;
        }
    }
    return 0;
}
int main()
{
    string x,y;
    cin >> x>>y;
    cout << f(x, y);
    return 0;
}

T3

题目描述

在一个N行N列的方阵(或称N阶方阵)中，从左上角到右下角这一斜线上有N个数据元素，这个斜线称为方阵的主对角线。给你一个方阵，请求方阵主对角线上数据的和。
输入
第一行是N（N<100），表示下边是一个N阶方阵。接下来N行N列用空格间隔放置正整数（int型）。
输出
N阶方阵主对角线上数据的和。

样例输入

3
1 2 3
1 2 3
1 2 3

样例输出

6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            int x;
            cin >> x;
            if(i==j){
                sum += x;
            }
        }
    }
    cout << sum;
    return 0;
}

T4

题目描述

给你一个N行N列的方格矩阵，从外圈按顺时针依次填写自然数，这会构成一个螺旋阵，你能编程实现吗？
比如5行5列的情况如下：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输入
输入一个正整数数N（N<100）。
输出
输出符合题意的螺旋阵。

样例输入

5

样例输出

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<vector<int>> res(n, vector<int>(n, 0));
    int quan = 0, k = 1;
    while (2 * quan < n)
    {
        for (int i = quan; i < n - quan; i++)
        {
            res[quan][i] = k++;
        }
        for (int i = quan + 1; i < n - quan; i++)
        {
            res[i][n - quan - 1] = k++;
        }
        if (quan < n - quan - 1)
        {
            for (int i = n - quan - 2; i >= quan; i--)
            {
                res[n - quan - 1][i] = k++;
            }
        }
        if (quan < n - quan - 1)
        {
            for (int i = n - quan - 2; i > quan; i--)
            {
                res[i][quan] = k++;
            }
        }
        quan++;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

T5

题目描述

有三根标为A,B,C的柱子，A柱子上从上到下按金字塔状依次叠放着n个半径从1厘米到n厘米的的圆盘，要把A上的所有盘子移动到柱子C上，中间可以临时放在B上，但每次移动每一根柱子上都不能出现大盘子在小盘子上方的情况，要求用最少的移动次数完成，请编程模拟每次移动。
输入
占一行，为整数n（n<64），表示盘子数。
输出
把A上的所有盘子移动到柱子C上，每次只能移动一个盘子，输出移动每一次过程。每次移动占一行，第一个数表示第几步移动，第二个数是移动的盘子的半径，然后是从哪个柱子移动到哪个柱子。

样例输入

2

样例输出

1 1 A->B
2 2 A->C
3 1 B->C

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int k = 1;
void Hanoi(int n,char x,char y,char z){
    if(n==1){
        cout << k <<" " << n << " " << x << "->" << z <<endl ;
        k++;
    }
    else{
        Hanoi(n - 1, x, z, y);
        cout <<k<< " " << n << " " << x << "->" << z <<endl;
        k++;
        Hanoi(n - 1, y, x, z);
    }
}
int main()
{
    int n;
    cin >> n;
    Hanoi(n, 'A', 'B', 'C');
    return 0;
}

T6

题目描述

已知一颗树的节点间关系，请编程实现该树的先根遍历。
输入
若干行，每行描述了一组双亲节点和孩子节点的关系序偶对（每个节点用不同的大写字母表示，节点小于26个）。且树的度小于5。
输出
该树的先根遍历序列，序列中每个字母用空格隔开。

样例输入

B E
B F
A B
A C

样例输出

A B E F C

代码

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
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, vector<char>> mp;
void f(char root){
    cout << root<<" ";
    for (int i = 0; i < mp[root].size();i++){
        f(mp[root][i]);
    }
}
int main()
{
    char x, y;
    vector<int> v(26, 0);
    while(cin>>x&&cin>>y){
        mp[x].push_back(y);
        int xx = int(x - 'A');
        if(v[xx]==0){
            v[xx] = 1;
        }
        xx = int(y - 'A');
        v[xx] = 2;
    }
    char root;
    for (int i = 0; i < 26;i++){
        if(v[i]==1){
            root = char(i + 'A');
        }
    }
    f(root);
    return 0;
}

T7

题目描述

已知一颗树的节点间关系，请编程实现该树的后根遍历序列。
输入
若干行，每行描述了一组双亲节点和孩子节点的关系序偶对（每个节点用不同的大写字母表示，节点小于26个）。且树的度小于5。
输出
该树的后根遍历序列，序列中每个字母用空格隔开。

样例输入

B E
B F
A B
A C

样例输出

E F B C A

代码

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
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, vector<char>> mp;
void f(char root){
    for (int i = 0; i < mp[root].size();i++){
        f(mp[root][i]);
    }
    cout << root<<" ";
}
int main()
{
    char x, y;
    vector<int> v(26, 0);
    while(cin>>x&&cin>>y){
        mp[x].push_back(y);
        int xx = int(x - 'A');
        if(v[xx]==0){
            v[xx] = 1;
        }
        xx = int(y - 'A');
        v[xx] = 2;
    }
    char root;
    for (int i = 0; i < 26;i++){
        if(v[i]==1){
            root = char(i + 'A');
        }
    }
    f(root);
    return 0;
}

第三次作业

T1

题目描述

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。对于每一个结点至多只有两棵子树的一类树，称其为二叉树。二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
在本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中的一种先序遍历和两种中序遍历的算法分别输出每一个非空节点。
输入
输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。
输出
共有三行，每一行包含一串字符，表示分别按先序、中序、中序得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

样例输入

ABC DE G F

样例输出

A B C D E G F
C B E G D F A
C B E G D F A

代码

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
#include <bits/stdc++.h>
using namespace std;
struct root{
    char id;
    root *left, *right;
    root(char id):id(id){}
};
root* buildtree(string &tree,int &k){
    if(k>=tree.size()||tree[k]==' '){
        return nullptr;
    }
    root *r=new root(tree[k]);
    k++;
    r->left=buildtree(tree,k);
    k++;
    r->right = buildtree(tree, k);
    return r;
}
void pre(root* r){
    if(r){
        cout << r->id << " ";
        pre(r->left);
        pre(r->right);
    }
}
void in(root *r)
{
    if (r)
    {
        in(r->left);
        cout << r->id << " ";
        in(r->right);
    }
}
int main()
{
    string tree;
    getline(cin, tree);
    int k = 0;
    root *r = buildtree(tree, k);
    pre(r);
    cout << endl;
    in(r);
    cout << endl;
    in(r);
    cout << endl;
    return 0;
}

T2

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有叶子结点的路径长度与权值的乘积之和。
输入
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出
输出权值。

样例输入

2
2 8
3
5 11 30

样例输出

10
62

代码

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
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int weight;
    node *left, *right;
    node(int weight, node *left, node *right) : weight(weight), left(left), right(right) {}
    node() {}
};
struct cmp
{
    bool operator()(node *a, node *b)
    {
        return a->weight > b->weight; 
    }
};
int main()
{
    int n;
    node *n1, *n2, *n3;
    while (cin >> n)
    {
        priority_queue<node *,vector<node*>,cmp> pq;
        while (n--)
        {
            int w;
            cin >> w;
            node *n1 = new node(w, nullptr, nullptr);
            pq.push(n1);
        }
        while (pq.size() > 1)
        {
            n1 = pq.top();
            pq.pop();
            n2 = pq.top();
            pq.pop();
            n3 = new node(n1->weight + n2->weight, n1, n2);
            pq.push(n3);
        }
        queue<node *> q;
        int depth = 0;
        int sum = 0;
        q.push(pq.top());
        while (!q.empty())
        {
            int m = q.size();
            while (m--)
            {
                n1 = q.front();
                if (n1->left && n1->right)
                {
                    q.push(n1->left);
                    q.push(n1->right);
                }
                else
                {
                    sum += depth * n1->weight;
                }
                q.pop();
            }
            depth++;
        }
        cout << sum << endl;
    }
    return 0;
}

T3

题目描述

假设二叉树中的所有键值都是不同的正整数。唯一的二元树可以通过给定的后序和顺序遍历序列，或前序和顺序遍历序列来确定。但是，如果仅给出后序和前序遍历序列，则相应的树可能不再是唯一的。
现在给出一对后序和前序遍历序列，您应该输出树的相应的中序遍历序列。如果树不是唯一的，只需输出其中任何一个。
输入
每个输入文件包含一个测试用例。对于每种情况，第一行给出正整数N（≤30），即二叉树中的节点总数。第二行给出预订序列，第三行给出后序序列。一行中的所有数字都用空格分隔。
输出
对于每个测试用例，如果树是唯一的，则首先是行中的Yes，否则是No。然后在下一行中打印相应二叉树的中序遍历序列。如果解决方案不是唯一的，那么任何答案都可以。保证至少存在一种解决方案。一行中的所有数字必须用一个空格分隔，并且行的末尾不能有额外的空格。

样例输入

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

样例输出

Yes
2 1 6 4 7 3 5

代码

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
#include <bits/stdc++.h>
using namespace std;
vector<int> in, pre, post;
bool flag = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight)
{
    if (preLeft == preRight)
    {
        in.push_back(pre[preLeft]);
        return;
    }
    if (pre[preLeft] == post[postRight])
    {
        int i = preLeft + 1;
        while (i <= preRight && pre[i] != post[postRight - 1])
            i++;
        if (i - preLeft > 1)
            getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
        else
            flag = false;
        in.push_back(post[postRight]);
        getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
    }
}
int main()
{
    int n;
    cin>>n;
    pre.resize(n), post.resize(n);
    for (int i = 0; i < n; i++)
        cin>>pre[i];
    for (int i = 0; i < n; i++)
        cin>>post[i];
    getIn(0, n - 1, 0, n - 1);
    if(flag){
        cout << "Yes"<<endl;
    }
    else{
        cout << "No"<<endl;
    }
    for (int i = 0; i < in.size(); i++)
        cout<<in[i]<<" ";
    return 0;
}

T4

题目描述

一个迷宫地图中，多个房间由单向通道相连，房间号从1到N依次编号。你能编程求解任意房间间的最短路径长度吗？
输入
第一行是迷宫中的房间数N和单项通道数M（0<N,M<100），接下来M行，每行三个数x,y,z，表示一个通道是从x到y,且通道长度是z(z<1000）。
最后一行是start和end，分别是起点房间号和终点房间号。
输出
输出起点房间号和终点房间号间的最短路径长度。如果没有通路，输出STOP。

样例输入

7 9
1 2 3
1 3 2
3 4 2
6 3 1
2 6 3
6 7 6
2 5 4
5 4 2
5 7 5
1 7

样例输出

12

代码

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
#include <bits/stdc++.h>
using namespace std;
struct State
{
    int id;
    int disfromstart;
    State(int id, int disfromstart) : id(id), disfromstart(disfromstart) {}
    bool operator>(const State &other) const{
        return disfromstart > other.disfromstart;
    }
};
vector<int> Dijkstra(vector<vector<pair<int, int>>> &graph, int start)
{
    vector<int> disTo(graph.size(), INT_MAX);
    disTo[start] = 0;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push(State(start, 0));
    while (!pq.empty()){
        State curstate = pq.top();
        pq.pop();
        int curid = curstate.id;
        int curdis = curstate.disfromstart;
        if (curdis > disTo[curid])
            continue;
        for (auto &neighbors : graph[curid]){
            int nextid = neighbors.first;
            int nextdis = neighbors.second;
            int newdis = nextdis + curdis;
            if (newdis < disTo[nextid]){
                pq.push(State(nextid, newdis));
                disTo[nextid] = newdis;
            }
        }
    }
    return disTo;
}
int main()
{
    int n, m;
    cin>>n>>m;
    vector < vector<pair<int, int>>> graph(n);
    while(m--){
        int room1, room2, length;
        cin >> room1 >> room2 >> length;
        graph[room1 - 1].push_back({room2 - 1, length});
    }
    int start, end;
    cin >> start >> end;
    vector<int> disTo = Dijkstra(graph, start - 1);
    int res=disTo[end-1];
    if(res==INT_MAX){
        cout << "STOP";
    }
    else{
        cout << res;
    }
    return 0;
}

T5

题目描述

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。
输入
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。
输出
只有一个整数，即最小生成树的总代价。请注意行尾输出换行。

样例输入

4
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0

样例输出

6

代码

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
#include <bits/stdc++.h>
using namespace std;
class UF
{
public:
    int _count;
    vector<int> parent;
    UF(int n){
        _count = n;
        for (int i = 0; i < n; i++){
            parent.push_back(i);
        }
    }
    int find(int p){
        if (parent[p] != p){
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }
    int count(){
        return _count;
    }
    bool isconnected(int p, int q){
        return find(p) == find(q);
    }
    void unionset(int p, int q){
        if (isconnected(p, q))
            return;
        parent[find(p)] = find(q);
        _count--;
    }
};
struct edge{
    int x, y;
    int weight;
    edge(int x,int y,int weight):x(x),y(y),weight(weight){}
};
struct cmp
{
    bool operator()(edge a, edge b){
        return a.weight > b.weight; 
    }
};
int main()
{
    int n ;
    cin>>n;
    priority_queue<edge, vector<edge>, cmp> pq;
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            int w;
            cin >> w;
            if(j>i&&w>0){
                pq.push(edge(i, j, w));
            }
        }
    }
    UF uf(n);
    int sum = 0;
    while(uf.count()>1){
        edge eg=pq.top();
        pq.pop();
        if(uf.isconnected(eg.x,eg.y)){
            continue;
        }
        uf.unionset(eg.x, eg.y);
        sum += eg.weight;
    }
    cout << sum;
    return 0;
}

第四次作业

T1

题目描述

在一个机器人王国里，围绕首都分N层构建卫星城市。以首都为圆心，以路相连分出两个卫星城在第一个层，然后每个卫星城又有路相连分出两个卫星城在下一层，但每条路的长度不同。第N层的卫星城不再分出新的卫星城。现在人类只探知到所有直接相连的城市间的路程，你能计算某个卫星城到达首都的路程吗？
输入
第一行为N，表示机器人王国里有N层卫星城，N最大为10。从第二行开始，共2N+1-2行，每行分别是城市的代号到其分出的卫星城的代号和它们间的路程。 代号用若干个字母表示，直连路程最大为100。最后一行是某卫星城的代号。
输出
根据最后一行的卫星城代号，求该卫星城到首都的路程。

样例输入

2
A F 20
B D 100
G A 5
G B 10
A C 6
B E 30
D

样例输出

110

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;
    int m = 1 << (n + 1);
    m -= 2;
    unordered_map<string, string> tree;
    unordered_map<string, int> path;
    for (int i = 0; i < m;i++){
        string x, y;
        int length;
        cin >> x >> y >> length;
        tree[y] = x;
        path[y] = length;
    }
    int res = 0;
    string cur;
    cin >> cur;
    while(path[cur]!=0){
        res+=path[cur];
        cur = tree[cur];
    }
    cout << res;
    return 0;
}

T2

题目描述

给你一个有向图的所有顶点有序对，顶点用1~n编号，每个有序对描述有向边，请编程求解从1到任意一个顶端i的最短路径长度。
输入
第一行是n和m,分别表示顶点数（n<100）和有向边数(m<100)。
从第二行开始n行，对应三个数，前两个表示顶点有序对，第三个数表示边的权。
最后一行i，表示要求解从1到顶点i的最短路径长度。
输出
从1到顶点i的最短路径长度。

样例输入

4 5
1 2 4
1 3 6
2 3 1
3 4 6
2 4 7
3

样例输出

5

代码

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
#include <bits/stdc++.h>
using namespace std;
struct State
{
    int id;
    int disfromstart;
    State(int id, int disfromstart) : id(id), disfromstart(disfromstart) {}
    bool operator<(const State &other) const
    {
        return disfromstart > other.disfromstart;
    }
};
vector<int> Dijkstra(vector<vector<pair<int, int>>> &graph, int start)
{
    vector<int> disTo(graph.size(), INT_MAX);
    disTo[start] = 0;
    priority_queue<State> pq;
    pq.push(State(start, 0));
    while (!pq.empty())
    {
        State curstate = pq.top();
        pq.pop();
        int curid = curstate.id;
        int curdis = curstate.disfromstart;
        if (curdis > disTo[curid])
            continue;
        for (auto &neighbors : graph[curid])
        {
            int nextid = neighbors.first;
            int nextdis = neighbors.second;
            int newdis = nextdis + curdis;
            if (newdis < disTo[nextid])
            {
                pq.push(State(nextid, newdis));
                disTo[nextid] = newdis;
            }
        }
    }
    return disTo;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    while (m--)
    {
        int point1, point2, length;
        cin >> point1 >> point2 >> length;
        graph[point1 - 1].push_back({point2 - 1, length});
    }
    int end;
    cin >> end;
    vector<int> disTo = Dijkstra(graph, 0);
    int res = disTo[end - 1];
    cout << res;
    return 0;
}

T3

题目描述

有一项大的工程，工程中有许多前后依赖的子任务，每个子任务都规划了完成需要的天数，假设给出用字母表示的事件结点，整个工程的开始事件用A表示，工程结束事件用Z表示，用事件结点有序对表示一个子任务的开始和结束，并给出每个子任务完成需要的天数。请编程求解完成这个工程的最短天数。
输入
第一行是事件结点的个数N（N<26）和子任务数M。
从第二行开始M行，每行是子任务的开始事件和结束事件以及完成该子任务所需天数。
输出
完成该工程所需的最少天数。

样例输入

4 3
A B 6
B Z 2
A Z 5

样例输出

8

代码

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
#include <bits/stdc++.h>
using namespace std;
int res = 0;
int maxv = 0;
void dfs(vector<vector<pair<int, int>>> &graph,int cur){
    for(auto& child:graph[cur]){
        res += child.second;
        maxv = max(maxv, res);
        dfs(graph, child.first);
        res -= child.second;
    }
}
int main()
{
    int n,m;cin>>n>>m;
    vector<vector<pair<int, int>>> graph(26);
    for (int i = 0; i < m; i++)
    {
        char x, y;
        int days;
        cin >> x >> y >> days;
        int xx = int(x) - 65;
        int yy = int(y) - 65;
        graph[yy].push_back({xx, days});
    }
    dfs(graph, 25);
    cout << maxv;
    return 0;
}

T4

题目描述

求n个整数中第二小的数。
相同的整数看成一个数。比如，有5个数分别是1,1,3,4,5，那么第二小的数就是3。
输入
输入包含多组测试数据。输入的第一行是一个整数C，表示有C组测试数据；
每组测试数据的第一行是一个整数n，表示本组测试数据有n个整数（2<=n<=10），接着一行是n个整数（每个数均小于100）。
输出
为每组测试数据输出第二小的整数，如果不存在第二小的整数则输出“NO”，每组输出占一行。

样例输入

3
2
1 2
5
1 1 3 4 5
3
1 1 1

样例输出

2
3
NO

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--){
        int x;
        cin >> x;
        set<int> st;
        vector<int> v;
        while(x--){
            int m;
            cin>>m;
            if(st.count(m)==0){
                v.push_back(m);
                st.insert(m);
            }
            else{
                continue;
            }
        }
        if(v.size()<2){
            cout << "NO" << endl;
        }
        else{
            sort(v.begin(),v.end());
            cout << v[1] << endl;
        }
    }
    return 0;
}

T5

题目描述

对于给定的正整数序列，按照每个数的十进制形式各个位上的数之和从大到小排序，各个位上的数和相同的按照本身大小排序，大的在前，小的在后。
输入
第一行 1 个整数 n,表示序列的大小。( 0 < n ≤ 1000) 第二行 n 个正整数，表示序列的每个数，每个数不大于 100000000。
输出
输出按照题目要求排序后的序列。

样例输入

6
17 26 9 13 88 22

样例输出

88 9 26 17 22 13

代码

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
#include <bits/stdc++.h>
using namespace std;
struct node{
    int num, ge;
    node(int num){
        this->num = num;
        this->ge = 0;
        while(num>0){
            this->ge += num % 10;
            num /= 10;
        }
    }
    bool operator<(const node& other){
        if(ge==other.ge){
            return num > other.num;
        }
        else{
            return ge > other.ge;
        }
    }
};
int main()
{
    int n;
    cin>>n;
    vector<node> v;
    while(n--){
        int x;
        cin >> x;
        v.push_back(node(x));
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size();i++){
        cout << v[i].num << " ";
    }
    return 0;
}

T6

题目描述

给你10个正整数，其中5个奇数、5个偶数，先递减排奇数，然后再递增排偶数。请编程实现。
输入
一行10个正整数（int类型范围）。
输出
先递减排5个奇数，然后再递增排5个偶数，各个数之间有一个空格间隔。

样例输入

1 2 3 4 5 6 7 8 10 9

样例输出

9 7 5 3 1 2 4 6 8 10

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> ji;
    vector<int> ou;
    for (int i = 0; i < 10;i++){
        int x;
        cin >> x;
        if(x%2==0){
            ou.push_back(x);
        }
        else{
            ji.push_back(x);
        }
    }
    sort(ji.begin(), ji.end(), greater<int>());
    sort(ou.begin(), ou.end());
    for (int i = 0; i < 10;i++){
        if(i<5){
            cout << ji[i]<<" ";
        }
        else{
            cout << ou[i - 5]<<" ";
        }
    }
    return 0;
}

数据结构课程作业

第一次作业

T1

题目描述

期末考试结束后，数学老师给出了班里同学们的数学成绩，为了快速查成绩，请编程帮助查成绩。
输入
第一行为N（N<1000）表示班级人数，第一行后N行，每行两个部分，一个是学号（符号最多8个），一个是成绩（整数）。
最后一行是要查找成绩同学的学号。
输出
输出要查找同学的学号。

样例输入

2
001 90
002 95
002

样例输出

95

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    unordered_map<string, int> mp;
    for (int i = 0; i < n;i++){
        string num;
        cin >> num;
        int sc;
        cin >> sc;
        mp[num]=sc;
    }
    string num;
    cin >> num;
    cout << mp[num];
    return 0;
}

T2

题目描述

已有一个整数序列，现在要在不同的位置插入一些整数，请输出插入数据后的序列。
输入
第一行是N（N<1000）表示原序列中元素的个数，紧接着第二行是N个整数，第三行是要插入的元素个数M（M<1000）,第四开始M行，每行是一对数据k（要插入到原序列的位置，从1开始计数）和x。
输出
输出插入元素后的整数序列。

样例输入

5
1 2 3 4 5
2
1 11
3 33

样例输出

11 1 2 33 3 4 5

代码

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
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int num;
    node *next;
    node(int num) : num(num), next(nullptr) {}
};
int main()
{
    int n;
    cin >> n;
    node *dummy = new node(-1);
    node *p = dummy;
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        p->next = new node(num);
        p = p->next;
    }
    cin >> n;
    vector<pair<int, int>> inserts;
    for (int i = 0; i < n; i++)
    {
        int pos, num;
        cin >> pos >> num;
        inserts.emplace_back(pos, num);
    }
    for (int i = inserts.size() - 1; i >= 0; i--)
    {
        int pos = inserts[i].first;
        int val = inserts[i].second;
        p = dummy;
        node *pre = nullptr;
        while (pos > 1 && p->next)
        {
            p = p->next;
            pos--;
        }
        node *newNode = new node(val);
        newNode->next = p->next;
        p->next = newNode;
    }
    p = dummy->next;
    while (p)
    {
        cout << p->num << " ";
        p = p->next;
    }
    p = dummy;
    while (p)
    {
        node *tmp = p;
        p = p->next;
        delete tmp;
    }
    return 0;
}

T3

题目描述

有两个按元素值递增有序的整数顺序表A和B，设计一个算法将顺序表A和B的全部元素合并到一个递增有序顺序表C中，并依次输出C中的元素。
输入
占两行，依次是A和B的序列（元素个数都小于100）。
输出
依次输出C中的元素。

样例输入

1 2 3 4 5
1 2 3 4 6

样例输出

1 1 2 2 3 3 4 4 5 6

代码

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
#include <bits/stdc++.h>
using namespace std;
vector<int> f(string& line) {
    vector<int> result;
    string num = "";
    for (char ch : line) {
        if (ch == ' ') {
            if (!num.empty()) {
                result.push_back(atoi(num.c_str()));
                num = "";
            }
        } else {
            num += ch;
        }
    }
    if (!num.empty()) {
        result.push_back(atoi(num.c_str()));
    }
    return result;
}
int main() {
    string lineA, lineB;
    getline(cin, lineA);
    getline(cin, lineB);
    vector<int> A = f(lineA);
    vector<int> B = f(lineB);
    vector<int> C;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        if (A[i] <= B[j]) {
            C.push_back(A[i++]);
        } else {
            C.push_back(B[j++]);
        }
    }
    while (i < A.size()) C.push_back(A[i++]);
    while (j < B.size()) C.push_back(B[j++]);
    for (int x : C) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

T4

题目描述

有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法查找L中最大值结点的个数。
输入
单链表L中的元素，个数不定。
输出
查找L中最大值结点的个数。

样例输入

1 2 3 4 5 5 20 20 1 2 3 4 5

样例输出

2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x, maxv = INT_MIN, maxcnt = 0;
    while(cin>>x){
        if(x>maxv){
            maxv = x;
            maxcnt = 1;
        }
        else if(x==maxv)
            maxcnt++;
    }
    cout << maxcnt;
    return 0;
}

T5

题目描述

编写一个程序求解约瑟夫（Joseph）问题。有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，数到第m（0<m<n）个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，…，如此反复直到所有的小孩全部出列为止，求整个出列序列。
输入
占一行为n和m（n<100）。
输出
整个出列序列。

样例输入

6 5

样例输出

5 4 6 2 3 1

代码

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
#include<bits/stdc++.h>
using namespace std;
struct node{
    int id;
    node* next;
    node(int n):id(n),next(nullptr){}
};
void josephus(int n,int m){
    node* tail= new node(1);
    node* head=tail;
    for(int i=2;i<=n;i++){
        tail->next= new node(i);
        tail=tail->next;
    }
    tail->next=head;
    node* pre=tail;
    node* p=pre->next;
    while(p!=pre){
        for(int i=1;i<m;i++){
            pre=p;
            p=p->next;
        }
        cout<<p->id<<" ";
        pre->next=p->next;
        delete p;
        p=pre->next;
    }
    cout<<p->id;
}
int main()
{
    int n,m;
    cin>>n>>m;
    josephus(n,m);
    return 0;
}

T6

题目描述

设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对（假设表达式中可能含有圆括号()、中括号[]和大括号{}）。
输入
占一行为含有三种括号的表达式（最长100个符号）。
输出
匹配时输出YES，小括号不匹配输出NO1，中括号不匹配时输出NO2，大括号不匹配时输出NO3。

样例输入

{([a])}

样例输出

YES

代码

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
#include <bits/stdc++.h>
using namespace std;
int f(const string &str)
{
    stack<char> st;
    for (char ch : str)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            st.push(ch);
        }
        else if (ch == ')')
        {
            if (st.empty() || st.top() != '(')
                if(st.top()=='[')
                    return 2;
                else if(st.top()=='{')
                    return 3;
            st.pop();
        }
        else if (ch == ']')
        {
            if (st.empty() || st.top() != '[')
                if (st.top() == '(')
                    return 1;
                else if (st.top() == '{')
                    return 3;
            st.pop();
        }
        else if (ch == '}')
        {
            if (st.empty() || st.top() != '{')
                if (st.top() == '[')
                    return 2;
                else if (st.top() == '(')
                    return 1;
            st.pop();
        }
    }
    if (!st.empty())
    {
        char ch = st.top();
        if (ch == '(')
            return 1;
        if (ch == '[')
            return 2;
        if (ch == '{')
            return 3;
    }
    return 0; 
}
int main()
{
    string str;
    cin >> str;
    int result = f(str);
    if (result == 0)
        cout << "YES";
    else if (result == 1)
        cout << "NO1";
    else if (result == 2)
        cout << "NO2";
    else if (result == 3)
        cout << "NO3";
    return 0;
}

T7

题目描述

给出一个中缀表达式，输出该表达式的后缀表达式。
输入
占一行，一个中缀表达式（运算符只有±*/，最多1000个字符），输出后缀表达式。
输出
输出后缀表达式。

样例输入

(56-20)/(4+2)

样例输出

56 20 - 4 2 + /

代码

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
77
78
#include<bits/stdc++.h>
using namespace std;
vector<string> trans(string exp)
{
    stack<char> st;
    int i = 0;
    char ch, e;
    vector<string> postexp;
    while (i < exp.size())
    {
        ch = exp[i];
        if (ch == '(')
            st.push(ch);
        else if (ch == ')')
        {
            while (!st.empty() && st.top() != '(')
            {
                e = st.top();
                st.pop();
                postexp.push_back(string(1, e));
            }
            st.pop();
        }
        else if (ch == '+' || ch == '-')
        {
            while (!st.empty() && st.top() != '(')
            {
                e = st.top();
                st.pop();
                postexp.push_back(string(1, e));
            }
            st.push(ch);
        }
        else if (ch == '*' || ch == '/')
        {
            while (!st.empty() && st.top() != '(' && (st.top() == '*' || st.top() == '/'))
            {
                e = st.top();
                st.pop();
                postexp.push_back(string(1, e));
            }
            st.push(ch);
        }
        else
        {
            string num = "";
            while (ch >= '0' && ch <= '9')
            {
                num += ch;
                i++;
                if (i < exp.size())
                    ch = exp[i];
                else
                    break;
            }
            i--;
            postexp.push_back(num);
        }
        i++;
    }
    while (!st.empty())
    {
        e = st.top();
        st.pop();
        postexp.push_back(string(1, e));
    }
    return postexp;
}
int main()
{
    string exp;
    cin>>exp;
    vector<string> res = trans(exp);
    for(auto& ch:res){
        cout << ch << " ";
    }
    return 0;
}

T8

题目描述

小C很喜欢倒着写单词，现在给你一行小C写的文本，你能把每个单词都反转并输出它们吗？
输入
输入包含多组测试样例。第一行为一个整数T，代表测试样例的数量，后面跟着T个测试样例。
每个测试样例占一行，包含多个单词。一行最多有1000个字符。
输出
对于每一个测试样例，你应该输出转换后的文本。

样例输入

3
olleh !dlrow
I ekil .bulcmca
I evol .mca

样例输出

hello world!
I like acmclub.
I love acm.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    cin.ignore();
    while (T--) {
        string line;
        getline(cin, line);
        string word = "";
        for (size_t i = 0; i <= line.length(); ++i) {
            if (i == line.length() || line[i] == ' ') {
                reverse(word.begin(), word.end());
                cout << word;
                if (i != line.length()) cout << " ";
                word = "";
            } else {
                word += line[i];
            }
        }
        cout << endl;
    }
    return 0;
}

第二次作业

T1

题目描述

现在给你一个字符串S，请你计算S中有多少连续子串是回文串。
输入
输入包含多组测试数据。每组输入是一个非空字符串，长度不超过5000。
输出
对于每组输入，输出回文子串的个数。

样例输入

aba
aa

样例输出

4
3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int countPalindromes(const string& s) {
    int n = s.size();
    int res = 0;
    for (int center = 0; center < 2 * n - 1; ++center) {
        int left = center / 2;
        int right = left + (center % 2);
        while (left >= 0 && right < n && s[left] == s[right]) {
            res++;
            left--;
            right++;
        }
    }
    return res;
}
int main() {
    string str;
    while (cin >> str) {
        cout << countPalindromes(str) << endl;
    }
    return 0;
}

T2

题目描述

现请你构建一个N*N的矩阵，第i行j列的元素为i与j的乘积。（i，j均从1开始）
输入
输入的第一行为一个正整数C，表示测试样例的个数。
然后是C行测试样例，每行为一个整数N（1<=N<=9），表示矩阵的行列数。
输出
对于每一组输入，输出构建的矩阵。

样例输入

2
1
4

样例输出

1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, vector<char>> mp;

void f(int x){
    vector<vector<int>> res(x, vector<int>(x, 0));
    for (int i = 0; i < x;i++){
        for (int j = 0; j < x;j++){
            cout << (i+1) * (j+1) << " ";
        }
        cout << endl;
    }
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n;i++){
        int x;
        cin >> x;
        f(x);
    }
        return 0;
}

T3

题目描述

小宇正在读小学，今天老师布置了几道数学题目。小宇平时上课经常不专心，这些他可发愁了，怎么办呢？看看你能不能帮帮他。
题目是给你一组有规律序列的前面5个整数，请你给出它后面跟着的5个整数，如：1,2,3,4,5这是个等差数列，后面应该是6,7,8,9,10，就这么简单。而且现在小宇已经知道这串序列要么是等差数列，要么是等比数列或者是斐波那契数列。
输入
输入包含多组测试数据。每组输入5个整数，每个数字之间隔一个空格，当5个数字都为0时输入结束。
输出
对于每组输入，输出这串数列的后面5个数字，每个数字之间隔一个空格。

样例输入

1 2 3 4 5
1 2 4 8 16
1 2 3 5 8
0 0 0 0 0

样例输出

6 7 8 9 10
32 64 128 256 512
13 21 34 55 89

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c, d, e;
    while (cin>>a>>b>>c>>d>>e)
    {
        if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0)
        {
            break;
        }
        if ((b - a) == (c - b) && (d - c) == (c - b) && (d - c) == (e - d))
        {
            int t = b - a;
            for (int i = 1; i <= 5; i++)
            {
                cout << e + i * t << " ";
            }
            cout << endl;
        }
        if ((b / a) == (c / b) && (c / b) == (d / c) && (d / c) == (e / d) && (b / a) != 1)
        {
            int t = b / a;
            for (int i = 1; i <= 5; i++)
            {
                cout << e * (int)pow(t, i) << " ";
            }
            cout<<endl;
        }
        if (a + b == c && b + c == d && c + d == e)
        {
            int t1 = d, t2 = e, s = 0;
            for (int i = 6; i < 11; i++)
            {
                s = t1 + t2;
                t1 = t2;
                t2 = s;
                cout<<s<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

T4

题目描述

小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。
输入
输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。
输出
对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
void f(string pre, string in)
{
    if (!pre.size())
        return;
    char root = pre[0];
    int pos = in.find(root);
    f(pre.substr(1, pos), in.substr(0, pos));
    f(pre.substr(pos + 1), in.substr(pos + 1));
    cout << pre[0];
}
int main()
{
    string pre, in;
    while (cin >> pre >> in)
    {
        f(pre, in);
        cout << endl;
    }
    return 0;
}

T5

题目描述

给你一颗二叉树的中序和后序遍历序列，请编程输出该二叉树左子树或右子树的后序遍历序列。
输入
占三行，第一行表示二叉树的中序遍历序列，第二行表示后序遍历序列。用大写字母标识结点，二叉树的结点最多26个。
第三行是单个字母，L表示要求输出该二叉树的左子树的后序遍历序列，R表示要求输出该二叉树的右子树的后序遍历序列。
输出
按要求输出该二叉树左子树或右子树的后序遍历序列。

样例输入

BDCEAFHG
DECBHGFA
R

样例输出

HGF

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string in, post;
    cin>>in>>post;
    char x;
    cin >> x;
    int pos = in.find(post[post.size() - 1]);
    if(x=='L'){
        cout << post.substr(0, pos);
    }
    else{
        cout << post.substr(pos, post.size() - pos-1);
    }
    return 0;
}

T6

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
S-###
-----
##—
E#—
—##

样例输出

9

代码

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
#include <bits/stdc++.h>
using namespace std;

int bfs(vector<vector<char>> &mg, int sx, int sy)
{
    int n = mg.size(), m = mg[0].size();
    queue<pair<int, int>> q;
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    q.push({sx, sy});
    int steps = 0;
    mg[sx][sy] = '#';
    while (!q.empty())
    {
        int sz = q.size();
        for (int i = 0; i < sz; ++i)
        {
            auto [x, y] = q.front();
            q.pop();

            for (auto &d : dir)
            {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;

                if (mg[nx][ny] == 'E')
                    return steps + 1;

                if (mg[nx][ny] == '-')
                {
                    mg[nx][ny] = '#'; 
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }

    return -1; 
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m, sx, sy;
        cin >> n >> m;
        vector<vector<char>> mg(n, vector<char>(m));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> mg[i][j];
                if (mg[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
            }
        }
        cout << bfs(mg, sx, sy) << endl;
    }
    return 0;
}

第三次作业

T1

题目描述

已知一个无向图G的顶点和边，顶点从0依次编号，现在需要深度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的深度优先搜索序列。
输入
第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。
输出
该图从0号顶点开始的深度优先搜索序列。

样例输入

5 5
0 1
2 0
1 3
1 4
4 2

样例输出

0 1 3 4 2

代码

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
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &graph, vector<int> &visited,int cur){
    cout << cur << " ";
    visited[cur] = 1;
    for (int i = 0; i < graph[cur].size();i++){
        if(visited[graph[cur][i]]==0){
            dfs(graph, visited, graph[cur][i]);
        }
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> graph(m);
    vector<int> visited(m,0);
    for (int i = 0; i < n;i++){
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(graph,visited,0);
    return 0;
}

T2

题目描述

现在给你n个结点的完全二叉树数组存储序列，请编程调整为最小堆，并输出相应最小堆的存储序列。
输入
第一行是n，第二行是n个结点的完全二叉树数组存储序列。
输出
输出相应最小堆的存储序列。

样例输入

8
53 17 78 23 45 65 87 9

样例输出

9 17 65 23 45 78 87 53

代码

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
#include <bits/stdc++.h>
using namespace std;
void heapify(vector<int> &v, int n, int cur){
    int smallest = cur;      
    int left = 2 * cur + 1;  
    int right = 2 * cur + 2; 
    if (left < n && v[left] < v[smallest])
        smallest = left;
    if (right < n && v[right] < v[smallest])
        smallest = right;
    if (smallest != cur)
    {
        swap(v[cur], v[smallest]);
        heapify(v, n, smallest);
    }
}
void buildMinHeap(vector<int> &v, int n){
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(v, n, i);
}
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++){
        cin >> v[i];
    }
    buildMinHeap(v, n);
    for (int i = 0; i < n; i++){
        cout << v[i]<<" ";
    }
    return 0;
}

T3

题目描述

给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。
输入
第一行是N，表示序列中数的个数，序列最长1000，第二行是一个有序序列，第三行是要找的数x。
输出
如果找到x，输出折半比较的次数，否则输出NO。

样例输入

11
5 13 19 21 37 56 64 75 80 88 92
19

样例输出

2

代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n;i++){
        cin >> v[i];
    }
    int x;
    cin >> x;
    int left = 0, right = n - 1, mid = 0;
    int cnt = 0;
    while(left<right){
        cnt++;
        mid=(left+right+1)/2;
        if(v[mid]>x)
            right = mid - 1;
        else if(v[mid]<x)
            left = mid + 1;
        else{
            cout << cnt;
            break;
        }
    }
    if(v[mid]!=x){
        cout << "NO";
    }
    return 0;
}

T4

题目描述

给你N个自然数，编程输出排序后的这N个数。
输入
第一行是整数的个数N（N<=100）。第二行是用空格隔开的N个数。
输出
排序输出N个数，每个数间用一个空格间隔。

样例输入

5
9 6 8 7 5

样例输出

5 6 7 8 9

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n;i++){
        cout << v[i] << " ";
    }
        return 0;
}

T5

题目描述

班级里有N个同学，老师希望你编个程序，把每个同学的学号、姓名、座位号保存下来，然后每次要查同学信息时，直接输入相应同学的学号，即可输出该同学的姓名和座位号。
输入
第一行为整数N（N<100）,表示班里同学的人数。接下来N行，每行分别是每个同学的学号、姓名和座位号，最后一行是要查询的同学的学号。
输出
输出查询同学的姓名和座位号。

样例输入

3
1 zhang 11
2 wang 22
3 li 33
2

样例输出

wang 22

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, string> mp;
    for (int i = 0; i < n;i++){
        int num;
        string name,pos;
        cin >> num >> name>>pos;
        mp[num] = name+" "+pos;
    }
    int x;
    cin>>x;
    cout<<mp[x];
    return 0;
}