首页 > ACM题库 > 九度OJ > 九度-1113-二叉树[解题代码]
2013
12-12

九度-1113-二叉树[解题代码]

题目来源:2007年北京大学计算机研究生机试真题

题目描述:

<[if !mso]>

<[if gte mso 9]>

Normal
0
false


7.8 磅
0
2

false
false
false

EN-US
ZH-CN
X-NONE

































<[if gte mso 9]>
DefSemiHidden="true" DefQFormat="false" DefPriority="99"
LatentStyleCount="267">
UnhideWhenUsed="false" QFormat="true" Name="Normal" />
UnhideWhenUsed="false" QFormat="true" Name="heading 1" />


















UnhideWhenUsed="false" QFormat="true" Name="Title" />

UnhideWhenUsed="false" QFormat="true" Name="Subtitle" />
UnhideWhenUsed="false" QFormat="true" Name="Strong" />
UnhideWhenUsed="false" QFormat="true" Name="Emphasis" />
UnhideWhenUsed="false" Name="Table Grid" />

UnhideWhenUsed="false" QFormat="true" Name="No Spacing" />
UnhideWhenUsed="false" Name="Light Shading" />
UnhideWhenUsed="false" Name="Light List" />
UnhideWhenUsed="false" Name="Light Grid" />
UnhideWhenUsed="false" Name="Medium Shading 1" />
UnhideWhenUsed="false" Name="Medium Shading 2" />
UnhideWhenUsed="false" Name="Medium List 1" />
UnhideWhenUsed="false" Name="Medium List 2" />
UnhideWhenUsed="false" Name="Medium Grid 1" />
UnhideWhenUsed="false" Name="Medium Grid 2" />
UnhideWhenUsed="false" Name="Medium Grid 3" />
UnhideWhenUsed="false" Name="Dark List" />
UnhideWhenUsed="false" Name="Colorful Shading" />
UnhideWhenUsed="false" Name="Colorful List" />
UnhideWhenUsed="false" Name="Colorful Grid" />
UnhideWhenUsed="false" Name="Light Shading Accent 1" />
UnhideWhenUsed="false" Name="Light List Accent 1" />
UnhideWhenUsed="false" Name="Light Grid Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 1" />

UnhideWhenUsed="false" QFormat="true" Name="List Paragraph" />
UnhideWhenUsed="false" QFormat="true" Name="Quote" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Quote" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1" />
UnhideWhenUsed="false" Name="Dark List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 1" />
UnhideWhenUsed="false" Name="Colorful List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 1" />
UnhideWhenUsed="false" Name="Light Shading Accent 2" />
UnhideWhenUsed="false" Name="Light List Accent 2" />
UnhideWhenUsed="false" Name="Light Grid Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2" />
UnhideWhenUsed="false" Name="Dark List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 2" />
UnhideWhenUsed="false" Name="Colorful List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 2" />
UnhideWhenUsed="false" Name="Light Shading Accent 3" />
UnhideWhenUsed="false" Name="Light List Accent 3" />
UnhideWhenUsed="false" Name="Light Grid Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3" />
UnhideWhenUsed="false" Name="Dark List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 3" />
UnhideWhenUsed="false" Name="Colorful List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 3" />
UnhideWhenUsed="false" Name="Light Shading Accent 4" />
UnhideWhenUsed="false" Name="Light List Accent 4" />
UnhideWhenUsed="false" Name="Light Grid Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4" />
UnhideWhenUsed="false" Name="Dark List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 4" />
UnhideWhenUsed="false" Name="Colorful List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 4" />
UnhideWhenUsed="false" Name="Light Shading Accent 5" />
UnhideWhenUsed="false" Name="Light List Accent 5" />
UnhideWhenUsed="false" Name="Light Grid Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5" />
UnhideWhenUsed="false" Name="Dark List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 5" />
UnhideWhenUsed="false" Name="Colorful List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 5" />
UnhideWhenUsed="false" Name="Light Shading Accent 6" />
UnhideWhenUsed="false" Name="Light List Accent 6" />
UnhideWhenUsed="false" Name="Light Grid Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6" />
UnhideWhenUsed="false" Name="Dark List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 6" />
UnhideWhenUsed="false" Name="Colorful List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 6" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Book Title" />



<[if gte mso 10]>

 


    如上所示,由正整数123……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是,结点m所在的子树中一共包括多少个结点。

    比如,n = 12m = 3那么上图中的结点131415以及后面的结点都是不存在的,结点m所在子树中包括的结点有36712,因此结点m的所在子树中共有4个结点。

输入:

<[if gte mso 9]>

Normal
0



7.8 磅
0
2

false
false
false

EN-US
ZH-CN
X-NONE

































