UVa 712 - S-Trees

712-S-Trees

2807

51.34%

1408

85.37%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=653

样例输入：

3
x1 x2 x3
00000111
4
000
010
111
110
3
x3 x1 x2
00010011
4
000
010
111
110
0

样例输出：

S-Tree #1:
0011

S-Tree #2:
0011

题目大意：

给一个序列集合VVI {x1, x2, x3, ....,xn}, VVI中不是0就是1 然后有一个n层的树， 每一层同层的都是相同的一个数，这个数取自VVI中， 输入会给出 每一层是VVI中的哪一个

最后一层是叶子结点， 上面是一串给定的数字。

从跟结点出发， 如果那个结点是0，就往左儿子方向走， 如果是1就往右儿子方向走。 最后落在最后一层的叶子结点上，输出这个数字

解题思路：

这题应该算是这个二叉树专题中很水的一道题了。 不用建树，如果是1就 当前结点*2+1，如果是0就乘。 最后得到一个数字。这个数字再减去前面层的结点之和，然后就可输出对应的结果。

具体看代码。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
char termi[200];
char vva[200];
vector<int>vtOrder;

inline void Solve(){
    char temp[10];
    int val;
    vtOrder.clear();
    for(int i=0; i<n; ++i){
        scanf("%s", temp);
        sscanf(temp+1, "%d", &val);
        vtOrder.push_back(val);
    }
    scanf("%s", termi);
    scanf("%d", &m);
    while(m--){
        scanf("%s", vva+1);
        int pos=1;
        for(int i=0; i<vtOrder.size(); ++i){
            if(vva[vtOrder[i]]=='0')
                pos = pos*2;
            else
                pos = pos*2+1;
        }
        printf("%c", termi[pos-(1<<n)]);
    }
    printf("\n");
}

int main(){
    freopen("input.txt", "r", stdin);
    int cas=1;
    while(scanf("%d", &n) && n){
        printf("S-Tree #%d:\n", cas++);
        Solve();
        printf("\n");
    }
    return 0;
}