阅读量:1
目录
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); } 