<[if gte mso 9]>
DefSemiHidden="true" DefQFormat="false" DefPriority="99"
LatentStyleCount="267">
UnhideWhenUsed="false" QFormat="true" Name="Normal" />
UnhideWhenUsed="false" QFormat="true" Name="heading 1" />


















UnhideWhenUsed="false" QFormat="true" Name="Title" />

UnhideWhenUsed="false" QFormat="true" Name="Subtitle" />
UnhideWhenUsed="false" QFormat="true" Name="Strong" />
UnhideWhenUsed="false" QFormat="true" Name="Emphasis" />
UnhideWhenUsed="false" Name="Table Grid" />

UnhideWhenUsed="false" QFormat="true" Name="No Spacing" />
UnhideWhenUsed="false" Name="Light Shading" />
UnhideWhenUsed="false" Name="Light List" />
UnhideWhenUsed="false" Name="Light Grid" />
UnhideWhenUsed="false" Name="Medium Shading 1" />
UnhideWhenUsed="false" Name="Medium Shading 2" />
UnhideWhenUsed="false" Name="Medium List 1" />
UnhideWhenUsed="false" Name="Medium List 2" />
UnhideWhenUsed="false" Name="Medium Grid 1" />
UnhideWhenUsed="false" Name="Medium Grid 2" />
UnhideWhenUsed="false" Name="Medium Grid 3" />
UnhideWhenUsed="false" Name="Dark List" />
UnhideWhenUsed="false" Name="Colorful Shading" />
UnhideWhenUsed="false" Name="Colorful List" />
UnhideWhenUsed="false" Name="Colorful Grid" />
UnhideWhenUsed="false" Name="Light Shading Accent 1" />
UnhideWhenUsed="false" Name="Light List Accent 1" />
UnhideWhenUsed="false" Name="Light Grid Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 1" />

UnhideWhenUsed="false" QFormat="true" Name="List Paragraph" />
UnhideWhenUsed="false" QFormat="true" Name="Quote" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Quote" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1" />
UnhideWhenUsed="false" Name="Dark List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 1" />
UnhideWhenUsed="false" Name="Colorful List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 1" />
UnhideWhenUsed="false" Name="Light Shading Accent 2" />
UnhideWhenUsed="false" Name="Light List Accent 2" />
UnhideWhenUsed="false" Name="Light Grid Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2" />
UnhideWhenUsed="false" Name="Dark List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 2" />
UnhideWhenUsed="false" Name="Colorful List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 2" />
UnhideWhenUsed="false" Name="Light Shading Accent 3" />
UnhideWhenUsed="false" Name="Light List Accent 3" />
UnhideWhenUsed="false" Name="Light Grid Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3" />
UnhideWhenUsed="false" Name="Dark List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 3" />
UnhideWhenUsed="false" Name="Colorful List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 3" />
UnhideWhenUsed="false" Name="Light Shading Accent 4" />
UnhideWhenUsed="false" Name="Light List Accent 4" />
UnhideWhenUsed="false" Name="Light Grid Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4" />
UnhideWhenUsed="false" Name="Dark List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 4" />
UnhideWhenUsed="false" Name="Colorful List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 4" />
UnhideWhenUsed="false" Name="Light Shading Accent 5" />
UnhideWhenUsed="false" Name="Light List Accent 5" />
UnhideWhenUsed="false" Name="Light Grid Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5" />
UnhideWhenUsed="false" Name="Dark List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 5" />
UnhideWhenUsed="false" Name="Colorful List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 5" />
UnhideWhenUsed="false" Name="Light Shading Accent 6" />
UnhideWhenUsed="false" Name="Light List Accent 6" />
UnhideWhenUsed="false" Name="Light Grid Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6" />
UnhideWhenUsed="false" Name="Dark List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 6" />
UnhideWhenUsed="false" Name="Colorful List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 6" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Book Title" />



