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

C/C++编程七级 题库

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

红色警报

 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。

时间限制:5000

内存限制:65536

输入

输入在第一行给出两个整数 N(0 < N <=500)和 M(<=5000),分别为城市个数(于是默认城市从 0 到 N-1 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以 1 个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数 K 和随后的 K 个被攻占的城市的编号。 注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。

输出

对每个被攻占的城市,如果它会改变整个国家的连通性,则输出“Red Alert: City k is lost!”,其中k是该城市的编号;否则只输出“City k is lost.”即可。如果该国失去了最后一个城市,则增加一行输出“Game Over.”。

样例输入

5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3

样例输出

City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
答案与解析
参考答案
//参考代码1
#include<cstdio>
#include<cstring>
using namespace std;
int pre[505];
bool del[505];
struct node{
	int x,y;
}p[5005];
int find(int x){
	return x==pre[x]?x:pre[x]=find(pre[x]);
}
void merge(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx!=fy)
		pre[fx] = fy;	
}
int main(){
	int n,m,k,x;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	pre[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p[i].x,&p[i].y);
		merge(p[i].x,p[i].y);
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(i==pre[i]) ans++;
	}
	scanf("%d",&k);
	while(k--){
	    scanf("%d",&x);
	    del[x]=true;
	    for(int i=0;i<n;i++)
	    pre[i]=i;
	    
	    for(int i=1;i<=m;i++){
	    	if(!del[p[i].x]&&!del[p[i].y])
	    	merge(p[i].x,p[i].y);
		}
		
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			if(pre[i]==i&&!del[i])
			cnt++;
		}
		if(cnt>ans)
		printf("Red Alert: City %d is lost!\n",x);
		else
		printf("City %d is lost.\n",x);
		ans=cnt;
		if(ans==0)
		printf("Game Over.\n");
	}
	return 0;
}
//参考代码2
#include<bits/stdc++.h>
using namespace std;
#define N 510 
#define M 5010 
int n ,m ,k ,vis[N] ,p[N];
struct node {
    int x;
    int y;
}g[M];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        p[i] = i;
    for (int i = 0; i < m; i++) {
        cin >> g[i].x >> g[i].y;
        if (find(g[i].x) != find(g[i].y))
            p[find(g[i].x)] = find(g[i].y);
    }
    int cnt1 = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] == i) 
            cnt1 ++;
    }
    cin >> k;
    for (int j = 0; j < k; j++) {
        int x ,cnt2 = 0;
        cin >> x;
        vis[x] = 1;
        for (int i =0 ; i < n; i++) 
            p[i] = i;
        for (int i = 0; i < m; i++) {
            if (vis[g[i].x] == 1 ||vis[g[i].y] == 1) 
                continue;
            if (find(g[i].x) != find(g[i].y))
                p[find(g[i].x)] = find(g[i].y);
        }
        for (int i = 0; i < n; i++) {
            if (p[i] == i)
                cnt2++;
        }
        if (cnt2 - cnt1 > 1) 
            printf ("Red Alert: City %d is lost!\n" ,x);
        else 
            printf ("City %d is lost.\n" ,x);
        cnt1 = cnt2;
    }
    if (k >= n) cout << "Game Over.\n";
    return 0;
}
题目详情
22 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

到底爱不爱我

 古代少女有了心上人时,会悄悄折一条树枝,揪那枝上的叶子,揪一片叶子念一句“爱我”,再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候,看看是停在“爱”还是“不爱”。

但聪明的慧娘一眼洞穿,只要数一下叶子有多少片,根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始,就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫,理科生杀死浪漫。

于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”:

- “专情枝”:是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候,这根枝条的根部才传出“爱”;否则树枝根部传出的是“不爱”。

- “博爱枝”:也是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候,这根枝条的根部才传出“不爱”;否则树枝根部传出的都是“爱”。

- “情变枝”:是没有分岔的一根直枝,如果一端接到“爱”,另一端必须传出“不爱”;反之如果一端接到“不爱”,另一端则会传出“爱”。

慧娘将这些树枝摆放在院子里,布了一个“情阵”,从某一枝的根部开始,扩散开去,令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来,在初始一枝的根部,她能得到“爱”还是“不爱”?

时间限制:10000

内存限制:65536

输入

输入在第一行中给出正整数 N(≤ 30),是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行,第 i 行给出第 i 枝的描述,格式为 类型 左分枝连接的编号 右分枝连接的编号 其中 `类型` 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝,则后面跟的是其唯一末端连接的情枝编号,并没有两个分枝的信息。如果一个分枝是末梢,并没有连接其它枝条,则对应编号为 0。 接下来一行中给出正整数 K(≤ 30),是慧娘询问的次数。以下 K 行,每行给出一个由 0 和 1 组成的字符串,其中 0 表示“不爱”,1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。

输出

对慧娘的每个询问,如果她在初始一枝的根部能得到“爱”,就输出 `Ai`;否则输出 `BuAi`。

样例输入

