题解：P1087 [NOIP 2004 普及组] FBI 树

这题理论上来说是考二叉树的，但是呢，当时我做这道题的时候刚刚学完线段树，于是......

小知识：线段树的递归建树过程就是一个后序遍历，所以我们可以直接用线段树的建树函数改造得到这道题的答案。

具体的，我们将整个串输入，之后像线段树递归那样，在这个

01

串上建树，建好之后，按照题意合并两个子节点的对应串：

对于叶子节点，若是 $0$ 就为 $B$ 串，反之为 $I$ 串。
$B+B=B,I+I=I,B+I=F,I+B=F,F+(B/I/F)=F$

按照上面的小知识，当求出每一个节点对应的类型时，直接输出，最终得到的就是答案。

上代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=10050;
char sgt[N]={0};
void build(int tt,string s)
{
	if(s.size()==1)
	{
		if(s[0]=='0')sgt[tt]='B';
		else sgt[tt]='I';
		cout<<sgt[tt];
		return ;
	}
	int mid=s.size()/2;
	build(tt*2,s.substr(0,mid));
	build(tt*2+1,s.substr(mid,mid));
	if(sgt[tt*2]=='I'&&sgt[tt*2+1]=='I')sgt[tt]='I';
	else if(sgt[tt*2]=='B'&&sgt[tt*2+1]=='B')sgt[tt]='B';
	else sgt[tt]='F';
	cout<<sgt[tt];
	return ;
}
int main()
{
	int n;
	string s;
	cin>>n;
	cin>>s;
	build(1,s);
	return 0;
}

题解：P1087 [NOIP 2004 普及组] FBI 树

文章操作

相关推荐

评论

题解：P1087 [NOIP 2004 普及组] FBI 树