题解：P1087 [NOIP2004 普及组] FBI 树

2025-01-22

未分类

2.3k 词

I. 读

1. 全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串

2. T 的根结点为 R，其类型与串 S(输入内容) 的类型相同；
3. 若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S_1 和 S_2；由左子串 S_1 构造 R 的左子树 T_1，由右子串 S_2 构造 R 的右子树 T_2

4. 请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列

啧，2. …… 和 3. …… 有点难理解，请求中译中！

2. …… T 是个树，根节点是 S ；

3. …… 如果树 T 里有节点的长度大于 1 就把那个节点的左孩子设为自己的左半，右孩子设为自已的右半

FBI树图示：

![FBI树](https://img520.com/odPGRq.png =565x250)

II. 写

1 框架

1 2	int n; // 输入的长度2^N中的N string fbi; // 输入的串

输入选择 string ，方便后续分半

因为我们需要重复进行分树等操作，题目中也提示了递归，所以我们使用神奇の递归作为操作方式

框架：

#include <bits/stdc++.h>
using namespace std;

int FBI( ? )
{
	?
}

int main()
{
	cin >> n >> fbi;
	FBI( ? );
	
	return 0;
}

2 程序

为方便，先把 n 改为实际长度再执行 FBI 函数

n = 1 << n;

FBI函数里拢共分三步 ↑

![说明](https://img520.com/TrFogf.png =95x175)

① 函数框架

因为需要分，所以需要一个起点 l 和终点 r 用来分 fbi (输入)

故函数定义写为

int FBI(int l, int r)
{
	?
}

主函数内调用也要写为
FBI(0, n - 1);
而 0 和 n - 1 就是 S 的起始和终止下标

② 如果长度为 1 ？

如果长度为 1 就可以直接判断是 I 还是 B ，如果为 1 就是 I，返回 0 ；如果是 0 就是 B，返回 0

③ 分树递归 + 判断

要将 S 分为两半，就需要三个下标，分别是第一个起始 l ，第一个终止（+1就是第二个起始） mid ，第二个终止 r ，而这些恰巧可以用到 FBI 函数上，而 FBI 函数的返回值就代表了被分出来的两个子节点的 FBI 属性，我们就可以用两个变量将其存下以用来判断当前的节点的 FBI 属性

1
2
3

int mid = l + (r - l) / 2; // 父节点
int flagl = FBI(l, mid);     // 结果是l ~ mid子串的FBI串
int flagr = FBI(mid + 1, r); // 结果是mid+1 ~ r子串的FBI串

而得之了两个子节点的 FBI 属性后就可以得出当前节点的 FBI 属性，只需要几个 if 就可以

if (flagl  1 and flagr  1) // 如果分出来的两个都是I（全1），则这个也是I
	{
		cout << "I";
		return 1;
	}
	else if (flagl or flagr) // 分出来的两个中只要有一个是I（全1）或F（有0有1），这个就是F
	{
		cout << "F";
		return 2;
	}
	else // FI全不是，就是B
	{
		cout << "B";
		return 0;
	}

III. 示例

根据上述思路一步步写出就得到了：

AC代码！

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n;
string fbi;

int FBI(int l, int r) // 后序遍历输出，l和r分别是左子和右子
{
	if (l  r) // 如果l和r指向同一个地方，说明这里只有一个数，所以不是B就是I 
	{
		if (fbi[l]  '0') // 如果是0
		{
			cout << "B";
			return 0; // 即全0
		}
		else // 如果是1
		{
			cout << "I";
			return 1; // 即全1
		}
	}
	
	int mid = l + (r - l) / 2; // 父节点
	
	// 分：
	int flagl = FBI(l, mid);     // 结果是l ~ mid子串的FBI串
	int flagr = FBI(mid + 1, r); // 结果是mid+1 ~ r子串的FBI串
	
	if (flagl  1 and flagr  1) // 如果分出来的两个都是I（全1），则这个也是I
	{
		cout << "I";
		return 1;
	}
	else if (flagl or flagr) // 分出来的两个中只要有一个是I（全1）或F（有0有1），这个就是F
	{
		cout << "F";
		return 2;
	}
	else // FI全不是，就是B
	{
		cout << "B";
		return 0;
	}
}

int main()
{
	cin >> n >> fbi;
	n = 1 << n;
	FBI(0, n - 1);
	
	return 0;
}

标签