🚀欢迎来到本文🚀
🍉个人简介：Hello大家好呀，我是陈童学，一个与你一样正在慢慢前行的普通人。
🏀个人主页：@陈童学哦`CSDN
💡所属专栏：PTA
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝
⛱️刷题的当下应是享受的！望与诸君共勉！🏄‍♂️

在这里插入图片描述

题目汇总

题解
- L2-004 这是二叉搜索树吗？
- L2-005 集合相似度
- L2-006 树的遍历
- L2-007 家庭房产
写在最后

题解

L2-004 这是二叉搜索树吗？

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：
输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：
7
8 6 5 7 10 8 11
输出样例 1：
YES
5 7 6 8 11 10 8
输入样例 2：
7
8 10 11 8 6 7 5
输出样例 2：
YES
11 8 10 7 5 6 8
输入样例 3：
7
8 6 8 5 10 9 11
输出样例 3：
NO

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,a[maxn];
vector<int>now;
void f(int l,int r,int x)
{if(l>r)return ;int tl=r;int tr=l+1;if(!x){while(tl>l&&a[tl]>=a[l])tl--;while(tr<=r&&a[tr]<a[l])tr++;}else{while(tl>l&&a[tl]<a[l]){tl--;}while(tr<=r&&a[tr]>=a[l]){tr++;}}if(tr-tl!=1)return;f(l+1,tl,x);f(tr,r,x);now.push_back(a[l]);
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);f(0,n-1,0);if(now.size()!=n){now.clear();f(0,n-1,1);}if(now.size()!=n)printf("NO");else{printf("YES\n%d",now[0]);for(int i=1;i<n;i++)printf(" %d",now[i]);}
}

L2-005 集合相似度

给定两个整数集合，它们的相似度定义为：N
c

/N
t

×100%。其中N
c

是两个集合都有的不相等整数的个数，N
t

是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10
4
），是集合中元素的个数；然后跟M个[0,10
9
]区间内的整数。

之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出格式：
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例：
50.00%
33.33%

AC代码：

#include<bits/stdc++.h>
using namespace std;
set<int> s[55];
void fun(int x,int y)
{int ans=0;set<int>::iterator it;for(it=s[x].begin();it!=s[x].end();it++)if(s[y].find(*it)!=s[y].end())ans++;int temp=s[x].size()+s[y].size()-ans;printf("%.2lf%\n",ans*1.0/temp*100);
}
int main()
{int m,n;cin>>m;for(int i=1;i<=m;i++){int temp;cin>>temp;for(int j=0;j<temp;j++){int num;cin>>num;s[i].insert(num);}}cin>>n;for(int i=0;i<n;i++){int x,y;cin>>x>>y;fun(x,y);}
}

L2-006 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int in[N],post[N];
int n;
unordered_map<int,int>l,r,pos;
int build(int ia,int ib,int pa,int pb)
{int root=post[pb];int k=pos[root];if(ia<k)l[root]=build(ia,k-1,pa,pa+k-1-ia);if(ib>k)r[root]=build(k+1,ib,pa+k-ia,pb-1);return root;
}void bfs(int x)
{queue<int>q;vector<int>ans;q.push(x);while(!q.empty()){int t=q.front();ans.push_back(t);q.pop();if(l[t])q.push(l[t]);if(r[t])q.push(r[t]);}for(int i=0;i<ans.size();i++){cout<<ans[i];if(i!=ans.size()-1)cout<<" ";}
}int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>post[i];for(int i=1;i<=n;i++)cin>>in[i],pos[in[i]]=i;int root=build(1,n,1,n);bfs(root);}

L2-007 家庭房产

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：
输入第一行给出一个正整数N（≤1000），随后N行，每行按下列格式给出一个人的房产：

编号父母 k 孩子1 … 孩子k 房产套数总面积
其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0≤k≤5）是该人的子女的个数；孩子i是其子女的编号。

输出格式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号家庭人口数人均房产套数人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
输出样例：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

AC代码：

#include<bits/stdc++.h>
using namespace std;int p[10000];
int visit[10000];
int num[10000];
int area[10000];
vector<int> ans[10005];
struct node{int minId;int people;double num;double area;
} res[10000];int cmp1(node a, node b){if(a.area != b.area)return a.area > b.area;return a.minId < b.minId;
}void init(){for(int i = 0; i < 10000; i++){p[i] = i;res[i].minId = 999999;}
}int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];
}void Union(int x, int y){p[find(y)] = find(x);
}int main(){init();int n;cin >> n;for(int i = 0; i < n; i++){int id, f, m, k;cin >> id >> f >> m >> k;visit[id] = 1;if(f != -1){ Union(id, f);visit[f] = 1;}if(m != -1){visit[m] = 1;Union(id, m);}for(int j = 0; j < k; j++){int child;cin >> child;visit[child] = 1;Union(id, child);}cin >> num[id] >> area[id];}int cnt = 0;map<int, int> m;for(int i = 0; i < 10000; i++){if(visit[i] == 1){int x = find(i);if(ans[x].size() == 0){cnt++;m[x] = cnt;}ans[x].push_back(i);int id = m[x];res[id].area += area[i];res[id].num += num[i];res[id].minId = min(res[id].minId, i);res[id].people++;}}for (int i = 1; i <= cnt; i++) {res[i].num = res[i].num * 1.0 / res[i].people;res[i].area = res[i].area * 1.0 / res[i].people;}sort(res + 1, res + 1 + cnt, cmp1);cout << cnt << endl;for(int i = 1; i <= cnt; i++){printf("%04d %d %.3f %.3f\n", res[i].minId, res[i].people, res[i].num, res[i].area);}
}