欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[数据结构 树] S-Trees UVa712

程序员文章站 2022-03-01 18:44:56
...

题目描述

给你一个深度为n的满二叉树,每层代表一个01变量,取0时向左走,取1时向右走。现给出所有的子叶的值和一些查询值,求每个查询值到达的子叶的值。

题解

本题应用的是完全二叉树的性质。不用建立树,以0n1的顺序保存子叶的值。将查询值看做二进制,还原为十进制对应的就是子叶的值。

AC代码

#include <cstdio>
#include <cstring>
const int maxn = 10000;
int order[8];
char val[maxn];

int main(){
    int n, kase = 0;
    while(scanf("%d", &n) != EOF && n){
        char a[3], dex[8];
        for(int i = 0; i<n; i++){
            scanf("%s", a);
            order[a[1]-1-'0']=n-i-1;
        }
        scanf("%s", val);
        int m;
        scanf("%d", &m);
        printf("S-Tree #%d:\n", ++kase);
        while(m--){
            int index = 0;
            scanf("%s", dex);
            for(int i = 0; i<n; i++){
                index += (dex[i]-'0') * (1<<order[i]);
            }
            printf("%c", val[index]);
        }
        printf("\n\n");
    }
}