UVa712(S树)

此题如果分析得当会发现本质上就是一个C语言的二-十进制转换。由于输入的S树的叶子节点是在xi已经排好序的基础上输入的，所以在解题时并不要考虑xi的顺序。

 1 #include 
 2 
 3 using namespace std;
 4 
 5 /**************** 
 6 UVa712 S树  
 7 ***************/
 8 
 9 int main()
10 {
11     //deep:树的深度 
12     int deep = 0;
13     cin >> deep;
14     //STree:存储叶子的数组  pow(2, deep)是叶子的个数  
15     int max = pow(2, deep);
16     int STree[max];
17     memset(STree, -1, sizeof(STree));
18     for(int i = 0; i < max; i++){
19         cin >> STree[i];
20     }
21     
22     //num:表达式的个数 
23     int tmp = 0, num = 0;
24     cin >> num;
25     //存储xi的值  
26     vector<int> v;
27     //存储答案  
28     vector<int> ans;
29     int res = 0, h = 0;
30     while(num--){
31         int k = 0;
32         v.clear();
33         //输入表达式 
34         for(int i = 0; i < deep; i++){
35             cin >> tmp;
36             v.push_back(tmp);
37         } 
38         res = 0;
39         //将查询式转变为十进制值  
40         while(!v.empty()){
41             int ch = v.back();
42             v.pop_back();
43             res += ch*pow(2, (k++));
44         }
45         ans.push_back(res);
46     } 
47     for(int i = 0; i < ans.size(); i++){
48         cout << STree[ans[i]];
49     }
50     cout << endl;
51     return 0;
52 } 

输出结果：

3
0 0 0 0 0 1 1 1
4
0 0 0
0 1 0
1 1 1
1 1 0
0011