UVa - 712 - S-Trees

712 - S-Trees

题解：统计每一层节点，每遇到1就增加当前区间的一半路程即可。

AC代码：

#include<cstdio>
#include<map>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;

#define _for(i,a,b) for(int i=(a);i<=(b);i++)
const int maxn = 130;

int n,m,a[maxn],tree[maxn],num[maxn];
char x[maxn];
map<int,int> Q;
int main()
{
    int kk = 1;
    while(cin>>n)
    {
        int h = 1;
        if(n==0)break;
        int i;
        _for(i,1,n)
        {
            char s[3];
            cin>>s;
            int k = s[1]-'0';
            Q[k]=i;
        }
        int leng = pow(2,n);
        cin>>x;
        _for(i,1,leng)
        {
            int k = x[i-1]-'0';
            tree[i]=k;
        }
        cin>>m;
        _for(i,1,m)
        {
             char y[n*2];
             cin>>y;
             _for(i,0,n-1)
             {
                 int now = y[i]-'0';
                 a[Q[i+1]] = now;
             }
            int l = 1;
            int ans = 1;
            int now = leng>>1;
            while(l<=n)
            {
                if(a[l]==1)ans+=now;
                l++;
                now=now>>1;
            }
            num[h++]=tree[ans];
        }
        cout<<"S-Tree #"<<kk<<":"<<endl;
        _for(i,1,h-2)cout<<num[i];
        cout<<num[h-1]<<endl;
        kk++;
        cout<<endl;
    }
    return 0;
}