6
2 6 4
1 0 0
3 1
2 0 0
3 0
1 5 2
5
11111
00000
11100
10011
01100

样例输出

BuAi
Ai
Ai
BuAi
BuAi

提示

样例说明: 样例对应的情阵以及慧娘第 3 问的情势如图所示,其中完整的心对应 1,裂开的心对应 0。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int t,root,i,tree[44][3],p[44],f[44],n;
string s;
bool dfs(int u){
	int x,y;
	if(p[u]!=3){
		if(tree[u][1])x=dfs(tree[u][1]);
		else x=s[i++]-'0';
		if(tree[u][2])y=dfs(tree[u][2]);
		else y=s[i++]-'0';
		if(p[u]==1)return x&&y;
		return x||y;
	}
	else {
		if(tree[u][1])return !dfs(tree[u][1]);
		else return !(s[i++]-'0');
	}
}
signed main(){
	ios;
	cin>>n;
	for(int i=1,x,y;i<=n;i++){
		cin>>p[i];
		if(p[i]==1||p[i]==2){
			cin>>x>>y;
			tree[i][1]=x;
			tree[i][2]=y;
			f[x]=f[y]=1;
		}
		else {
			cin>>x;
			tree[i][1]=x;
			f[x]=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]==0){
			root=i;
			break;
		}
	}
	cin>>t;
	while(t--){
		cin>>s;
		i=0;
		if(dfs(root))cout<<"Ai\n";
		else cout<<"BuAi\n";
	}
	return 0;
}
题目详情
23 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

兰州拉面派餐系统

兰州拉面是著名美食,其煮面很有讲究,不同种类的面需要煮不同的时长。拉面馆的煮面师傅的规则很简单,只要手头有煮面篮子是空闲的,就把下一份客单指定的面放到空闲篮子里煮;如果空闲的篮子不止一个,那么先放到其中编号最小的篮子里煮;如果没有篮子是空闲的,就等待。一个篮子里的面煮够了时间,师傅要准时捞出来放到该客单对应的碗里,招呼服务员端给客人;如果有多个篮子里的面同时到了捞取时间,师傅会同时捞起,但要本着先到先得的原则,按下单顺序招呼送餐。

在生意火爆的拉面馆里,煮面师傅需要很强的记忆力和计时能力,才能面对源源不断的客单,同时照顾一大堆煮面篮子而不出错。如果面的品种不太多,篮子也不太多,那一位拉面师傅的大脑还是能应对的。但如果我们有上千种面、上万只煮面篮、数十万客单呢…… 这就需要请你帮忙,写个派餐系统来完成这个任务了。

时间限制:7000

内存限制:65536

输入

输入在第一行中给出 3 个正整数:N(≤ 103)为面的种类数;M(≤ 104)为煮面篮子的个数;L(≤ 105)为客单总数。于是我们假设面的种类从 1 到 N 编号、篮子从 1 到 M 编号、客单从 1 到 L 编号。 第二行给出 N 个不超过 10 的正整数,第 i 个数字对应第 i 种面需要煮的时间长度(分钟)。 第三行给出 L 个正整数,第 i 个数字对应第 i 份客单所点的面种 —— 这里我们将情况简化为一份客单只要一种面,并且只要一碗,所以只要给出面的种类即可。 一行中数字间以空格分隔。 因为面馆的生意太火爆,我们可以认为所有的客单都是在开门前就预约好的,并且是按预约的顺序递增编号的。此外,与煮面的时长相比,下面、捞面和送餐的时长是可以忽略不计的。

输出

首先按照送单顺序在一行中输出所有客单的编号和送餐时间,格式为 `编号:时间`。 随后在下一行按照编号递增序输出每只篮子煮了多少碗面。 一行的输出之间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

3 5 10
3 5 8
2 1 3 3 1 1 2 1 3 2

样例输出

2:3 5:3 1:5 6:6 3:8 4:8 7:8 8:8 10:13 9:14
3 3 1 1 2
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100010;
 
typedef pair<int,int> PII;	
 
int n,m,l;
// t代表每种面需要的时间,c代表每个顾客需要的面的种类,cnt代表每个篮子被用的次数 
int t[N], c[N], cnt[N];	 
// 小跟堆升序,维护篮子所用的时间和篮子编号
priority_queue<PII,vector<PII>,greater<PII>> heap;	 
// 维护时间,顾客编号,可以实现时间由小到大排序 
vector<PII> ans; 
 
//对时间相同的按编号从小到大排序 
bool cmp(PII a,PII b)
{
	if(a.first!=b.first)	return a.first<b.first;
	return a.second<b.second;		
} 
 
