土特产网站模板,彩票网站建设服务,wordpress 列表页面,重庆建设工程质量信息网本文由Jzwalliser原创#xff0c;发布在CSDN平台上#xff0c;遵循CC 4.0 BY-SA协议。 因此#xff0c;若需转载/引用本文#xff0c;请注明作者并附原文链接#xff0c;且禁止删除/修改本段文字。 违者必究#xff0c;谢谢配合。 个人主页#xff1a;blog.csdn.net/jzw… 本文由Jzwalliser原创发布在CSDN平台上遵循CC 4.0 BY-SA协议。 因此若需转载/引用本文请注明作者并附原文链接且禁止删除/修改本段文字。 违者必究谢谢配合。 个人主页blog.csdn.net/jzwalliser 题目
洛谷 P1087 [NOIP2004 普及组] FBI 树 [NOIP2004 普及组] FBI 树 题目描述 我们可以把由 0 和 1 组成的字符串分为三类全 0 串称为 B 串全 1 串称为 I 串既含 0 又含 1 的串则称为 F 串。 FBI 树是一种二叉树它的结点类型也包括 F 结点B 结点和 I 结点三种。由一个长度为 2 N 2^N 2N 的 01 串 S S S 可以构造出一棵 FBI 树 T T T递归的构造方法如下 T T T 的根结点为 R R R其类型与串 S S S 的类型相同若串 S S S 的长度大于 1 1 1将串 S S S 从中间分开分为等长的左右子串 S 1 S_1 S1 和 S 2 S_2 S2由左子串 S 1 S_1 S1 构造 R R R 的左子树 T 1 T_1 T1由右子串 S 2 S_2 S2 构造 R R R 的右子树 T 2 T_2 T2。 现在给定一个长度为 2 N 2^N 2N 的 01 串请用上述构造方法构造出一棵 FBI 树并输出它的后序遍历序列。 输入格式 第一行是一个整数 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% 的数据 N ≤ 2 N \le 2 N≤2 对于全部的数据 N ≤ 10 N \le 10 N≤10。 noip2004普及组第3题 想法
题目大意就是把一个字符串不停地分割成等长的两半然后建立二叉树对其进行后序遍历。来解读一下样例。 根据输入我们可以获得这样的二叉树 #mermaid-svg-36pJ4ahTGpLIJXRD {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .error-icon{fill:#552222;}#mermaid-svg-36pJ4ahTGpLIJXRD .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-36pJ4ahTGpLIJXRD .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-36pJ4ahTGpLIJXRD .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-36pJ4ahTGpLIJXRD .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-36pJ4ahTGpLIJXRD .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-36pJ4ahTGpLIJXRD .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-36pJ4ahTGpLIJXRD .marker{fill:#333333;stroke:#333333;}#mermaid-svg-36pJ4ahTGpLIJXRD .marker.cross{stroke:#333333;}#mermaid-svg-36pJ4ahTGpLIJXRD svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-36pJ4ahTGpLIJXRD .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .cluster-label text{fill:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .cluster-label span{color:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .label text,#mermaid-svg-36pJ4ahTGpLIJXRD span{fill:#333;color:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .node rect,#mermaid-svg-36pJ4ahTGpLIJXRD .node circle,#mermaid-svg-36pJ4ahTGpLIJXRD .node ellipse,#mermaid-svg-36pJ4ahTGpLIJXRD .node polygon,#mermaid-svg-36pJ4ahTGpLIJXRD .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-36pJ4ahTGpLIJXRD .node .label{text-align:center;}#mermaid-svg-36pJ4ahTGpLIJXRD .node.clickable{cursor:pointer;}#mermaid-svg-36pJ4ahTGpLIJXRD .arrowheadPath{fill:#333333;}#mermaid-svg-36pJ4ahTGpLIJXRD .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-36pJ4ahTGpLIJXRD .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-36pJ4ahTGpLIJXRD .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-36pJ4ahTGpLIJXRD .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-36pJ4ahTGpLIJXRD .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-36pJ4ahTGpLIJXRD .cluster text{fill:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD .cluster span{color:#333;}#mermaid-svg-36pJ4ahTGpLIJXRD div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-36pJ4ahTGpLIJXRD :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 10001011 F 1000 F 1011 F 10 F 00 B 10 F 11 I 1 I 0 B 0 B 0 B 1 I 0 B 1 I 1 I 那么后序遍历输出就是IBFBBBFIBFIIIFF。 不过写程序的时候不需要刻意地、人为地去建立、维护一个二叉树只需要一个递归函数并按照一定的顺序输出就可以达到效果。
实现
把字符串切成等长的两段分别递归。判断字符串类型。如果当前的字符串只有一个字符那就return。由于是后序遍历所以在两次递归操作完成后再输出。
题解
C
#includeiostream
using namespace std;
string fbi(string str){ //递归建树if(str.size() 1){ //字符串只有一个字符了if(str 1){ //I串cout I;return I;}else{ //B串cout B;return B;}}else{ //字符串不止一个字符string a fbi(str.substr(0,str.size() / 2)); //处理字符串前半部分string b fbi(str.substr(str.size() / 2,str.size() / 2)); //处理字符串后半部分string ftype a b;if(ftype II){ //如果两个子串都是I串cout I; //那么这个字符串也是I串return I;}else if(ftype BB){ //如果两个子串都是B串cout B; //那么这个字符串也是B串return B;}else{ //否则这个字符串就是F串cout F;return F;}}
}int main(){int length; //长度string str; //字符串cin length str; //输入fbi(str); //递归return 0;
}Python
ans
length input() #获取长度
string input()[0:2 ** int(length)] #不知道为什么Python不截取字符串会WA所以这里还是操作一下
def fbi(string): #递归建树global ans #将答案存放到ans里面if len(string) 1: #字符串只有一个字符了if string 1: #I串ans Ireturn Ielse: #B串ans Breturn Belse: #字符串不止一个字符a fbi(string[0:int(len(string) / 2)]) #处理字符串前半部分b fbi(string[int(len(string) / 2):]) #处理字符串后半部分ftype a bif ftype II: #如果两个子串都是I串ans I #那么这个字符串也是I串return Ielif ftype BB: #如果两个子串都是B串ans B #那么这个字符串也是B串return Belse: #否则这个字符串就是F串ans Freturn F
fbi(string) #递归
print(ans)难度
难度★☆☆☆☆ 这道题其实还好主要是题目有点难读。需要认真理解才能看懂。之后的操作应该都比较简单吧递归输出。
结尾
你是怎么想的欢迎留言我们下期再见(˵¯͒〰¯͒˵)
