国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

P1030 [NOIP2001 普及組] 求先序排列

2年前作者：熬夜寫代碼的小編分類：Toy博客閱讀(33)違法舉報

這篇具有很好參考價值的文章主要介紹了P1030 [NOIP2001 普及組] 求先序排列。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

題目描述

給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，且二叉樹的節(jié)點個數(shù)?≤8≤8）。

輸入格式

共兩行，均為大寫字母組成的字符串，表示一棵二叉樹的中序與后序排列。

輸出格式

共一行一個字符串，表示一棵二叉樹的先序。

輸入輸出樣例

輸入 #1復(fù)制

BADC
BDCA

輸出 #1復(fù)制

ABCD

說明/提示

【題目來源】

NOIP 2001 普及組第三題

首先，一點基本常識，給你一個后序遍歷，那么最后一個就是根（如ABCD，則根為D）。

因為題目求先序，意味著要不斷找根。

那么我們來看這道題方法：（示例）

中序ACGDBHZKX，后序CDGAHXKZB，首先可找到主根B；

那么我們找到中序遍歷中的B，由這種遍歷的性質(zhì)，可將中序遍歷分為ACGD和HZKX兩棵子樹，

那么對應(yīng)可找到后序遍歷CDGA和HXKZ（從頭找即可）

從而問題就變成求1.中序遍歷ACGD，后序遍歷CDGA的樹 2.中序遍歷HZKX，后序遍歷HXKZ的樹；

接著遞歸，按照原先方法，找到1.子根A，再分為兩棵子樹2.子根Z，再分為兩棵子樹。

就按這樣一直做下去（先輸出根，再遞歸）；

模板概括為step1:找到根并輸出

step2:將中序，后序各分為左右兩棵子樹；

step3:遞歸，重復(fù)step1,2；

代碼如下文章來源地址http://www.zghlxwxcb.cn/news/detail-421338.html

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
    if (in.size()>0){
        char ch=after[after.size()-1];
        cout<<ch;//找根輸出
        int k=in.find(ch);
        beford(in.substr(0,k),after.substr(0,k));
        beford(in.substr(k+1),after.substr(k,in.size()-k-1));//遞歸左右子樹；
    }
}
int main(){
    string inord,aftord;
    cin>>inord;cin>>aftord;//讀入
    beford(inord,aftord);cout<<endl;
    return 0;
}

到了這里，關(guān)于P1030 [NOIP2001 普及組] 求先序排列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

