首页 › 题库 › C/C++编程考级 › 1 树与二叉树

C/C++编程七级 题库

共 38 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 1 树与二叉树 清除
1 单选题 适中 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

一棵有1000个节点的完全二叉树,其深度为(根节点深度为1)?( )

A
9
B
10
C
11
D
12
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

欧拉函数φ(12)的值是?( )

A
2
B
4
C
6
D
8
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 判断题 偏易 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

A*算法是一种启发式搜索算法( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
4 判断题 偏易 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

乘法原理是指完成一件事有多个步骤,每个步骤有多种方法,总方法数为各步骤方法数的乘积。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
5 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

有多少种二叉树(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;
}
题目详情
6 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

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;
}
题目详情
7 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

走迷宫

一个迷宫由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;
}
题目详情
8 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。

时间限制: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至倒数第二个点是树的右子树节点。
*/
题目详情
9 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

快速堆猪

小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制: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;
}
题目详情
10 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

表达式· 表达式树· 表达式求值

众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,

表达式 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;
}
题目详情
11 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

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;
}
题目详情
12 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

二叉树的深度

给定一棵二叉树,求该二叉树的深度

二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度

时间限制: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;
}
题目详情
13 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

快速堆猪

小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制: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;
}


题目详情
14 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。

时间限制: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至倒数第二个点是树的右子树节点。
*/


题目详情
15 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

快速堆猪(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;
}


题目详情
16 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

表达式·表达式树·表达式求值

众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式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;
}


题目详情
17 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

迷宫(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;
}
题目详情
18 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

二叉树的深度(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;
}
题目详情
19 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

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");
  }
}
题目详情
20 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

玩转二叉树

题目收集中……

答案与解析
参考答案

答案整理中……

题目详情