[NOIP2004 普及組] FBI 樹 題目描述

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

站在用戶的角度思考問題，與客戶深入溝通，找到石泉網(wǎng)站設(shè)計與石泉網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：網(wǎng)站設(shè)計制作、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名注冊、虛擬主機、企業(yè)郵箱。業(yè)務(wù)覆蓋石泉地區(qū)。

FBI 樹是一種二叉樹，它的結(jié)點類型也包括 F 結(jié)點，B 結(jié)點和 I 結(jié)點三種。由一個長度為 2 N 2^N 2N 的 01 串 S S S 可以構(gòu)造出一棵 FBI 樹 T T T，遞歸的構(gòu)造方法如下：

1. T T T 的根結(jié)點為 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? 構(gòu)造 R R R 的左子樹 T 1 T_1 T1?，由右子串 S 2 S_2 S2? 構(gòu)造 R R R 的右子樹 T 2 T_2 T2?。

現(xiàn)在給定一個長度為 2 N 2^N 2N 的 01 串，請用上述構(gòu)造方法構(gòu)造出一棵 FBI 樹，并輸出它的后序遍歷序列。

輸入格式

第一行是一個整數(shù) 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% 的數(shù)據(jù)， N ≤ 2 N \le 2 N≤2；

對于全部的數(shù)據(jù)， N ≤ 10 N \le 10 N≤10。

noip2004普及組第3題

后序遍歷二叉樹，順序是，左右根。題意是，如果字符串長度大于1，就把字符串一分為二，前一半為左支樹，后一半為右支樹。輸出左右根的字符串。

每一個結(jié)點，都是判斷字符串長度，如果大于1就平分2段，先遞歸左支樹，再遞歸右支樹，然后再輸出這個結(jié)點的字符串。

#includeusing namespace std;
void judge(string ch)
{//	cout<return ;
	}else
	{		for(int i=0;i	if(ch[i+1]!=ch[i])
			{		cout<<"F";
				return ; 
			}
		}
		if(ch[0]=='0')
		{	cout<<"B";
			return ;
		}else if(ch[0]=='1')
		{	cout<<"I";
			return ;
		}
	}
}

void dg(string s)
{if(s.size()==1)
	{judge(s);
	}else
	{int n=s.size();
		string str1=s.substr(0,n/2);
		dg(str1);
		string str2=s.substr(n/2);
		dg(str2);
	    judge(s);
	}
}

int main()
{int n=0;
	cin>>n;
	long m=pow(2,n);
	
	string s="";
	cin>>s;
	dg(s);
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標題：FBI樹【普及-】-創(chuàng)新互聯(lián)
本文路徑：http://aaarwkj.com/article48/dpghep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、虛擬主機、搜索引擎優(yōu)化、營銷型網(wǎng)站建設(shè)、App開發(fā)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)