信息學(xué)奧賽一本通：1316：【例4.6】數(shù)的計數(shù)(Noip2001)
【題目描述】我們要求找出具有下列性質(zhì)數(shù)的個數(shù)（包括輸入的自然數(shù)nn）。先輸入一個自然數(shù)n(n≤1000)n(n≤1000)，然后對此自然數(shù)按照如下方法進行處理：不作任何處理；在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直
2024年02月10日
瀏覽(21)
P1024 [NOIP2001 提高組] 一元三次方程求解題解
題目有形如：這樣的一個一元三次方程。給出該方程中各項的系數(shù)（a,b,c,d均為實數(shù)），并約定該方程存在三個不同實根（根的范圍在?100至100之間），且根與根之差的絕對值≥1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后2位。提
2024年02月20日
瀏覽(19)
P1025 [NOIP2001 提高組] 數(shù)的劃分———C++(動態(tài)規(guī)劃、DFS)
將整數(shù) n n n 分成 k k k 份，且每份不能為空，任意兩個方案不相同（不考慮順序）。例如： n = 7 n=7 n = 7 ， k = 3 k=3 k = 3 ，下面三種分法被認為是相同的。 1 , 1 , 5 1,1,5 1 , 1 , 5 ; 1 , 5 , 1 1,5,1 1 , 5 , 1 ; 5 , 1 , 1 5,1,1 5 , 1 , 1 . 問有多少種不同的分法。 n , k n,k n , k （ 6 n ≤ 200 6n le
2024年01月22日
瀏覽(15)
P1025 [NOIP2001 提高組] 數(shù)的劃分（dfs+剪枝 or dp）
思路：暴力枚舉搜索，不過要優(yōu)雅剪枝一下下 1:處理重復(fù)情況--我們只需要然后方取值從前往后的時候呈現(xiàn)遞增（可以相等，即不遞減） 2：剪枝--基于上思想，剩下的“盤子”里面的數(shù)至少都大于等于當(dāng)前“盤子”的數(shù)，所以我們?nèi)⊥戤?dāng)前盤子的數(shù)完，就可判斷--剩下的盤子
2024年02月14日
瀏覽(43)
[NOIP2002 普及組] 選數(shù)#洛谷
已知 n n n 個整數(shù) x 1 , x 2 , ? ? , x n x_1,x_2,cdots,x_n x 1 ? , x 2 ? , ? , x n ? ，以及 1 1 1 個整數(shù) k k k （ k n kn k n ）。從 n n n 個整數(shù)中任選 k k k 個整數(shù)相加，可分別得到一系列的和。例如當(dāng) n = 4 n=4 n = 4 ， k = 3 k=3 k = 3 ， 4 4 4 個整數(shù)分別為 3 , 7 , 12 , 19 3,7,12,19 3 , 7 , 12 , 19 時，
2024年01月20日
瀏覽(22)
【洛谷 P1024】[NOIP2001 提高組] 一元三次方程求解題解（數(shù)學(xué)+二分答案）
有形如： a x 3 + b x 2 + c x + d = 0 a x^3 + b x^2 + c x + d = 0 a x 3 + b x 2 + c x + d = 0 這樣的一個一元三次方程。給出該方程中各項的系數(shù)（ a , b , c , d a,b,c,d a , b , c , d 均為實數(shù)），并約定該方程存在三個不同實根（根的范圍在 ? 100 -100 ? 100 至 100 100 100 之間），且根與根之差的絕對值
2024年02月06日
瀏覽(18)
一本通1919：【02NOIP普及組】選數(shù)
這道題感覺很好玩。先放題目：信息學(xué)奧賽一本通（C++版）在線評測系統(tǒng) (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.php?pid=1919 已知 n 個整數(shù) x1,x2,…,xn，以及一個整數(shù) k（k＜n）。從 n 個整數(shù)中任選 k 個整數(shù)相加，可分別得到一系列的和。例如當(dāng) n=4，k＝3，4 個整數(shù)分別為 3，7，
2024年02月16日
瀏覽(26)
[NOIP2007 普及組] 紀念品分組
元旦快到了，校學(xué)生會讓樂樂負責(zé)新年晚會的紀念品發(fā)放工作。為使得參加晚會的同學(xué)所獲得的紀念品價值相對均衡，他要把購來的紀念品根據(jù)價格進行分組，但每組最多只能包括兩件紀念品，并且每組紀念品的價格之和不能超過一個給定的整數(shù)。為了保證在盡量短的時間
2024年02月14日
瀏覽(25)
[NOIP2009 普及組] 分數(shù)線劃定#洛谷
世博會志愿者的選拔工作正在 A 市如火如荼的進行。為了選拔最合適的人才，A 市對所有報名的選手進行了筆試，筆試分數(shù)達到面試分數(shù)線的選手方可進入面試。面試分數(shù)線根據(jù)計劃錄取人數(shù)的 150 % 150% 150% 劃定，即如果計劃錄取 m m m 名志愿者，則面試分數(shù)線為排名第 m ×
2024年01月17日
瀏覽(24)
NOIP2013普及組復(fù)賽T4：車站分級
題目鏈接：洛谷P1983 [NOIP2013 普及組] 車站分級一條單向的鐵路線上，依次有編號為 1 , 2 , … , n 1, 2, …, n 1 , 2 , …
2024年02月08日
瀏覽(28)