H: CBT?

時(shí)間限制: 1 s ? ? ?內(nèi)存限制: 128 MB ? ? ?提交 我的狀態(tài)

題目描述

對(duì)于二叉樹，如果這棵樹的節(jié)點(diǎn)排布是按行從上到下，每行從左到右挨個(gè)放置，中間不會(huì)有空閑的節(jié)點(diǎn)。則我們稱之為完全二叉樹。

注：這棵樹的根節(jié)點(diǎn)的值一定是1

輸入

輸入數(shù)字正整數(shù)n (1≤n≤201≤n≤20)

接下來(lái)n行，每行為兩個(gè)數(shù)字(a,b)和一個(gè)字符c(L 或者 R)，如果字符c是L，則表示b是a的左子節(jié)點(diǎn)；如果字符c是R，則表示b是a的右子節(jié)點(diǎn)。 (1≤a,b≤30001≤a,b≤3000)

輸出

判斷這棵樹是否為完全二叉樹，如果是則輸出Yes，否則輸出No

樣例輸入

5

1 2 L

1 3 R

2 4 L

2 5 R

3 6 L

樣例輸出

Yes

分析：建立一個(gè)類型P(u,k),u為該點(diǎn)的值，k用于選擇該點(diǎn)的左右子結(jié)點(diǎn)；用map儲(chǔ)存u點(diǎn)子節(jié)點(diǎn)的值，用隊(duì)列實(shí)現(xiàn)從根節(jié)點(diǎn)開始往下再往右遍歷的過(guò)程；通過(guò)改變k的值實(shí)現(xiàn)同一結(jié)點(diǎn)從左兒子到右兒子遍歷的過(guò)程，左或右兒子不存在則退出循環(huán)，若通過(guò)遍歷的結(jié)點(diǎn)數(shù)量驗(yàn)證是否為完全二叉樹；

#include

#include

#include

#include

#include

using namespace std;

typedef pairM;//用于選擇左節(jié)點(diǎn)和右結(jié)點(diǎn)

int x[3033];

bool vis[3033];//用于尋找根節(jié)點(diǎn)

mapp;//用于尋找子節(jié)點(diǎn)

queueq;//用于遍歷樹

int main()

{

int n,y;

char c;

scanf("%d",&n);

M tmp;

for(int i=0;i

scanf("%d%d",&x[i],&y);

cin>>c;

tmp.first=x[i],tmp.second=c;

p[tmp]=y;

vis[y]=1;

}

for(int i=1;i<=n;i++)

if(!vis[x[i]]){

q.push(x[i]);break;//插入根節(jié)點(diǎn)

}

int cnt=0;

while(!q.empty()){

tmp.first=q.front();

q.pop();

tmp.second='L';

if(p.find(tmp)!=p.end()){

q.push(p[tmp]);//插入tmp的左兒子

cnt++;

}else{

break;

}

tmp.second='R';

if(p.find(tmp)!=p.end()){

q.push(p[tmp]);//插入tmp的左兒子

cnt++;

}else{

break;

}

}

cnt==n?printf("Yes\n"):printf("No\n");

return 0;

}

Just oj 2018 C語(yǔ)言程序設(shè)計(jì)競(jìng)賽(高級(jí)組)D&colon; 四邊形面積

D: 四邊形面積 時(shí)間限制: 1 s ? ? ?內(nèi)存限制: 128 MB ? ? ?提交 我的狀態(tài) 題目描述 有一個(gè)四邊形,現(xiàn)在需要求它的面積 輸入 輸入四行,每行兩個(gè)數(shù)整數(shù)xx, yy (1≤x,y ...

Just oj 2018 C語(yǔ)言程序設(shè)計(jì)競(jìng)賽(高級(jí)組)F&colon;Star(結(jié)構(gòu)體排序&plus;最小生成樹)

F: Star Time Limit:?1 s ?????Memory Limit:?128 MB Submit?My Status Problem Description 31世紀(jì),人類世界的科技已 ...

2018年江西理工大學(xué)C語(yǔ)言程序設(shè)計(jì)競(jìng)賽&lpar;高級(jí)組&rpar;&Tab; &Tab;三角平方數(shù)

題目描述 三角數(shù):形如圖a,圓點(diǎn)擺放成等邊三角形的數(shù)字,則為三角數(shù). (圖a) 平方數(shù):形如圖b,小方塊擺放成正方形的數(shù)字,則為平方數(shù). (圖b) 那么如果一個(gè)數(shù)字既是三角形數(shù)又是平方數(shù),則稱為三角平 ...

Just Oj 2017C語(yǔ)言程序設(shè)計(jì)競(jìng)賽高級(jí)組A&colon; 求近似值&lpar;矩陣快速冪)