int main()
{
	cin>>n>>m>>l;
	
	for(int i=1;i<=n;i++)	cin>>t[i];	// 每种面需要的时间 
	for(int i=1;i<=l;i++)	cin>>c[i];	// 每个顾客需要的面的种类
	for(int i=1;i<=m;i++)	 heap.push({0,i});	// 开始时间都是0,然后对篮子编号
	
	for(int i=1;i<=l;i++)
	{
		auto u=heap.top();	// 取当前时间被用最短的篮子 
		heap.pop();
		
		int id=u.second, time=u.first;
		cnt[id]++;
		ans.push_back({time+t[c[i]], i});	
		heap.push({time+t[c[i]],id});
	} 
	sort(ans.begin(),ans.end(),cmp);
	
	for(int i=0;i<l;i++)
	{
		if(i!=l-1)	cout<<ans[i].second<<":"<<ans[i].first<<" ";
		else	cout<<ans[i].second<<":"<<ans[i].first<<endl;
	}
	
	for(int i=1;i<=m;i++)
	{
		if(i!=m)	cout<<cnt[i]<<" ";
		else	cout<<cnt[i]<<endl;
	}
	
	return 0;
}
题目详情
24 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

有多少种二叉树(2024-3-7级)

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

快速堆猪(2024-3-7级)

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

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


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

二叉树遍历

题目描述

有一棵二叉树,结点数量不超过 26 个,树上的每个结点都有一个大写字母。

给定这棵二叉树的中序遍历及后序遍历,请输出它的前序遍历。

输入格式

第一行:一个字符串,表示二叉树的中序遍历;

第二行:一个字符串,表示二叉树的后序遍历。

输出格式

单独一行:一个字符串,表示二叉树的前序遍历。

输入样例

DBEAC

DEBCA

输出样例

ABDEC

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;

// 中序in, 后序post, 输出前序
void build(string in, string post) {
    if (in.empty()) return;
    // 后序最后一个是根
    char root = post.back();
    cout << root;
    int pos = in.find(root);
    // 递归左右
    build(in.substr(0, pos), post.substr(0, pos));
    build(in.substr(pos+1), post.substr(pos, in.size()-pos-1));
}

int main() {
    string in, post;
    cin >> in >> post;
    build(in, post);
    return 0;
}
题目详情
27 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

平衡运输

题目描述

远古遗迹中发掘出了 n 件魔力核心,第 i 件核心蕴含的能量为 ki。

为了安全运输,需要将这些核心分配到两个不同的能量舱(记为舱 A 和舱 B)中。

每件核心必须整个放入一个舱,不可拆分。

分配完成后,设舱 A 的总能量为 sa,舱 B 的总能量为 sb。

为了平衡运输风险,希望两个舱中总能量较大的一方尽可能小,即最小化 max(sa,sb)。

请你计算这个最小的最大值。

输入格式

第一行,一个整数 n。

第二行,n 个整数 k1,k2,…,kn。

输出格式

输出一个整数,表示 max(sa,sb) 的最小可能值。

输入样例#1

5
2 3 5 10 12

输出样例#1

17

输入样例#2

6
22 25 26 45 22 31

输出样例#2

89

说明提示

2≤n≤20

1≤ki≤108

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include<iostream>
int N;
int A[20];
int S = 0;
int solve(int i, int sum)
{
    if (i == N)
    {
        return std::max(sum, S - sum);
    }
    else
    {
        auto pick = solve(i + 1, sum + A[i]);
        auto drop = solve(i + 1, sum);
        return std::min(pick, drop);
    }
}
int main()
{
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        S += A[i];
    }
    std::cout << solve(0, 0) << "\n";
}
题目详情
28 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

专属教室

题目描述

在一所学校中,有 N 个班级,每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si,但学校计划将其调整到新的教室 Ti。

已知所有班级当前使用的教室编号互不相同,所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室,且一次只能安排一个班级进行更换。在更换时,目标教室必须是空闲的。

学校希望找到一个合理的更换顺序,使得所有班级都能顺利迁入目标教室。请判断是否可能。

输入格式

第一行一个整数 N。

接下来 N 行,每行两个字符串 Si 和 Ti,表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。

输出格式

如果存在一种顺序使得所有班级都能完成更换,输出 Yes,否则输出 No。

输入样例#1

2
b m
m d

输出样例#1

Yes

输入样例#2

3
a b
b c
c a

输出样例#2

No

说明提示

1≤N≤105

Si,Ti 为由小写英文字母组成的字符串,长度在 1 到 8 之间。

Si≠Ti

所有 Si 互不相同。

所有 Ti 互不相同。

限制

时间限制:1000ms

内存限制:256MiB


答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<string, vector<string>> adj;
map<string, int> state;

bool has_cycle(string v) {
  state[v] = 1;
  
  for (string next_v : adj[v]) {
    if (state[next_v] == 1) return true;
    if (state[next_v] == 0) {
      if (has_cycle(next_v)) return true;
    }
  }
  
  state[v] = 2;
  return false;
}

