P1087 [NOIP2004 普及组] FBI 树

大家好！下面为大家讲解我做了两年半的题目，

[NOIP2004 普及组] FBI 树

题目描述

我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。

FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2 N 2^N 2N 的 01 串 S S S 可以构造出一棵 FBI 树 T T T，递归的构造方法如下：

1. T T T 的根结点为 R R R，其类型与串 S S S 的类型相同；
2. 若串 S S S 的长度大于 1 1 1，将串 S S S 从中间分开，分为等长的左右子串 S 1 S_1 S1​ 和 S 2 S_2 S2​；由左子串 S 1 S_1 S1​ 构造 R R R 的左子树 T 1 T_1 T1​，由右子串 S 2 S_2 S2​ 构造 R R R 的右子树 T 2 T_2 T2​。

现在给定一个长度为 2 N 2^N 2N 的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

输入格式

第一行是一个整数 N ( 0 ≤ N ≤ 10 ) N(0 \le N \le 10) N(0≤N≤10)，

第二行是一个长度为 2 N 2^N 2N 的 01 串。

输出格式

一个字符串，即 FBI 树的后序遍历序列。

样例 #1

样例输入 #1

3
10001011

样例输出 #1

IBFBBBFIBFIIIFF

提示

对于 40 % 40\% 40% 的数据， N ≤ 2 N \le 2 N≤2；

对于全部的数据， N ≤ 10 N \le 10 N≤10。

noip2004普及组第3题


反正题目就是这么说的，一开始还没看懂，用人话来说就是把10001011，分成1000，1011，然后把1000，1011分成10，00，10，11，再然后就把10,00,10,11分成1,0,0,0,1,0,1,1.然后用树来表示就是这样：

实现这个的代码十分简单难，长这样：

tree[1].data=s;
	queue<xd> q;
	q.push((xd){1,s});
	while(1) {
		o=q.front();
		q.pop();
		if(o.f.size()==1) {
			break;
		}
		string e,w;
		for(int i=0;i<o.f.size()/2;i++) {
			e.push_back(o.f[i]);
		}
		q.push((xd){o.ty*2,e});
		tree[o.ty*2].data=e;
		for(int i=o.f.size()/2;i<o.f.size();i++) {
			w.push_back(o.f[i]);
		}
		q.push((xd){o.ty*2+1,w});
		tree[o.ty*2+1].data=w;
	}

这运用了一个数据结构——队列，用人话叫先进先出的数据结构

char pd(string h) {
	int ans=0,ans1=0;
	for(int i=0;i<h.size();i++) {
		if(h[i]=='1') ans++;
		if(h[i]=='0') ans1++;
		if(ans>0&&ans1>0) return 'F';
	}
	if(ans>0) return 'I';
	else return 'B';
}
void dfs(int x) {
	if(tree[x].data.size()==0) {
		return ;
	}
	dfs(x*2);
	dfs(x*2+1);
	cout<<pd(tree[x].data);
}

这运用了一个数据结构——树，加上一个判断条件，判断是F or B or I.

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n;
string s;
struct node {
	string data;
}tree[100000];
struct xd {
	int ty;
	string f;
}o;
char pd(string h) {
	int ans=0,ans1=0;
	for(int i=0;i<h.size();i++) {
		if(h[i]=='1') ans++;
		if(h[i]=='0') ans1++;
		if(ans>0&&ans1>0) return 'F';
	}
	if(ans>0) return 'I';
	else return 'B';
}
void dfs(int x) {
	if(tree[x].data.size()==0) {
		return ;
	}
	dfs(x*2);
	dfs(x*2+1);
	cout<<pd(tree[x].data);
}
signed main() {
	cin>>n>>s;
	tree[1].data=s;
	queue<xd> q;
	q.push((xd){1,s});
	while(1) {
		o=q.front();
		q.pop();
		if(o.f.size()==1) {
			break;
		}
		string e,w;
		for(int i=0;i<o.f.size()/2;i++) {
			e.push_back(o.f[i]);
		}
		q.push((xd){o.ty*2,e});
		tree[o.ty*2].data=e;
		for(int i=o.f.size()/2;i<o.f.size();i++) {
			w.push_back(o.f[i]);
		}
		q.push((xd){o.ty*2+1,w});
		tree[o.ty*2+1].data=w;
	}
	dfs(1);
} 

华丽结束