POJ 1105 - S-Trees

http://poj.org/problem?id=1105

概要

高さ n の完全二分木 S-Tree がある． 非終端ノードには変数 x[i] がラベルされており，ルートからの距離が等しい非終端ノードには同じ変数がラベルされ，距離が異なる非終端ノードには異なる変数がラベルされている (つまり全部で n 種類の変数がある)． 終端ノードにはそれぞれ 0 か 1 がラベルされている．

S-Tree は関数 f を表現しており，f(x[1], ..., x[n]) は，そのノードにラベルされた変数が真なら右の子ノードへ，偽なら左の子ノードへと辿っていった先の終端ノードの値を返す．

ラベルの情報と終端ノードの値が与えられたとき，与えられた x[1], ..., x[n] に対して f(x[1], ..., x[n]) の値を答える．

制約

解法

高さ n の完全二分木はサイズが 2^n の配列で表現できる． f(x[1], ..., x[n]) の値のインデックスは，x[1], ..., x[n] を二進表記とみなした数に対応する．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int count = 1;
 8   int depth;
 9   while (cin >> depth && depth != 0) {
10     vector<int> v(depth);
11     for (int i = 0; i < depth; i++) {
12       char x;
13       cin >> x >> v[i];
14     }
15     vector<int> stree(1<<depth);
16     for (int i = 0; i < 1<<depth; i++) {
17       char b;
18       cin >> b;
19       int c = 0;
20       for (int j = 0; j < depth; j++) {
21         c |= ((i&(1<<j))>>j)<<(depth-v[depth-j-1]);
22       }
23       stree[c] = b-'0';
24     }
25 
26     int m;
27     cin >> m;
28     cout << "S-Tree #" << count++ << ':' << endl;
29     for (int i = 0; i < m; i++) {
30       string s;
31       cin >> s;
32       int b = 0;
33       for (int j = 0; j < depth; j++) {
34         b |= (s[j]-'0')<<(depth-j-1);
35       }
36       cout << stree[b];
37     }
38     cout << endl << endl;
39   }
40   return 0;
41 }
poj/1105.cc