int main() {
  int N;
  cin >> N;
  
  vector<string> S(N), T(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i] >> T[i];
    adj[S[i]].push_back(T[i]);
  }
  
  for (auto const& [name, _] : adj) {
    if (state[name] == 0) {
      if (has_cycle(name)) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  
  cout << "Yes" << endl;
  return 0;
}
题目详情
29 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

数字之和

题目描述

给定一个数字字符串 n,定义一次操作为:移除字符串中一个非空子串,并将剩余部分拼接形成新数字。

求所有可能操作方案生成的新数字之和,结果对 109+7取模。

输入格式

一行字符串 n

输出格式

一个整数,表示所有方案生成数字之和取模后的结果。


输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤105,| n |表示字符串长度。

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_LEN = 1e5 + 10;

long long pow10[MAX_LEN];
long long inv9, inv81;

long long mod_pow(long long base, long long exp, int mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

void precompute(int L) {
    pow10[0] = 1;
    for (int i = 1; i <= L; ++i) {
        pow10[i] = (pow10[i - 1] * 10) % MOD;
    }
    inv9 = mod_pow(9, MOD - 2, MOD);
    inv81 = mod_pow(81, MOD - 2, MOD);
}

int main() {
    string n;
    cin >> n;
    int L = n.size();
    precompute(L);
    
    long long ans = 0;
    for (int k = 0; k < L; ++k) {
        int d = n[k] - '0';
        if (d == 0) {
            continue; // 贡献为0,可直接跳过
        }
        
        // 计算左侧贡献
        long long left = 0;
        if (k > 0) {
            long long count = (1LL * k * (k + 1)) / 2 % MOD;
            int exponent = L - k - 1;
            long long pow_val = pow10[exponent];
            left = (count * pow_val) % MOD;
        }
        
        // 计算右侧贡献
        long long right = 0;
        int exponent = L - k - 1;
        if (exponent > 0) {
            long long part1 = (1LL * (L - k - 1) * pow10[exponent]) % MOD;
            long long term1 = (part1 * inv9) % MOD;
            
            long long part2 = (pow10[exponent] - 1 + MOD) % MOD;
            long long term2 = (part2 * inv81) % MOD;
            
            right = (term1 - term2 + MOD) % MOD;
        }
        
        long long total = (left + right) % MOD;
        ans = (ans + 1LL * d * total) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}
题目详情
30 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换!

最初,所有 N辆花车排成一行,花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中:

· 第 1 分钟:位置 a1 与 b1 的花车交换位置

· 第 2 分钟:位置 a2 与 b2 的花车交换位置

· ……

· 第 K 分钟:位置 aK 与 bK 的花车交换位置

· 第 K+1 分钟:重新从 (a1,b1) 开始交换(即位置 a1 与 b1 交换)

· 第 K+2 分钟:位置 a2 与 b2 交换

· 如此无限循环……

请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 N,K。

接下来 K 行每行包含 ai,bi(1≤ai<bi≤N)。

输出格式

输出 N行,第 i行为花车 i能到达的不同位置数量。

输入样例

5 4
1 3
1 2
2 3
2 4

输出样例

4
4
3
4
1

说明提示

样例解释

· 花车 1 可到达位置 {1,2,3,4}

· 花车 2 可到达位置 {1,2,3,4}

· 花车 3 可到达位置 {1,2,3}

· 花车 4 可到达位置 {1,2,3,4}

· 花车 5 始终在位置 5(未移动)

【数据范围】

1≤K≤2×105

2≤N≤105

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> swaps(K);
    unordered_set<int> S;
    for (int i = 0; i < K; ++i) {
        int a, b;
        cin >> a >> b;
        swaps[i] = {a, b};
        S.insert(a);
        S.insert(b);
    }

    // 计算P = Q_K,即经过K步后的置换
    vector<int> Q(N + 1), R(N + 1); // 1-based
    for (int i = 1; i <= N; ++i) {
        Q[i] = i;
        R[i] = i;
    }
    for (auto [a, b] : swaps) {
        int x1 = R[a];
        int x2 = R[b];
        swap(R[a], R[b]);
        swap(Q[x1], Q[x2]);
    }
    vector<int> P = Q; // P是Q_K

    // 对P进行循环分解
    vector<bool> visited(N + 1, false);
    vector<vector<int>> cycles;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            vector<int> cycle;
            int cur = i;
            while (!visited[cur]) {
                visited[cur] = true;
                cycle.push_back(cur);
                cur = P[cur];
            }
            cycles.push_back(cycle);
        }
    }

    // 为每个循环计算答案
    vector<int> ans(N + 1);
    for (auto& cycle : cycles) {
        // 检查循环是否与S有交集
        bool has_intersection = false;
        for (int x : cycle) {
            if (S.count(x)) {
                has_intersection = true;
                break;
            }
        }
        if (!has_intersection) {
            // 答案是循环大小
            int sz = cycle.size();
            for (int x : cycle) {
                ans[x] = sz;
            }
            continue;
        }

        // 模拟current_set的变化,计算Y的大小
        unordered_set<int> current_set(cycle.begin(), cycle.end());
        unordered_set<int> Y(current_set.begin(), current_set.end());

        for (int t = 0; t < K - 1; ++t) { // t处理0到K-2,对应步骤1到K-1
            auto [a, b] = swaps[t];
            bool has_a = current_set.count(a);
            bool has_b = current_set.count(b);

            if (has_a && has_b) {
                // 交换后集合不变
                continue;
            } else if (has_a) {
                current_set.erase(a);
                current_set.insert(b);
                Y.insert(b);
            } else if (has_b) {
                current_set.erase(b);
                current_set.insert(a);
                Y.insert(a);
            }
            // 否则集合不变
        }

        int res = Y.size();
        for (int x : cycle) {
            ans[x] = res;
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}
题目详情
31 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

公平

题目描述

有多干所精英学院和 N 名天才学员(编号 1 到 N)。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。

联盟定期进行学员调院操作(共 Q 次):第 j次操作将学员 Cj 调到学院 Dj。

联盟公平指数定义为:

对每所至少有一名学员的学院,取该学院最高能力值;再取这些最高能力值中的最小值。

请计算每次调院操作后的联盟公平指数。

输入格式

· 第一行:N Q

· 接下来 N 行:每行 Ai Bi,表示学员 ii 的能力值和初始学院

· 接下来 Q 行:每行 Cj Dj,表示将学员 Cj 调到学院 Dj

输出格式

· Q 行:每行一个整数,表示每次操作后的公平指数


输入样例#1

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

输出样例#1

6

2

6

输入样例#2

2 2

4208 1234

3056 5678

1 2020

2 2020

输出样例#2

3056

4208

说明提示

1≤N,Q≤2×105,1≤N,Q≤2×105

1≤Ai≤109,1≤Ai≤109

1≤Cj≤N,1≤Cj≤N

1≤Bi,Dj≤2×105,1≤Bi,Dj≤2×105

输入均为整数

每次转园操作会改变所属学院

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> ability(N + 1);
    vector<int> current_college(N + 1);
    unordered_map<int, multiset<int>> college_students;

    for (int i = 1; i <= N; ++i) {
        int A, B;
        cin >> A >> B;
        ability[i] = A;
        current_college[i] = B;
        college_students[B].insert(A);
    }

    multiset<int> global_max;
    for (const auto& pair : college_students) {
        const auto& s = pair.second;
        if (!s.empty()) {
            global_max.insert(*s.rbegin());
        }
    }

    while (Q--) {
        int Cj, Dj;
        cin >> Cj >> Dj;
        int c = Cj;
        int a = ability[c];
        int old_college = current_college[c];
        int new_college = Dj;

        // 处理旧学院
        auto& old_set = college_students[old_college];
        int x = *old_set.rbegin();
        auto it_old = old_set.find(a);
        old_set.erase(it_old);

        if (old_set.empty()) {
            auto it_global = global_max.find(x);
            if (it_global != global_max.end()) {
                global_max.erase(it_global);
            }
            college_students.erase(old_college);
        } else {
            int x_new = *old_set.rbegin();
            if (x_new != x) {
                auto it_global = global_max.find(x);
                if (it_global != global_max.end()) {
                    global_max.erase(it_global);
                }
                global_max.insert(x_new);
            }
        }

        // 处理新学院
        auto& new_set = college_students[new_college];
        bool was_empty = new_set.empty();
        int y = 0;
        if (!was_empty) {
            y = *new_set.rbegin();
        }
        new_set.insert(a);
        int y_new = *new_set.rbegin();

        if (was_empty) {
            global_max.insert(y_new);
        } else {
            if (y_new != y) {
                auto it_global = global_max.find(y);
                if (it_global != global_max.end()) {
                    global_max.erase(it_global);
                }
                global_max.insert(y_new);
            }
        }

        current_college[c] = new_college;
        cout << *global_max.begin() << '\n';
    }

    return 0;
}
题目详情
32 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

子序列

题目描述

给定两个整数序列,第一个序列长度为 n,第二个序列长度为 m。请问,这两个序列有多少种公共的子序列?输出数量模 998244353 的余数。

所谓子序列,是指从原序列中选择部分或全部元素组成新序列,这些元素在原序列中不必连续,但要保持在原序列中的顺序。只要下标不同,哪怕数字相同,也要算成不同的子序列。

输入格式

第一行:两个整数表示 n 与 m;

第二行: n 个数字 a1,a2,... ,an;

第三行:m 个数字 b1,b2,... ,bm;

输出格式

单个整数表示答案。

输入样例

4 3
3 4 6 2
3 3 2

输出样例

6

说明提示

1≤n,m≤2000

1≤ai,bj≤100,000

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 空子序列
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int j = 0; j <= m; ++j) dp[0][j] = 1;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
            } else {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
            }
            if (dp[i][j] < 0) dp[i][j] += MOD;
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}
题目详情
33 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

