UVA ~ 712 ~ S-Trees（二叉树，二进制枚举）

题意

给出一棵满二叉树，每一层用一个$x_i$xi​的01变量来表示，$x_i$xi​取0往左走，取1往右走。每个叶子结点有一个值（0或1），然后有一些询问，求每个询问到达的叶子结点的值。

多组测试数据，以n=0表示结束，每组先输入n表示有n层，然后输入从根到叶子每一层对应$x_几$x几​那个变量，然后输入叶子结点对应的值。
接下来输入Q次询问，每次询问输入一个长度为n的01串表示$x_1->x_n$x1​−>xn​对应的值。
对于每个询问输出一个答案，每组测试数据之后输出两个换行。

思路

我们把最后一层看作一个长度为n的二进制数，000对应第一个，001对应第二个，010对应第三个。
每次询问把那个01串转化为10进制就是对应的叶子位置，输出即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 130;
int n, x[MAXN];
char leaf[MAXN], a[MAXN];
int main()
{
    int CASE = 1;
    while (~scanf("%d%*c", &n) && n)
    {
        for (int i = 0; i < n; i++) scanf("%*c%d%*c", &x[i]);
        scanf("%s%*c", leaf);
        string ans;
        int Q; scanf("%d", &Q);
        while (Q--)
        {
            scanf("%s%*c", a);
            int res = 0;
            for (int i = 0; i < n; i++)
            {
                if (a[x[i] - 1] == '1') res |= 1 << (n - i - 1);
            }
            ans += leaf[res];
        }
        printf("S-Tree #%d:\n%s\n\n", CASE++, ans.c_str());
    }
    return 0;
}
/*
3
x1 x2 x3
00000111
4
000
010
111
110
3
x3 x1 x2
00010011
4
000
010
111
110
0
*/