712 - S-Trees

Problem.png

题目给出了叶子的值和每一层的取值，因此可以不用建树，直接模拟二分查找的过程即可。二分查找本质上也是构造了一棵搜索树。

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;

int main() {
    int n;
    int t = 1;
    while (cin >> n && n) {
        getchar();
        printf("S-Tree #%d:\n", t++);
        string order;
        getline(cin, order);
        vector<int> seq;
        for (int i = 0; i < order.length(); i++) {
            if (order[i] >= '0' && order[i] <= '9')
                seq.push_back(order[i] - '0');
        }
        string leaf;
        cin >> leaf;
        int m;
        cin >> m;
        for (int i = 0; i < m; i++) {
            string vva;
            cin >> vva;
            int low = 0, high = (1 << n) - 1;
            int mid = 0;
            for (int j = 0; j < seq.size(); j++) {
                if (vva[seq[j] - 1] == '0') {
                    // 等于0，取左边一半
                    mid = low + (high - low) / 2;
                    high = mid;
                }
                else {
                    // 等于1，取右边一半
                    mid = low + (high - low) / 2 + 1;
                    low = mid;
                }
            }
            cout << leaf[mid];
        }
        cout << endl << endl;
    }
    return 0;
}