逻辑表达式

题目描述

给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^:

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值:0、1、?。

每个 ? 必须赋值成为 0 或 1 中的一种,请问有多少种不同的赋值方式,可以让整个逻辑表达式的值为 0?

由于答案可能很大,请输出方案数模1,000,000,007 的余数。

前缀表达式的定义如下:

0、1、? 都是前缀表达式;

如果 x,y 都是前缀表达式,则 &xy、|xy、^xy 都是前缀表达式;

不满足以上两条规则的表达式都不是前缀表达式。

输入格式

单个字符串表示输入的前缀表达式

输出格式

单个整数:表示答案模 1,000,000,007 的余数。


输入样例#1

&??

输出样例#1

3

输入样例#2

||??|||?^?|0|1&???|??

输出样例#2

4

输入样例#3

|?^?|0|&??||?^?|1??

输出样例#3

64

说明提示

设 ∣s∣表示输入字符串的长度

50%的数据,1≤∣s∣<1,000

100%的数据,1≤∣s∣<200,000

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
//C语言参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

typedef struct {
   long long zero;
   long long one;
} Node;

Node stack[200000];
int top = -1;

void push(Node node) {
   stack[++top] = node;
}

Node pop() {
   return stack[top--];
}

int main() {
   char s[200001];
   scanf("%s", s);
   int len = strlen(s);

   for (int i = len - 1; i >= 0; i--) {
       char c = s[i];
       if (c == '0') {
           push((Node){1, 0});
       } else if (c == '1') {
           push((Node){0, 1});
       } else if (c == '?') {
           push((Node){1, 1});
       } else {
           Node right = pop();
           Node left = pop();
           Node res = {0, 0};
           if (c == '&') {
               res.zero = (left.zero * right.zero % MOD + left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
               res.one = left.one * right.one % MOD;
           } else if (c == '|') {
               res.zero = left.zero * right.zero % MOD;
               res.one = (left.one * right.zero % MOD + left.zero * right.one % MOD + left.one * right.one % MOD) % MOD;
           } else if (c == '^') {
               res.zero = (left.zero * right.zero % MOD + left.one * right.one % MOD) % MOD;
               res.one = (left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
           }
           push(res);
       }
   }

   Node result = pop();
   printf("%lld\n", result.zero);
   return 0;
}
//C++参考代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MOD = 1e9+7;

struct Node {
    long long zero, one;
    Node(long long z=0, long long o=0) : zero(z), one(o) {}
};

int main() {
    string s;
    cin >> s;
    stack<Node> st;
    
    for (int i = s.size()-1; i >= 0; --i) {
        char c = s[i];
        if (c == '0') {
            st.push(Node(1, 0));
        } else if (c == '1') {
            st.push(Node(0, 1));
        } else if (c == '?') {
            st.push(Node(1, 1));
        } else {
            Node right = st.top(); st.pop();
            Node left = st.top(); st.pop();
            Node res;
            
            if (c == '&') {
                res.zero = (right.zero * left.zero % MOD + 
                           right.zero * left.one % MOD + 
                           right.one * left.zero % MOD) % MOD;
                res.one = right.one * left.one % MOD;
            } else if (c == '|') {
                res.zero = right.zero * left.zero % MOD;
                res.one = (right.one * left.one % MOD + 
                          right.one * left.zero % MOD + 
                          right.zero * left.one % MOD) % MOD;
            } else if (c == '^') {
                res.zero = (right.zero * left.zero % MOD + 
                           right.one * left.one % MOD) % MOD;
                res.one = (right.zero * left.one % MOD + 
                          right.one * left.zero % MOD) % MOD;
            }
            st.push(res);
        }
    }
    
    cout << st.top().zero % MOD << endl;
    return 0;
}


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

联盟

题目描述

在国际会议上,共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况,请计算存在多少种合法的联盟分配方案。

输入格式

第一行:单个整数 n 表示国家数量

第二行到第 n 行:在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n,其中

ci,j=0-表示 i 号国家与 j 号国家不接壤

ci,j=1 表示 i 号国家与 j 号国家接壤

输出格式

单个整数:表示合法的联盟分配方案总数。


输入样例#1

3
1 1
1

输出样例#1

6

输入样例#2

4
1 1 1
1 1
1

输出样例#2

0

说明提示

数据范围

对于 50% 的数据,1≤n≤12

对于 100% 的数据,1≤n≤20

样例1说明

三国两两接壤,形成三角形。三个联盟的排列方案为 3!=6种。

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> color;
int count = 0;

bool isValid(int country, int c) {
    for (int i = 0; i < country; ++i) {
        if (adj[i][country] && color[i] == c) {
            return false;
        }
    }
    return true;
}

void dfs(int country) {
    if (country == n) {
        count++;
        return;
    }
    
    for (int c = 1; c <= 3; ++c) {
        if (isValid(country, c)) {
            color[country] = c;
            dfs(country + 1);
            color[country] = 0;
        }
    }
}

int main() {
    cin >> n;
    adj.resize(n, vector<int>(n, 0));
    color.resize(n, 0);
    
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            cin >> adj[i][j];
            adj[j][i] = adj[i][j];
        }
    }
    
    dfs(0);
    cout << count << endl;
    return 0;
}
题目详情
35 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

