【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】搞懂了赛场上拿下就稳
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-001 - L2-024）搞懂了赛场上拿下就稳了
【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-025 - L2-048）搞懂了赛场上拿下这些分就稳了
L2-005 集合相似度 STL
给定两个整数集合，它们的相似度定义为：Nc/Nt×100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。
之后一行给出一个正整数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%
分析：
最多50个集合，预处理出全部的组合，C50 2=49∗25, 用set存放所有的集合，然后预处理的时候遍历两个set中较小的那个，在较大的中查找是否存在，将集合i和集合j共同拥有的数量存在both[i][j]中。Nc就是both[i][j]，Nt就是两个集合size加起来再减掉both[i][j]。时间复杂度：25∗49∗10000∗log(10000)=49000000。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
set<int> s[55];
int main(){
int n; cin>>n;
int i,j,m,x;
for(i=0;i<n;i++){
cin>>m;
for(j=0;j<m;j++){
cin>>x;
s[i].insert(x);
}
}
int q; cin>>q;
for(i=0;i<q;i++){
int x,y;
cin>>x>>y;
x--,y--;
int num1=0,num2=s[x].size()+s[y].size();
for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++){
if(s[y].count(*i)!=0) num1++; //注意指针运算符
// cout<<*i<<endl;
}
printf("%.2lf%\n",num1*100.0/(num2-num1));
}
return 0;
}
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
分析：
知道中序+后序或者前序，就能确定一棵唯一的二叉树。所以此题知道后序+中序，可以建立二叉树后层序遍历。由于后序是左右根，所以最后面的节点就是根，然后在中序中找到这个根的位置，左边就是左子树的范围，右边就是右子树的范围，递归处理即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct node{
node *lson,*rson;
int val;
};
typedef node* Tree;
vector<int> Mid_order, Post_order;
int n,x,i,now;
Tree build(int l,int r){ //中序和后序建树
if(l>r) return NULL;
Tree root = new(node);
root -> val = Post_order[now];
int mid = l;
while(Post_order[now] != Mid_order[mid])mid++;
now--;
root -> rson = build(mid+1,r);
root -> lson = build(l,mid-1);
return root;
}
void print(Tree root){ //层序遍历输出
queue<Tree> q;
q.push(root);
int tot = 0;
while(!q.empty()){
Tree t = q.front();
if(t->lson != NULL)q.push(t->lson);
if(t->rson != NULL)q.push(t->rson);
printf("%d",t->val);
q.pop();
tot++;
if(tot<n)cout<<' ';
else cout<<endl;
}
}
int main(){
cin>>n;
for(i = 0 ; i < n ; i ++)
cin>>x,Post_order.push_back(x);
for(i = 0 ; i < n ; i ++)
cin>>x,Mid_order.push_back(x);
now = n - 1;
print(build(0,n-1));
return 0;
}