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{x 1,x 2,x 3,...,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("
");
}

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

-生命の意味は、その意味を与えることにある.
オリジナル
http://blog.csdn.net/shuangde800
,By D_Double