树的同构

给定两棵树  T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

图一

图二

现给定两棵树,请你判断它们是否是同构的。

时间限制:1000

内存限制:65536

输入

输入给出2棵二叉树的信息。对于每棵树,首先在一行中给出一个非负整数 n(≤ 10),即该树的结点数(此时假设结点从 0 到 n -1 编号);随后 n 行,第 i 行对应编号第 i 个结点,给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出

如果两棵树是同构的,输出“Yes”,否则输出“No”。


样例输入

样例#1(对应图1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

样例#2(对应图2):

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

样例输出

样例#1:

Yes

样例#2:

No
答案与解析
参考答案

答案整理中……

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

网红点打卡攻略

一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

时间限制:1000

内存限制:65536

输入

首先第一行给出两个正整数:网红点的个数 N(1 < N ≤ 200)和网红点之间通路的条数 M。随后 M 行,每行给出有通路的两个网红点、以及这条路上的旅行花费(为正整数),格式为“网红点1 网红点2 费用”,其中网红点从 1 到 N 编号;同时也给出你家到某些网红点的花费,格式相同,其中你家的编号固定为 0。 再下一行给出一个正整数 K,是待检验的攻略的数量。随后 K 行,每行给出一条待检攻略,格式为: n V1 V2 … Vn 其中 n (≤ 200) 是攻略中的网红点数,Vi 是路径上的网红点编号。这里假设你从家里出发,从 V1 开始打卡,最后从 Vn 回家。

