【NOIP2004PJ】FBI樹

目錄

• 前言
• 題目概述
• 輸入
• 輸出
• 樣例輸入
• 樣例輸出
• 思路
• 代碼

前言

光陰似箭，日月如梭。大家好，我盛藝承又雙叒叕回來了！今天給大家講一講NOIP2004的題目，花生采摘。

題目概述

我們可以把由“0”和“1”組成的字元串分為三類：全“0”串稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。

FBI樹是一種二叉樹[1]，它的結點類型也包括F結點，B結點和I結點三種。由一個長度為2N的“01”串S可以構造出一棵FBI樹T，遞歸的構造方法如下：

(1)T的根結點為R，其類型與串S的類型相同；

(2)若串S的長度大于1，将串S從中間分開，分為等長的左右子串S1和S2；由左子串S1構造R的左子樹T1，由右子串S2構造R的右子樹T2。

現在給定一個長度為2N的“01”串，請用上述構造方法構造出一棵FBI樹，并輸出它的後序周遊[2]序列。

[1] 二叉樹：二叉樹是結點的有限集合，這個集合或為空集，或由一個根結點和兩棵不相交的二叉樹組成。這兩棵不相交的二叉樹分别稱為這個根結點的左子樹和右子樹。

[2] 後序周遊：後序周遊是深度優先周遊二叉樹的一種方法，它的遞歸定義是：先後序周遊左子樹，再後序周遊右子樹，最後通路根。

輸入

輸入檔案fbi.in的第一行是一個整數N（0 <= N <= 10），第二行是一個長度為2N的“01”串。

輸出

輸出檔案fbi.out包括一行，這一行隻包含一個字元串，即FBI樹的後序周遊序列。

樣例輸入

3

10001011

樣例輸出

IBFBBBFIBFIIIFF

思路

這一題也和花生采摘一樣，也是一道水沝淼㵘題啊！花生采摘詳情點這：花生采摘隻需要用一個dg就能夠輕松解決了。

代碼

#include<bits/stdc++.h>
using namespace std;
int n,i;
string s;
char dfs(int x,int y){
	if(x==n+1){
		cout<<s[y-1];
		return s[y-1];
	}
	char bl1=dfs(x+1,2*y-1),bl2=dfs(x+1,2*y);
	if(bl1==bl2){
		cout<<bl1;
		return bl1;
	}else{
		cout<<'F';
		return 'F';
	}
}
int main(){
	cin>>n;
	cin>>s;
	for(i=0;i<s.size();i++){
		if(s[i]=='0') s[i]='B';
		if(s[i]=='1') s[i]='I';
	}
	dfs(1,1);
}
           

這一題是不是非常非常非常非常非常非常非常非常的水沝淼㵘呢

記得要點贊呀！o(￣▽￣)ｄ

火箭工作室QQ号：2558249307。