16哈理工新生赛 G FBI Tree （模拟二叉树后序遍历）

迷南。 2022-07-14 10:09 63阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>题目链接：<a href="http://acm.hrbust.edu.cn/index.php?m=ProblemSet&amp;a=showProblem&amp;problem_id=2299" rel="nofollow">点击打开链接</a> FBI Tree</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 58(41 users)</td> 
 <td>Total Accepted: 47(41 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td> FBI Tree的描述如下： 我们可以把由0和1组成的字符串分为3类，全0的串成为B串，全1的串成为I串，既含0又含1的串则称为F串。FBI树是一种二叉树，它的节点类型也包括F串节点、B串节点和I串节点三种。由一个长度为2^N的01串S可以构造出一颗FBI树T,递归的构造方法如下： （1）&nbsp;&nbsp;T的根节点为R，其类型与串S的类型相同。 （2）&nbsp;&nbsp;若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给出一个长度为2^N的01串，请用上述构造方法构造出一棵FBI树，并输出它的后续遍历序列。 </td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td> 第一行为一个正整数T，表示测试数据组数。 每组测试数据第一行为一个整数N（0 &lt;= N &lt;= 10），第二行是一个长度为2^N的01串。 </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td> 输出FBI树的后续遍历序列。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td> 2 1 10 3 10001011 </td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td> IBF IBFBBBFIBFIIIFF </td> 
 </tr> 
 <tr> 
 <td>Source</td> 
 </tr> 
 <tr> 
 <td>2016级新生程序设计全国邀请赛</td> 
 </tr> 
 </tbody> 
</table>

题解：模拟一下题意。自己建一棵二叉树，然后后序遍历一下就可以啦。

AC代码：

//#include<bits/stdc++.h>
 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 using namespace std;
 int tree[1<<16];
 char s[1000];
 int n;
 #define mid ((l+r)>>1)
 void pushup(int rt)
 {
 	if(tree[rt<<1]==2 || tree[rt<<1|1]==2) tree[rt]=2;
 	else if(tree[rt<<1]==0&&tree[rt<<1|1]==0) tree[rt]=0;
 	else if(tree[rt<<1]==1&&tree[rt<<1|1]==0) tree[rt]=2;
 	else if(tree[rt<<1]==0&&tree[rt<<1|1]==1) tree[rt]=2;
 	else if(tree[rt<<1]==1&&tree[rt<<1|1]==1) tree[rt]=1;
 	
 }
 void build(int rt,int l,int r)
 {
 	if(r==l)
 	{
 		tree[rt]=s[l]-'0';
 		return ;
 	}
 	
 	build(rt<<1,l,mid);
 	build(rt<<1|1,mid+1,r);
 	pushup(rt);
 }
 int ans;
 void print(int rt)
 {
 	ans++;
 	if(ans >= ( 1<<(n+1)) ) return ;
 	if(tree[rt]==0) cout<<"B";
 	else if(tree[rt]==1) cout<<"I";
 	else if(tree[rt]==2) cout<<"F";
 }
 void dfs(int rt,int l,int r)
 {
 	
 	if(l==r);
 	else
 	{
 		dfs(rt<<1, l, mid);
 		dfs(rt<<1|1, mid+1, r);
 	}
 	print(rt);
 	return ;
 }
 int main()
 {
 int t;
 scanf("%d",&t);
 while(t--)
 { 
 	ans=0;
 	scanf("%d",&n);
 scanf("%s",s+1);
 build(1, 1,(1<<(n+1))-1);
 		dfs(1, 1, (1<<(n+1))-1); 
 puts("");
 	}
 return 0;
 }