A: 求近似值 時(shí)間限制:?1 s ?????內(nèi)存限制:?128 MB 提交?我的狀態(tài) 題目描述 求?(5–√+6–√)2n??(5+6)2n?%9932017. 例如:n=1,(5–√+6–√)2( ...

Just Oj 2017C語(yǔ)言程序設(shè)計(jì)競(jìng)賽高級(jí)組E&colon; DATE ALIVE(二分匹配)

E: DATE ALIVE 時(shí)間限制:?1 s ?????內(nèi)存限制:?128 MB 提交?我的狀態(tài) 題目描述 五河士道家里的精靈越來(lái)越多了,而每一個(gè)精靈都想和他有一個(gè)約會(huì).然而五河士道卻只有一個(gè),無(wú)奈 ...

Just Oj 2017C語(yǔ)言程序設(shè)計(jì)競(jìng)賽高級(jí)組D&colon; 字符串最大表示(next數(shù)組)

D: 字符串最大表示 時(shí)間限制:?1 s ?????內(nèi)存限制:?128 MB 題目描述 有如下定義,abcnabcn表示字符串a(chǎn)bc重復(fù)n次,例如abc2abc2表示abcabc. 給定一個(gè)字符串,求 ...

2018年江西理工大學(xué)C語(yǔ)言程序設(shè)計(jì)競(jìng)賽高級(jí)組部分題解

B Interesting paths 考察范圍:組合數(shù)學(xué) 此題是機(jī)器人走方格的變種,n*m的網(wǎng)格,從(1,1)走到(n,m),首先可以明確,水平要走m-1格,豎直要走n-1格,則走到目的地的任意一條 ...

2014江西理工大學(xué)C語(yǔ)言程序設(shè)計(jì)競(jìng)賽高級(jí)組題解

1001?Beautiful Palindrome Number 枚舉回文數(shù)字前半部分,然后判斷該數(shù)字是否滿足,復(fù)雜度為O(sqrt(n))! 1002?Recovery Sequence? 本題的核 ...

2017年江西理工大學(xué)C語(yǔ)言程序設(shè)計(jì)競(jìng)賽&lpar;高級(jí)組&rpar;

問(wèn)題 A: 求近似值 #include #include #include using namespac ...

隨機(jī)推薦

linux 的iptables防火墻

.a文件就是*.o文件的集合, 是object文件的歸檔文件, 所以, 用nm -A? ???.a看到的 symbolic符合名稱都是 相應(yīng)的,? 包含的? .o文件.... linux 2.4內(nèi)核中 ...

Ehcache&lpar;2&period;9&period;x&rpar; - API Developer Guide&comma; Cache Exception Handlers

About Exception Handlers By default, most cache operations will propagate a runtime CacheException o ...

Spring&plus;SpringMVC&plus;MyBatis深入學(xué)習(xí)及搭建&lpar;十二&rpar;——SpringMVC入門程序

轉(zhuǎn)載請(qǐng)注明出處:http://www.cnblogs.com/Joanna-Yan/p/6999743.html 前面講到:Spring+SpringMVC+MyBatis深入學(xué)習(xí)及搭建(十一)--S ...

Windows下基于ADS&plus;J-Link 的ARM開發(fā)環(huán)境搭建

在一般ARM編程教學(xué)和實(shí)驗(yàn)環(huán)境里,一般采用 ADS加+并口轉(zhuǎn)Jtag板+H-Jtag的開發(fā)環(huán)境.但是這種方法最大缺點(diǎn)是需要機(jī)器上有一個(gè)并口.現(xiàn)在無(wú)論P(yáng)C還是筆記本都很難有并口,因此采用USB接口調(diào)試器 ...

Hive 導(dǎo)入 parquet 格式數(shù)據(jù)

Hive 導(dǎo)入 parquet 數(shù)據(jù)步驟如下: 查看 parquet 文件的格式 構(gòu)造建表語(yǔ)句 倒入數(shù)據(jù) 一.查看 parquet 內(nèi)容和結(jié)構(gòu) 下載地址 社區(qū)工具 GitHub 地址 命令 查看結(jié)構(gòu): ...

c&sol;c&plus;&plus; 重載運(yùn)算符 關(guān)系，下標(biāo)，遞增減，成員訪問(wèn)的重載

重載運(yùn)算符 關(guān)系,下標(biāo),遞增減,成員訪問(wèn)的重載 為了演示關(guān)系,下標(biāo),遞增減,成員訪問(wèn)的重載,創(chuàng)建了下面2個(gè)類. 1,類StrBlob重載了關(guān)系,下標(biāo)運(yùn)算符 2,類StrBlobPtr重載了遞增,抵減, ...

和初學(xué)者交流學(xué)習(xí)java語(yǔ)言一些體會(huì)。

對(duì)初學(xué)者,自己學(xué)習(xí)java語(yǔ)言的一些體會(huì): 1.工欲善其事,必先利其器.先把Java學(xué)習(xí)工具準(zhǔn)備好,包括集成開發(fā)環(huán)境IDE,自己覺(jué)得MyEclipse比較適合,還有數(shù)據(jù)庫(kù),Oracle或MySQL,S ...

接口工具之postman

在我們?nèi)粘ｉ_發(fā)中,經(jīng)常會(huì)對(duì)功能接口進(jìn)行相應(yīng)的測(cè)試.那么postman是一款不錯(cuò)的測(cè)試工具,因?yàn)槠匠Ｊ褂玫谋容^多,因此在這里簡(jiǎn)單記錄一下,經(jīng)常使用到的一些地方 簡(jiǎn)單的使用就不錯(cuò)介紹了, 基本流程: 新建 ...

總結(jié)

以上是生活随笔為你收集整理的c语言oj竞选投票,Just oj 2018 C语言程序设计竞赛（高级组）H: CBT?的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。