<[if gte mso 10]>

    输入数据包括多行,每行给出一组测试数据,包括两个整数mn (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0,表示输入的结束,这组数据不用处理。

输出:

<[if gte mso 9]>

Normal
0



7.8 磅
0
2

false
false
false

EN-US
ZH-CN
X-NONE

































<[if gte mso 9]>
DefSemiHidden="true" DefQFormat="false" DefPriority="99"
LatentStyleCount="267">
UnhideWhenUsed="false" QFormat="true" Name="Normal" />
UnhideWhenUsed="false" QFormat="true" Name="heading 1" />


















UnhideWhenUsed="false" QFormat="true" Name="Title" />

UnhideWhenUsed="false" QFormat="true" Name="Subtitle" />
UnhideWhenUsed="false" QFormat="true" Name="Strong" />
UnhideWhenUsed="false" QFormat="true" Name="Emphasis" />
UnhideWhenUsed="false" Name="Table Grid" />

UnhideWhenUsed="false" QFormat="true" Name="No Spacing" />
UnhideWhenUsed="false" Name="Light Shading" />
UnhideWhenUsed="false" Name="Light List" />
UnhideWhenUsed="false" Name="Light Grid" />
UnhideWhenUsed="false" Name="Medium Shading 1" />
UnhideWhenUsed="false" Name="Medium Shading 2" />
UnhideWhenUsed="false" Name="Medium List 1" />
UnhideWhenUsed="false" Name="Medium List 2" />
UnhideWhenUsed="false" Name="Medium Grid 1" />
UnhideWhenUsed="false" Name="Medium Grid 2" />
UnhideWhenUsed="false" Name="Medium Grid 3" />
UnhideWhenUsed="false" Name="Dark List" />
UnhideWhenUsed="false" Name="Colorful Shading" />
UnhideWhenUsed="false" Name="Colorful List" />
UnhideWhenUsed="false" Name="Colorful Grid" />
UnhideWhenUsed="false" Name="Light Shading Accent 1" />
UnhideWhenUsed="false" Name="Light List Accent 1" />
UnhideWhenUsed="false" Name="Light Grid Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 1" />

UnhideWhenUsed="false" QFormat="true" Name="List Paragraph" />
UnhideWhenUsed="false" QFormat="true" Name="Quote" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Quote" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1" />
UnhideWhenUsed="false" Name="Dark List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 1" />
UnhideWhenUsed="false" Name="Colorful List Accent 1" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 1" />
UnhideWhenUsed="false" Name="Light Shading Accent 2" />
UnhideWhenUsed="false" Name="Light List Accent 2" />
UnhideWhenUsed="false" Name="Light Grid Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2" />
UnhideWhenUsed="false" Name="Dark List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 2" />
UnhideWhenUsed="false" Name="Colorful List Accent 2" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 2" />
UnhideWhenUsed="false" Name="Light Shading Accent 3" />
UnhideWhenUsed="false" Name="Light List Accent 3" />
UnhideWhenUsed="false" Name="Light Grid Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3" />
UnhideWhenUsed="false" Name="Dark List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 3" />
UnhideWhenUsed="false" Name="Colorful List Accent 3" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 3" />
UnhideWhenUsed="false" Name="Light Shading Accent 4" />
UnhideWhenUsed="false" Name="Light List Accent 4" />
UnhideWhenUsed="false" Name="Light Grid Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4" />
UnhideWhenUsed="false" Name="Dark List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 4" />
UnhideWhenUsed="false" Name="Colorful List Accent 4" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 4" />
UnhideWhenUsed="false" Name="Light Shading Accent 5" />
UnhideWhenUsed="false" Name="Light List Accent 5" />
UnhideWhenUsed="false" Name="Light Grid Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5" />
UnhideWhenUsed="false" Name="Dark List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 5" />
UnhideWhenUsed="false" Name="Colorful List Accent 5" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 5" />
UnhideWhenUsed="false" Name="Light Shading Accent 6" />
UnhideWhenUsed="false" Name="Light List Accent 6" />
UnhideWhenUsed="false" Name="Light Grid Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium List 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6" />
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6" />
UnhideWhenUsed="false" Name="Dark List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Shading Accent 6" />
UnhideWhenUsed="false" Name="Colorful List Accent 6" />
UnhideWhenUsed="false" Name="Colorful Grid Accent 6" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis" />
UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Intense Reference" />
UnhideWhenUsed="false" QFormat="true" Name="Book Title" />



<[if gte mso 10]>

    对于每一组测试数据,输出一行,该行包含一个整数,给出结点m所在子树中包括的结点的数目。

样例输入:
3 12
0 0
样例输出:
4

cpp 代码如下:
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
int n, m, ans;
int p2[32];
int main() {
	p2[0] = 1;
	for(int i=1; i<32; i++)
	p2[i] = p2[i-1] << 1;
	while(cin >> m >> n, m) {
		int s = log2(m);
		int e = log2(n);
		ans = 0;
		if(m == 1){
			cout << n << endl;
			continue;
		}

//		if( (m - p2[s] < p2[s-1] || n-p2[e] >= p2[e-1])){
//			ans = n - p2[e] + 1;
//			if(ans > p2[e-1]) ans -= p2[e-1];
//		}

		int cnt = 0;
		int last = m;
		while(e > s) {
			ans += p2[cnt];
			e --;
			cnt ++;
			last <<= 1;
		}
		//cout << ans << " " << last << endl;
		if(n >= last){
			int t = n-last >= p2[cnt] ? p2[cnt] : n-last+1;
			ans += t;
		}
		cout << ans << endl;
	}
	return 0;
}

/**************************************************************
	Problem: 1113
	User: coder
	Language: C++
	Result: Accepted
	Time:0 ms
	Memory:1532 kb
****************************************************************/


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