首页 > 代码库 > POJ2499 -Binary Tree

POJ2499 -Binary Tree

题意

一个二叉树某个结点为(a,b),其左孩子为(a + b, b),右孩子为 (a, a + b),根节点为(1,1)。给某一结点,问从根节点到此结点需要向左多少步向右多少步

思路

给出某个节点(a,b),若a>b则为左孩子,相反则为右孩子,并由此可以推出其父节点,按照这个规律一直推到(1,1)。若(a,b)是由根节点向左L向右R,则(b,a)为根节点向左R向右L。

推过样例之后就能发现规律啦

总结

水题,output有空行忘记了,WA了一次,但是现在A完之后不显示A了是什么鬼啊,生气

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <string>
 5 #include <iostream>
 6 
 7 using namespace std ;
 8 int T, kase = 0, a, b;
 9 
10 int main()
11 {
12   //  freopen("in.txt", "r", stdin);
13     scanf("%d", &T);
14     while(T--)
15     {
16         scanf("%d %d", &a, &b);
17         int Left = 0, Right = 0;
18         bool flag = false;
19         bool Reverse = false;
20         if(a < b) {
21             Reverse = true;
22             swap(a, b);
23         }
24 //左右左,左是false
25         while(b)
26         {
27             int x = a, y = b;
28             if(!flag)
29             {
30                 Left += a / b;
31             }
32             else
33             {
34                 Right += a / b;
35             }
36             flag = !flag;
37             a = y;
38             b = x % y;
39         }
40         if(flag) Left--;
41         else Right--;
42         printf("Scenario #%d:\n", ++kase);
43         if(Reverse)
44             printf("%d %d\n", Right, Left);
45         else
46             printf("%d %d\n", Left, Right);
47         printf("\n");
48     }
49     return 0 ;
50 }

 

POJ2499 -Binary Tree