输出

在第一行输出满足要求的攻略的个数。 在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。 题目保证至少存在一个有效攻略,并且总路费不超过 109。


样例输入

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

样例输出

3
5 11

提示

样例说明: 第 2、3、4、6 条都不满足攻略的基本要求,即不能做到从家里出发,在每个网红点打卡仅一次,且能回到家里。所以满足条件的攻略有 3 条。 第 1 条攻略的总路费是:(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14; 第 5 条攻略的总路费同理可算得:1 + 1 + 1 + 2 + 3 + 1 + 2 = 11,是一条更省钱的攻略; 第 7 条攻略的总路费同理可算得:2 + 1 + 1 + 2 + 2 + 2 + 1 = 11,与第 5 条花费相同,但序号较大,所以不输出。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> matrix(201, vector<int>(201, -1));
	for (int i = 0; i < M; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		matrix[u][v] = c;
		matrix[v][u] = c;
	}
	int K;
	cin >> K;
	vector<pair<int, int>> valid_plans;
	for (int plan_idx = 1; plan_idx <= K; ++plan_idx) {
		int n;
		cin >> n;
		vector<int> Vi(n);
		for (int i = 0; i < n; ++i) {
			cin >> Vi[i];
		}
		if (n != N) {
			continue;
		}
		vector<bool> visited(N + 1, false);
		bool valid_vi = true;
		for (int v : Vi) {
			if (v < 1 || v > N || visited[v]) {
				valid_vi = false;
				break;
			}
			visited[v] = true;
		}
		for (int i = 1; i <= N && valid_vi; ++i) {
			if (!visited[i]) {
				valid_vi = false;
				break;
			}
		}
		if (!valid_vi) {
			continue;
		}
		int cost = 0;
		int current = 0;
		bool path_valid = true;
		if (matrix[current][Vi[0]] == -1) {
			path_valid = false;
		} else {
			cost += matrix[current][Vi[0]];
			current = Vi[0];
		}
		for (int i = 1; i < n && path_valid; ++i) {
			int next = Vi[i];
			if (matrix[current][next] == -1) {
				path_valid = false;
			} else {
				cost += matrix[current][next];
				current = next;
			}
		}
		if (path_valid) {
			if (matrix[current][0] == -1) {
				path_valid = false;
			} else {
				cost += matrix[current][0];
			}
		}
		if (path_valid) {
			valid_plans.emplace_back(plan_idx, cost);
		}
	}
	cout << valid_plans.size() << endl;
	if (!valid_plans.empty()) {
		auto min_plan = valid_plans[0];
		for (const auto &p : valid_plans) {
			if (p.second < min_plan.second || (p.second == min_plan.second && p.first < min_plan.first)) {
				min_plan = p;
			}
		}
		cout << min_plan.first << " " << min_plan.second << endl;
	}
	return 0;
}


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

树的偏斜度

对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。

时间限制:1000

内存限制:65536

输入

输入在第一行给出正整数 n (≤ 103),为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列,键值为 1 到 n 的整数。同行数字间以空格分隔。

输出

在一行中按以下格式输出树的偏斜度: Ds = nL - nR


样例输入

7
1 2 7 5 4 3 6
1 2 3 4 7 5 6

样例输出

2 = 3 - 1
答案与解析
参考答案
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
 
pair<int, int> calcSkew(vector<int>& post, vector<int>& in, int ps, int pe, int is, int ie) {
    if (ps > pe) return {0, 0};
    int root = post[pe], idx = is;
    while (in[idx] != root) idx++;
    pair<int, int> left = calcSkew(post, in, ps, ps + idx - is - 1, is, idx - 1);
    pair<int, int> right = calcSkew(post, in, ps + idx - is, pe - 1, idx + 1, ie);
    return {left.first  + right.first  + (idx > is && idx == ie), left.second  + right.second  + (idx < ie && idx == is)};
}
 
