目录
A: 子串个数
本题未考虑重复的情况，直接使用公式既可
考虑重复的情况：不同子串个数 - 洛谷
#include <bits/stdc++.h>
using namespace std;
int cs(string s) {
int n = s.length();
return n * (n + 1) / 2+1;
}
string s;
int main() {
while (getline(cin,s)){
cout<<cs(s)<<'\n';
}
return 0;
}B.模式串
应该是想考察KMP的，但由于样例很水，导致暴力就能拿满。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
string tar,s;
int main(){
cin>>s>>tar;
for(int i=0;i<=s.length()-tar.length();i++){
for(int j=0;j<tar.length();j++){
if(s[i+j]!=tar[j]) break;
if(j==tar.length()-1)
{
cout<<i+1;
return 0;
}
}
}
cout<<0;
}
C.主对角线上的数据和
#include<bits/stdc++.h>
using namespace std;
long long sum = 0;
int main(){
int n;cin>>n;
int temp;
cin>>temp;
sum+=temp;
for(int i=1;i<n;i++){
for(int i=1;i<=n;i++){
cin>>temp;
}
cin>>temp;
sum+=temp;
}
cout<<sum;
}
D.顺时针排螺旋阵
模拟题，看成回型阵一层一层模拟即可
回是口中口
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int a[MAXN][MAXN];
int main(){
int n,i=0,j,now=0;
cin>>n;
int r=1,cnt=n; //r为层
while(r<=cnt){ //模拟，横五竖四
for( j=r ;j<=cnt;j++) a[r][j]=++now; //up
for(i=r+1 ;i<=cnt;i++) a[i][cnt]=++now; //right
for(j=cnt-1;j>=r ;j--) a[cnt][j]=++now; //down
for(i=cnt-1;i>r ;i--) a[i][r]=++now; //left
r++;cnt--;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
cout<<a[i][j]<<' ';
printf("\n");
}
}E: 汉诺塔游戏中的移动
假设现在要把n个盘子移动到C上，那么我们需要做的就是将最大的那个盘子移动到C上，再将其余的盘子移动到C上。解决n-1个盘子的问题时亦是如此。而解决第n-1个盘子的问题时，刚刚所说的第 n 个盘子完全可以视而不见，故对结果没有影响。由此可见，不断递归下去，最终会来到1个盘子的问题，这样即可解决问题。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int cnt=0;
void solve(int n,char start,char mid,char tar){
if(n==1){
cnt++;
printf("%d %d %c->%c\n",cnt,n,start,tar);
return;
}
solve(n-1,start,tar,mid);
cnt++;
printf("%d %d %c->%c\n",cnt,n,start,tar);
solve(n-1,mid,start,tar);
}
int main(){
int n;cin>>n;
solve(n,'A','B','C');
}
F.树的先根遍历
样例具有误导性，事实上这个题并不是二叉树。既然不是二叉树，那么使用结构体就略嫌麻烦。不如使用数组，用 t [i][j] 代表 i 的孩子分别是谁 cnt[i] 代表 i 有几个孩子
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
int t[MAXN][30];
int cnt[MAXN];
void pre_order(int x){ //前序遍历
cout<<(char)(x+'A')<<' ';
for(int i=1;i<=cnt[x];i++){
pre_order(t[x][i]);
}
}
string s;
int main(){
int root=0; //用来确定谁是根
int now = 0;
char s1,s2;
while(cin>>s1>>s2){
if(now==0){
root=s1-'A';
}
now++; //将根初始化
t[s1-'A'][++cnt[s1-'A']] = s2-'A'; //处理输入的数据
if(s2-'A'==root) //更新根
root = s1-'A';
}
pre_order(root);
}
G.树的后根遍历
在上一题的基础上略加改动即可。先遍历孩子，再输出本身
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
int t[MAXN][30];
int cnt[MAXN];
void aft_order(int x){
for(int i=1;i<=cnt[x];i++){
aft_order(t[x][i]);
}
cout<<(char)(x+'A')<<' ';
}
string s;
int main(){
int root=0;
int now = 0;
char s1,s2;
while(cin>>s1>>s2){
if(now==0){
root=s1-'A';
}
now++;
t[s1-'A'][++cnt[s1-'A']] = s2-'A';
if(s2-'A'==root)
root = s1-'A';
}
aft_order(root);
}