如题,贴出AC代码,仅供参考不提供讲解
代码主打的就是一个叛逆
问题 A: 子串个数
内存限制:128 MB
时间限制:1.000 S
题目描述
给你若干个字符串,请编程输出每个字符串的子串个数。
输入
若干个字符串,每个字符串占一行,字符串中不含空格,长度最大为1000。
输出
对应每一行的字符串,输出该字符串子串的个数。
样例输入
样例输出
代码
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 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 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 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 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 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 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了,那就这样吧;同时因为题目特殊性,用矩阵的方式存储了树。