0%

中国矿业大学数据结构实践2

如题,贴出AC代码,仅供参考不提供讲解

代码主打的就是一个叛逆

问题 A: 子串个数

内存限制:128 MB

时间限制:1.000 S

题目描述

给你若干个字符串,请编程输出每个字符串的子串个数。

输入

若干个字符串,每个字符串占一行,字符串中不含空格,长度最大为1000。

输出

对应每一行的字符串,输出该字符串子串的个数。

样例输入

1
2
3
abc
apple
software

样例输出

1
2
3
7
16
37

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

string s;
while(cin>>s){
int len=s.size();
cout<<len*(len+1)/2+1<<endl;
}

return 0;
}

别忘了空串是任何串的子串

问题 B: 模式串

内存限制:128 MB

时间限制:1.000 S

题目描述

给你一个目标串,请查找在给目标串中是否存在模式串,存在就输出第一个模式串在目标串中出现的位置。

输入

占两行,第一行是目标串(长度小于1000),第二行为模式串(长度小于100)。

输出

输出模式串在目标串中出现的位置,即模式串匹配到目标串时第一个字符在目标串的位置(注意从1开始描述字符开始位置),不能匹配时输出0.

样例输入

1
2
appleorange
orange

样例输出

1
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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
class KMP {
private:
string pat;
int *next;
public:
KMP(string _pat) {
pat = _pat;
next = new int[pat.length()];
next[0] = 0;
for (int i = 1, j = 0; i < pat.length(); i++) {
while (j > 0 && pat[i] != pat[j])
j = next[j - 1];
if (pat[i] == pat[j])
j++;
next[i] = j;
}
}
int find(string text) {
for (int i = 0, j = 0; i < text.length(); i++) {
while (j > 0 && text[i] != pat[j])
j = next[j - 1];
if (text[i] == pat[j])
j++;
if (j == pat.length())
return i - j + 1;
}
return -1;
}
~KMP() { delete[] next; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

string pattern,text;
cin>>text>>pattern;
KMP kmp(pattern);
cout<<kmp.find(text)+1;

return 0;
}

谁家大好人数数从1开始数啊?啊??

直接套的KMP模板,没啥好说的。

问题 C: 主对角线上的数据和

内存限制:128 MB

时间限制:1.000 S

题目描述

在一个N行N列的方阵(或称N阶方阵)中,从左上角到右下角这一斜线上有N个数据元素,这个斜线称为方阵的主对角线。给你一个方阵,请求方阵主对角线上数据的和。

输入

第一行是N(N<100),表示下边是一个N阶方阵。接下来N行N列用空格间隔放置正整数(int型)。

输出

N阶方阵主对角线上数据的和。

样例输入

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

样例输出

1
6

代码

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>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T,temp,ans=0;
cin>>T;
for(int i=0;i<T;i++)
for(int j=0;j<T;j++){
cin>>temp;
if(i==j)
ans+=temp;
}
cout<<ans;
return 0;
}

问题 D: 顺时针排螺旋阵

内存限制:128 MB

时间限制:1.000 S

题目描述

给你一个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)。

输出

输出符合题意的螺旋阵。

样例输入

1
5

样例输出

1
2
3
4
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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;

int matrix[110][110];
void init(int N){
int ha=N/2;
int cnt=1;
for(int i=0;i<ha;i++){
int x=i,y=i;
int step=N-i*2-1;
for(int j=0;j<step;j++)matrix[x++][y]=cnt++;
for(int j=0;j<step;j++)matrix[x][y++]=cnt++;
for(int j=0;j<step;j++)matrix[x--][y]=cnt++;
for(int j=0;j<step;j++)matrix[x][y--]=cnt++;
}
if(N%2==1)
matrix[N/2][N/2]=N*N;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin>>N;
mm(matrix);
init(N);

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cout<<matrix[j][i]<<(j==N-1?'\n':' ');

return 0;
}

这题的代码还可以简单的缩短一下,这样重复性太高了,不过没啥意思

问题 E: 汉诺塔游戏中的移动

内存限制:128 MB

时间限制:1.000 S

题目描述

有三根标为A,B,C的柱子,A柱子上从上到下按金字塔状依次叠放着n个半径从1厘米到n厘米的的圆盘,要把A上的所有盘子移动到柱子C上,中间可以临时放在B上,但每次移动每一根柱子上都不能出现大盘子在小盘子上方的情况,要求用最少的移动次数完成,请编程模拟每次移动。

输入

占一行,为整数n(n<64),表示盘子数。

输出

把A上的所有盘子移动到柱子C上,每次只能移动一个盘子,输出移动每一次过程。每次移动占一行,第一个数表示第几步移动,第二个数是移动的盘子的半径,然后是从哪个柱子移动到哪个柱子。

样例输入

1
2

样例输出

1
2
3
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
23
24
25
26
27
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int step=0;
void move(int n,char A,char B,char C){
if(n==1){
cout<<++step<<' '<<1<<' '<<A<<"->"<<C<<endl;
}else{
move(n-1,A,C,B);
cout<<++step<<' '<<n<<' '<<A<<"->"<<C<<endl;
move(n-1,B,A,C);
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N;
cin>>N;
move(N,'A','B','C');

return 0;
}

这题的关键就是要明白汉诺塔的递归解法,明白递归解法中各步骤的含义。

问题 F: 树的先根遍历

内存限制:128 MB

时间限制:1.000 S

题目描述

已知一颗树的节点间关系,请编程实现该树的先根遍历。

输入

若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。

输出

该树的先根遍历序列,序列中每个字母用空格隔开。

样例输入

1
2
3
4
B E
B F
A B
A C

样例输出

1
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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int tree[28][28];
int func(int x){
cout<<char(x+'A')<<" ";
if(tree[x][0]==0)
return 0;
for(int i=1;i<=tree[x][0];i++)
func(tree[x][i]);
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

mm(tree);
char A,B;
while(cin>>A){
cin>>B;
tree[A-'A'][++tree[A-'A'][0]]=B-'A';
}
func(0);
return 0;
}

问题 G: 树的后根遍历

内存限制:128 MB

时间限制:1.000 S**

题目描述

已知一颗树的节点间关系,请编程实现该树的后根遍历序列。

输入

若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。

输出

该树的后根遍历序列,序列中每个字母用空格隔开。

样例输入

1
2
3
4
B E
B F
A B
A C

样例输出

1
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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
int tree[28][28];
int func(int x){
if(tree[x][0]==0){
cout<<char(x+'A')<<" ";
return 0;
}
for(int i=1;i<=tree[x][0];i++)
func(tree[x][i]);
cout<<char(x+'A')<<" ";
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

mm(tree);
char A,B;
while(cin>>A){
cin>>B;
tree[A-'A'][++tree[A-'A'][0]]=B-'A';
}
func(0);
return 0;
}

F、G题没有明确A作为根节点,不过经过观察确定A应该是根节点,尝试提交AC了,那就这样吧;同时因为题目特殊性,用矩阵的方式存储了树。

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道