C/C++编程七级 题库
有多少种二叉树(2023.3)
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <iostream>
using namespace std;
long long cat(int n) {
if (n == 0)
return 1;
long long sum(0);
for (int i = 0; i < n; i++)
sum += cat(i) * cat(n - 1 - i);
return sum;
}
int main() {
int n;
cin >> n;
cout << cat(n);
return 0;
}Sequence
给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和
时间限制:3000
内存限制:65536
输入
输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例,输出一行用空格隔开的数,表示最小的n个和
样例输入
1 2 3 1 2 3 2 2 3
样例输出
3 3 4
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
int T;
cin >> T;
int m, n;
while (T--) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n); // 用a做总的和数组
for (int i = 1; i < m; i++) // 轮接下来的序列
{
for (int j = 0; j < n; j++) {
scanf("%d", &b[j]);
que.push(a[0] + b[j]);
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j] + b[k] < que.top()) {
que.pop();
que.push(a[j] +
b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
}
}
}
for (int i = 0; i < n; i++) {
a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
que.pop(); // 队列已经被清空了,轮下一次
}
}
for (int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d\n", a[n - 1]);
}
return 0;
}走迷宫
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
时间限制:1000
内存限制:65536
输入
第一行是两个整数,R和C,代表迷宫的长和宽。(1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用'.'表示,有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。
输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
样例输入
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出
9
#include <iostream>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int idata = 1000 + 5;
char maps[idata][idata];
int judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int Count[idata][idata];
int soux, souy;
int exitx, exity;
bool flag;
int m, n;
int main() {
int i, j;
int tail = 1, head = 0;
cin >> m >> n;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
cin >> maps[i][j];
if (maps[i][j] == '#')
judge[i][j] = 1;
}
}
judge[1][1] = 1;
Count[1][1] = 1;
x[1] = 1, y[1] = 1;
while (head < tail) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !judge[nx][ny]) {
judge[nx][ny] = 1;
tail++;
x[tail] = nx;
y[tail] = ny;
Count[x[tail]][y[tail]] = Count[x[head]][y[head]] + 1;
if (nx == m && ny == n) {
flag = 1;
break;
}
}
}
if (flag)
break;
}
cout << Count[m][n] << endl;
return 0;
}重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
#include <stdio.h>
#include <string.h>
void bulid(int n, char s1[],
char s2[]) // n是树的节点数,s1是记录先序遍历,s2中序遍历
{
if (n <= 0)
return; // 没有节点了,找到边界return
int p = strchr(s2, s1[0]) - s2;
// strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址
// 所以p是 s1[0]第一次出现在s2中的位置
bulid(p, s1 + 1, s2);
// 数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...
// 以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点
// s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)
bulid(n - p - 1, s1 + p + 1, s2 + p + 1);
// 数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)
// 以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点
// s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点
// )
printf("%c", s1[0]); // 输出
}
int main() {
char s1[10007], s2[10007]; // s1是树的前序遍历,s2是树的中序遍历
while (scanf("%s %s", s1, s2) != EOF) // 多组数据
{
bulid(strlen(s1), s1, s2);
printf("\n"); // 记得输出\n
}
return 0;
}
/*
先序遍历第一个节点一定是根节点。
中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。
后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。
*/快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
swap(h[u / 2], h[u]);
u /= 2;
}
}
void down(int u) {
int t = u;
if (u * 2 <= size_ && h[u * 2] < h[u])
t = u * 2;
if (u * 2 + 1 <= size_ && h[u * 2 + 1] < h[u])
t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}
int main() {
char t[10];
string s;
int n;
while (scanf("%s", t) != EOF) {
s = string(t);
if (s == "pop") {
if (size_ == 0)
continue;
h[1] = h[size_];
size_--;
down(1);
} else if (s == "min") {
if (size_ == 0)
continue;
cout << h[1] << endl;
} else if (s == "push") {
cin >> n;
size_++;
h[size_] = n;
up(size_);
}
}
return 0;
}表达式· 表达式树· 表达式求值
众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,
表达式 a+b*c, 可以表示为如下的表达式树:
+
/ \
a *
/ \
b c
现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制: 1000
内存限制: 65535
输入
输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。
样例输入
a+b*c 3 a 2 b 7 c 5
样例输出
abc*+ + / \ a * / \ b c 37
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>
#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number {
char ch;
int value;
};
number a[10];
// 定义二叉树类型
typedef struct BiNode {
char date;
struct BiNode *lchild, *rchild;
} BiNode;
// 定义栈类型
typedef struct SqStack {
char *base;
char *top;
int stacksize;
} SqStack;
// 初始化栈
int InitStack(SqStack &S) {
S.base = new char[MAXSIZE];
if (!S.base)
exit(ERROR);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
// 出栈
char Pop(SqStack &S) {
if (S.top == S.base)
return ERROR;
char e = *(--S.top);
return e;
}
// 入栈
int Push(SqStack &S, char e) {
if (S.top - S.base == S.stacksize)
return ERROR;
*(S.top++) = e;
return OK;
}
// 将中缀表达式转化为后缀表达式
string Change(string str) {
// str为中缀表达式,str2为后缀表达式
string str2 = "";
char ch, e; // e用于保存栈中弹出的元素
SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式
InitStack(S1);
for (int i = 0; i < str.size(); i++) {
ch = str[i];
if (ch >= 'a' && ch <= 'z') {
str2 += ch;
}
if (ch == '(')
Push(S1, ch);
if (ch == ')') {
while (*(S1.top - 1) != '(') {
e = Pop(S1);
str2 += e;
}
Pop(S1); // 左括号出栈但不入S2栈中
}
// 遇到+或-时
// 栈空/栈顶为左括号:直接入栈
// 否则一直出栈,直到栈空/栈顶为左括号,再入栈
if (ch == '+' || ch == '-') {
while (*(S1.top - 1) != '(' && S1.base != S1.top) {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
// 遇到*或/时
// 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
// 否则一直出栈,直到满足上述条件,再入栈
if (ch == '*' || ch == '/') {
while (S1.base != S1.top && *(S1.top - 1) != '(' &&
*(S1.top - 1) != '-' && *(S1.top - 1) != '+') {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
}
// 中缀表达式遍历完成,还需检查栈中是否有未输出字符
// 判断栈空,非空则直接出栈
while (S1.base != S1.top) {
e = Pop(S1);
if (e != '(')
str2 += e;
}
return str2;
}
struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树
int top = -1;
// 建立二叉树
BiNode *CreatTree(string str) {
// str为后缀表达式
BiNode *T, *T2;
SqStack S;
BiNode *e1, *e2;
int i;
InitStack(S);
for (i = 0; i < str.size() - 1; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
T = new BiNode;
T->date = str[i];
T->lchild = T->rchild = NULL;
s[++top] = T;
} else {
T = new BiNode;
T->date = str[i];
e1 = s[top--];
e2 = s[top--];
T->lchild = e2;
T->rchild = e1;
s[++top] = T;
}
}
T = new BiNode;
T->date = str[i];
T->rchild = s[top--];
T->lchild = s[top--];
s[++top] = T;
T2 = new BiNode;
T2 = s[top];
return T2;
}
int Seek(char e, int n) {
for (int i = 0; i < n; i++) {
if (a[i].ch == e)
return a[i].value;
}
}
int Count(string str, int n) {
// str为后缀表达式数组,n变量个数
int sum = 0;
stack<int> S;
int x, x1, x2;
for (int i = 0; i < n; i++) {
cin >> a[i].ch >> a[i].value;
}
for (int i = 0; i < str.size(); i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
x = Seek(str[i], n);
S.push(x);
} else {
x2 = S.top();
S.pop(); // 左操作数
x1 = S.top();
S.pop(); // 右操作数
switch (str[i]) {
case '+':
sum = x1 + x2;
break;
case '-':
sum = x1 - x2;
break;
case '*':
sum = x1 * x2;
break;
case '/':
sum = x1 / x2;
break;
}
S.push(sum);
}
}
sum = S.top();
return sum;
}
char arr[1000][1000];
// 打印二叉树
void PrintTree(int tag, BiNode *T, int x, int m, int y) {
arr[2 * tag - 1][(x + m) / 2] = T->date;
if (tag != 1) {
if (y == 1)
arr[2 * tag - 2][m] = '/';
else
arr[2 * tag - 2][x] = '\\';
}
if (T->lchild != NULL)
PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
if (T->rchild != NULL)
PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}
// 计算二叉树的深度
int Depth(BiNode *T) {
int m, n;
if (T == NULL)
return 0;
else {
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return (m + 1);
else
return (n + 1);
}
}
bool Judge(int i, int j, int n) {
for (int k = j + 1; k <= n; k++) {
if (arr[i][k] != ' ')
return 1;
}
return 0;
}
int main() {
string str1; // 中序表达式
cin >> str1;
int n; // 变量个数
cin >> n;
string str2 = Change(str1); // str2为后序表达式
BiNode *T = CreatTree(str2);
int sum = Count(str2, n);
int dp = Depth(T);
cout << str2 << endl;
memset(arr, ' ', sizeof(arr));
PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
for (int i = 1; i <= 2 * dp - 1; i++) {
for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
cout << arr[i][j];
if (arr[i][j] != ' ') {
if (Judge(i, j, pow(2.0, dp) - 1))
continue;
else
break;
}
}
cout << endl;
}
cout << sum << endl;
return 0;
}priority queue练习题
我们定义一个正整数a比正整数b优先的含义是:
*a的质因数数目(不包括自身)比b的质因数数目多;
*当两者质因数数目相等时,数值较大者优先级高。
现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。
时间限制:2500
内存限制:131072
输入
第一行: num (添加元素次数,num <= 30)
下面10*num行,每行一个正整数n(n < 10000000).
输出
每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。
样例输入
1 10 7 66 4 5 30 91 100 8 9
样例输出
66 5
#include<bits/stdc++.h>
using namespace std;
int num,d[35][15],pri[500010],tot[500010],a[500010];
int DECOMPOSITION(int x){
int cnt=0,Cnt=0;
for(int i=2;i<=x/i;i++){
for(;x%i==0;x/=i){
a[++cnt]=i;
}
}
if(x>1)a[++cnt]=x;
for(int i=1;i<=cnt;i++,tot[Cnt]++){
if(a[i]!=a[i-1])pri[++Cnt]=a[i];
}
return Cnt;
}
bool isprime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
struct node{
int tmp;
int cs;
bool operator<(const node &b)const{
if(cs!=b.cs)return cs<b.cs;
else return tmp<b.tmp;
}
};
struct node1{
int tmp;
int cs;
bool operator<(const node1 &b)const{
if(cs!=b.cs)return cs>b.cs;
else return tmp>b.tmp;
}
};
priority_queue<node>q1;
priority_queue<node1>q2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>num;
for(int i=1;i<=num;i++){
for(int j=1;j<=10;j++){
cin>>d[i][j];
int cyt=DECOMPOSITION(d[i][j]);
if(d[i][j]==1||d[i][j]==0||isprime(d[i][j]))cyt=0;
node top1 ;;
node1 top2;
top1.tmp=d[i][j];
top1.cs=cyt;
top2.tmp=d[i][j];
top2.cs=cyt;
q1.push(top1);
q2.push(top2);
}
cout<<q1.top().tmp<<" "<<q2.top().tmp<<endl;
q1.pop();q2.pop();
}
return 0;
}二叉树的深度
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+7;
struct node{
int left,right;
}t[MAXN];
int n;
void build(){
for(int i=1;i<=n;i++){
cin>>t[i].left>>t[i].right;
}
}
#define rep1(i,n) for(int i=1;i<=n;i++)
inline int dfs(int x){
if(x==-1)return 0;
return max(dfs(t[x].left),dfs(t[x].right))+1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
build();
cout<<dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string tp;
int weight,cnt=0;
int minid[100010];
minid[0]=0x3f3f3f3f;
queue<int>q;
while(cin>>tp){
if(tp=="push"){
cin>>weight;
cnt++;
q.push(weight);
minid[cnt]=min(minid[cnt-1],weight);
}else if(tp=="pop"){
if(!q.empty()){
cnt--;
q.pop();
}
}else if(tp=="min"){
if(!q.empty())cout<<minid[cnt]<<endl;
}
}
return 0;
}重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include<stdio.h>
#include<string.h>
void bulid(int n,char s1[],char s2[])//n是树的节点数,s1是记录先序遍历,s2中序遍历
{
if(n<=0) return;//没有节点了,找到边界return
int p=strchr(s2,s1[0])-s2;
// strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址
//所以p是 s1[0]第一次出现在s2中的位置
bulid(p,s1+1,s2);
//数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...
//以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点
//s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)
bulid(n-p-1,s1+p+1,s2+p+1);
//数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)
//以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点
//s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点 )
printf("%c",s1[0]);//输出
}
int main()
{
char s1[10007],s2[10007];//s1是树的前序遍历,s2是树的中序遍历
while(scanf("%s %s",s1,s2)!=EOF)//多组数据
{
bulid(strlen(s1),s1,s2);
printf("\n");//记得输出\n
}
return 0;
}
/*
先序遍历第一个节点一定是根节点。
中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。
后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。
*/快速堆猪(2023.9)
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u){
while(u/2&&h[u/2]>h[u]){
swap(h[u/2],h[u]);
u/=2;
}
}
void down(int u){
int t=u;
if(u*2<=size_&&h[u*2]<h[u]) t=u*2;
if(u*2+1<=size_&&h[u*2+1]<h[u]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);down(t);
}
}
int main()
{
char t[10];
string s;
int n;
while(scanf("%s",t)!=EOF){
s=string(t);
if(s=="pop"){
if(size_==0) continue;
h[1]=h[size_];
size_--;
down(1);
}
else if(s=="min"){
if(size_==0) continue;
cout<<h[1]<<endl;
}
else if(s=="push"){
cin>>n;
size_++;
h[size_]=n;
up(size_);
}
}
return 0;
}表达式·表达式树·表达式求值
众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式a+b*c,可以表示为如下的表达式树:
+
/ \
a *
/ \
b c
现在,给你一个中缀表达式,这个中缀表达式用变量来表示(不含数字),请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制:1000
内存限制:65535
输入
输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。
样例输入
a+b*c 3 a 2 b 7 c 5
样例输出
abc*+ + / \ a * / \ b c 37
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include<iostream>
#include<string>
#include <cstring>
#include<cmath>
#include<stack>
#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number
{
char ch;
int value;
};
number a[10];
//定义二叉树类型
typedef struct BiNode{
char date;
struct BiNode* lchild, * rchild;
}BiNode;
//定义栈类型
typedef struct SqStack {
char* base;
char* top;
int stacksize;
}SqStack;
//初始化栈
int InitStack(SqStack& S)
{
S.base = new char[MAXSIZE];
if (!S.base) exit(ERROR);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
//出栈
char Pop(SqStack& S)
{
if (S.top == S.base)
return ERROR;
char e = *(--S.top);
return e;
}
//入栈
int Push(SqStack& S, char e)
{
if (S.top - S.base==S.stacksize)
return ERROR;
*(S.top++) = e;
return OK;
}
//将中缀表达式转化为后缀表达式
string Change(string str)
{
//str为中缀表达式,str2为后缀表达式
string str2="";
char ch,e;//e用于保存栈中弹出的元素
SqStack S1;//S1用于存放操作符(为辅助栈),S用于存放后续表达式
InitStack(S1);
for (int i = 0; i < str.size(); i++)
{
ch = str[i];
if (ch >= 'a' && ch <= 'z')
{
str2 += ch;
}
if (ch == '(')
Push(S1, ch);
if (ch == ')')
{
while (*(S1.top - 1) != '(')
{
e=Pop(S1);
str2 += e;
}
Pop(S1);//左括号出栈但不入S2栈中
}
//遇到+或-时
//栈空/栈顶为左括号:直接入栈
//否则一直出栈,直到栈空/栈顶为左括号,再入栈
if (ch == '+' || ch == '-')
{
while (*(S1.top - 1) != '(' && S1.base != S1.top)
{
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
//遇到*或/时
//栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
//否则一直出栈,直到满足上述条件,再入栈
if (ch == '*' || ch == '/')
{
while (S1.base != S1.top && *(S1.top - 1) != '(' && *(S1.top - 1) != '-' && *(S1.top - 1) != '+')
{
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
}
//中缀表达式遍历完成,还需检查栈中是否有未输出字符
//判断栈空,非空则直接出栈
while (S1.base != S1.top)
{
e = Pop(S1);
if (e != '(')
str2 +=e;
}
return str2;
}
struct BiNode* s[MAXSIZE];//定义栈,该栈用于存放树
int top = -1;
//建立二叉树
BiNode* CreatTree(string str)
{
//str为后缀表达式
BiNode* T,* T2;
SqStack S;
BiNode* e1, * e2;
int i;
InitStack(S);
for (i = 0; i < str.size()-1; i++)
{
if (str[i] >= 'a' && str[i] <= 'z')
{
T = new BiNode;
T->date = str[i];
T->lchild = T->rchild = NULL;
s[++top] = T;
}
else
{
T = new BiNode;
T->date = str[i];
e1 = s[top--];
e2 = s[top--];
T->lchild = e2; T->rchild = e1;
s[++top] = T;
}
}
T = new BiNode;
T->date = str[i];T->rchild = s[top--];T->lchild = s[top--];
s[++top] = T;
T2 = new BiNode;
T2 = s[top];
return T2;
}
int Seek(char e,int n)
{
for (int i = 0; i < n; i++)
{
if (a[i].ch == e)
return a[i].value;
}
}
int Count(string str,int n)
{
//str为后缀表达式数组,n变量个数
int sum = 0;
stack<int>S;
int x,x1, x2;
for (int i = 0; i < n; i++)
{
cin >> a[i].ch >> a[i].value;
}
for (int i = 0; i < str.size(); i++)
{
if (str[i] >= 'a' && str[i] <= 'z')
{
x = Seek(str[i], n);
S.push(x);
}
else
{
x2 = S.top(); S.pop();//左操作数
x1 = S.top(); S.pop();//右操作数
switch (str[i])
{
case'+':sum = x1 + x2; break;
case'-':sum = x1 - x2; break;
case'*':sum = x1 * x2; break;
case'/':sum = x1 / x2; break;
}
S.push(sum);
}
}
sum = S.top();
return sum;
}
char arr[1000][1000];
//打印二叉树
void PrintTree(int tag,BiNode* T,int x,int m,int y)
{
arr[2 * tag - 1][(x + m) / 2] = T->date;
if (tag != 1)
{
if (y == 1)
arr[2 * tag - 2][m] = '/';
else
arr[2 * tag - 2][x] = '\\';
}
if (T->lchild != NULL)
PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
if (T->rchild != NULL)
PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}
//计算二叉树的深度
int Depth(BiNode* T)
{
int m, n;
if (T == NULL) return 0;
else {
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n) return (m + 1);
else
return(n + 1);
}
}
bool Judge(int i, int j, int n)
{
for (int k = j + 1; k <= n; k++)
{
if (arr[i][k] != ' ')
return 1;
}
return 0;
}
int main()
{
string str1;//中序表达式
cin >> str1;
int n;//变量个数
cin >> n;
string str2 = Change(str1);//str2为后序表达式
BiNode* T = CreatTree(str2);
int sum = Count(str2, n);
int dp = Depth(T);
cout << str2 << endl;
memset(arr, ' ', sizeof(arr));
PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
for (int i = 1; i <= 2 * dp - 1; i++)
{
for (int j = 1; j <= pow(2.0, dp) - 1; j++)
{
cout << arr[i][j];
if (arr[i][j] != ' ')
{
if(Judge(i,j,pow(2.0,dp)-1))
continue;
else
break;
}
}
cout << endl;
}
cout << sum << endl;
return 0;
}迷宫(2023.12)
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
// 参考答案1
#include <queue>
#include <stdio.h>
#include <string.h>
int m;
char c[100][100];
int xa, ya, xb, yb;
bool vis[100][100];
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
int x;
int y;
int step;
} q[10000];
void bfs(int xa, int ya, int xb, int yb) {
int head = 1, tail = 1;
memset(vis, 0, sizeof(vis));
q[tail].x = xa;
q[tail].y = ya;
q[tail].step = 0;
tail++;
vis[xa][ya] = 1;
int flag = 1;
while (head < tail) {
int x = q[head].x;
int y = q[head].y;
int step = q[head].step;
if (x == xb && y == yb) {
flag = 0;
printf("YES\n");
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m && c[nx][ny] == '.' &&
vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step + 1;
tail++;
}
}
head++;
}
if (flag == 1) {
printf("NO\n");
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", c[i]);
}
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
bfs(xa, ya, xb, yb);
}
return 0;
}// 参考答案1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int k, n, v[102][102];
char a[102][102];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool bfs(int x1, int y1, int x2, int y2) {
if (a[x1][y1] == '#' || a[x2][y2] == '#')
return false;
if (a[x1][y1] != '#' && x1 == x2 && y1 == y2)
return true;
queue<pair<int, int>> q;
pair<int, int> pa;
pa.first = x1;
pa.second = y1;
v[x1][y1] = 1;
q.push(pa);
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= n)
continue;
if (a[xx][yy] == '.' && v[xx][yy] == 0) {
if (xx == x2 && yy == y2)
return true;
v[xx][yy] = 1;
pa.first = xx;
pa.second = yy;
q.push(pa);
}
}
}
return false;
}
int main() {
cin >> k;
int x1, y1, x2, y2;
while (k--) {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cin >> x1 >> y1 >> x2 >> y2;
memset(v, 0, sizeof(v));
if (bfs(x1, y1, x2, y2))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}二叉树的深度(2023.12)
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+7;
struct node{
int left,right;
}t[MAXN];
int n;
void build(){
for(int i=1;i<=n;i++){
cin>>t[i].left>>t[i].right;
}
}
#define rep1(i,n) for(int i=1;i<=n;i++)
inline int dfs(int x){
if(x==-1)return 0;
return max(dfs(t[x].left),dfs(t[x].right))+1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
build();
cout<<dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}//题解3
#include <bits/stdc++.h>
using namespace std;
struct node {
int left;
int right;
} tree[25];
int depth(int root) {
if (root == -1)
return 0;
int a = depth(tree[root].left);
int b = depth(tree[root].right);
return max(a, b) + 1;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tree[i].left >> tree[i].right;
}
cout << depth(1);
return 0;
}Sequence(2023.12)
给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和
时间限制:3000
内存限制:65536
输入
输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例,输出一行用空格隔开的数,表示最小的n个和
样例输入
1 2 3 1 2 3 2 2 3
样例输出
3 3 4
// 参考答案1
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
int T;
cin >> T;
int m, n;
while (T--) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n); // 用a做总的和数组
for (int i = 1; i < m; i++) // 轮接下来的序列
{
for (int j = 0; j < n; j++) {
scanf("%d", &b[j]);
que.push(a[0] + b[j]);
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j] + b[k] < que.top()) {
que.pop();
que.push(a[j] +
b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
}
}
}
for (int i = 0; i < n; i++) {
a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
que.pop(); // 队列已经被清空了,轮下一次
}
}
for (int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d\n", a[n - 1]);
}
return 0;
}// 参考答案2
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int m, n;
vector<int> a[105];
struct Plan {
pii ptr;
bool last; // 记录本方案是否是由ptr2++得到的
int sum;
Plan() {}
Plan(int i, int j, pii _ptr, bool _last) {
ptr = _ptr;
last = _last;
sum = a[i][ptr.first] + a[j][ptr.second];
}
bool operator<(const Plan &oth) const { return sum > oth.sum; }
} init;
priority_queue<Plan> Q;
int main() {
int T;
cin >> T;
while (T--) {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
a[i].clear();
for (int j = 1, x; j <= n; j++) {
scanf("%d", &x);
a[i].push_back(x);
}
sort(a[i].begin(), a[i].end());
}
int i = 1;
for (int j = 2; j <= m; j++, i ^= 1) {
init = Plan(i, j, make_pair(0, 0), 0);
while (!Q.empty())
Q.pop();
Q.push(init);
a[i ^ 1].clear();
while (!Q.empty()) {
Plan now = Q.top();
Q.pop();
a[i ^ 1].push_back(now.sum);
if (a[i ^ 1].size() >= n)
break;
if (!now.last && now.ptr.first < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first + 1, now.ptr.second), 0));
if (now.ptr.second < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first, now.ptr.second + 1), 1));
}
}
for (int k = 0; k < a[i].size(); k++)
printf("%d ", a[i][k]);
printf("\n");
}
}