int main() {
    int n;
    cin >> n;
    vector<int> post(n), in(n);
    for (int &x : post) cin >> x;
    for (int &x : in) cin >> x;
    pair<int, int> res = calcSkew(post, in, 0, n - 1, 0, n - 1);
    cout << res.first  - res.second  << " = " << res.first  << " - " << res.second  << endl;
}
//参考代码2
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {
	if (inStart > inEnd || postStart > postEnd) return nullptr;
	int rootVal = postorder[postEnd];
	TreeNode* root = new TreeNode(rootVal);
	int rootIndex = inMap[rootVal];
	int leftSize = rootIndex - inStart;
	root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1, inMap);
	root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1, inMap);
	return root;
}

void countSkew(TreeNode* node, int& nL, int& nR) {
	if (!node) return;
	bool hasLeft = node->left != nullptr;
	bool hasRight = node->right != nullptr;
	if (hasLeft && !hasRight) nL++;
	else if (!hasLeft && hasRight) nR++;
	countSkew(node->left, nL, nR);
	countSkew(node->right, nL, nR);
}

int main() {
	int n;
	cin >> n;
	vector<int> post(n), in(n);
	for (int i = 0; i < n; i++) cin >> post[i];
	for (int i = 0; i < n; i++) cin >> in[i];
	
	unordered_map<int, int> inMap;
	for (int i = 0; i < n; i++) inMap[in[i]] = i;
	
	TreeNode* root = buildTree(in, post, 0, n-1, 0, n-1, inMap);
	
	int nL = 0, nR = 0;
	countSkew(root, nL, nR);
	
	cout << nL - nR << " = " << nL << " - " << nR << endl;
	return 0;
}


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

是不是堆

二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。

时间限制:1000

内存限制:65536

输入

输入在一行中给出两个正整数:m(≤ 100)是将要测试的完全二叉树的数量;n(1 < n ≤ 1000)是完全二叉树中的结点数。 随后 m 行,每行给出 n 个互不相同的键值(均在整型范围内),为完全二叉树的层序遍历序列。

输出

对输入的每棵完全二叉树,如果它是最大堆(大顶堆),就在一行中输出 `Max Heap`;如果是最小堆(小顶堆),则输出 `Min Heap`;如果根本不是堆,则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

样例输出

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10
答案与解析
参考答案
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
 
string checkHeap(const vector<int>& tree) {
    int n = tree.size(); 
    for (int i = 0; i < n; ++i) {
        int l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && tree[i] > tree[l]) return "Min Heap";
        if (r < n && tree[i] > tree[r]) return "Min Heap";
        if (l < n && tree[i] < tree[l]) return "Max Heap";
        if (r < n && tree[i] < tree[r]) return "Max Heap";
    }
    return "Not Heap";
}
 
void printPostOrder(const vector<int>& tree, int i, vector<int>& res) {
    if (i >= tree.size())  return;
    printPostOrder(tree, 2 * i + 1, res);
    printPostOrder(tree, 2 * i + 2, res);
    res.push_back(tree[i]); 
}
 
int main() {
    int m, n;
    cin >> m >> n;
    while (m--) {
        vector<int> tree(n);
        for (int &x : tree) cin >> x;
        cout << checkHeap(tree) << endl;
        vector<int> res;
        printPostOrder(tree, 0, res);
        for (int i = 0; i < res.size();  ++i) cout << res[i] << (i == res.size()  - 1 ? '\n' : ' ');
    }
}


//参考代码2
#include <iostream>
#include <vector>
using namespace std;

void postOrder(int index, const vector<int>& arr, vector<int>& res) {
	if (index >= arr.size()) return;
	postOrder(2 * index + 1, arr, res);
	postOrder(2 * index + 2, arr, res);
	res.push_back(arr[index]);
}

int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<int>> testCases(m, vector<int>(n));
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> testCases[i][j];
		}
	}
	
	for (const auto& arr : testCases) {
		bool is_max = true, is_min = true;
		int size = arr.size();
		for (int i = 0; i < size; ++i) {
			int left = 2 * i + 1;
			int right = 2 * i + 2;
			if (left < size) {
				if (arr[i] < arr[left]) is_max = false;
				if (arr[i] > arr[left]) is_min = false;
			}
			if (right < size) {
				if (arr[i] < arr[right]) is_max = false;
				if (arr[i] > arr[right]) is_min = false;
			}
			if (!is_max && !is_min) break;
		}
		
		if (is_max) cout << "Max Heap\n";
		else if (is_min) cout << "Min Heap\n";
		else cout << "Not Heap\n";
		
		vector<int> post;
		postOrder(0, arr, post);
		for (int i = 0; i < post.size(); ++i) {
			if (i) cout << ' ';
			cout << post[i];
		}
		cout << endl;
	}
	return 0;
}

题目详情