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

UVa 712 - S-Trees

程序员文章站 2024-03-18 21:59:22
...

题目:给你一棵全然二叉树,再给你一个xi1~xin-1的序列,相应从根到叶子上一层。

            每层相应一个xi,叶子是0或1,如今给你一些路径,输出路径相应的叶子的值;

            路径是01串。从更開始往下走,0表示左子树,1表示右子树,相应x1~xn-1的顺序。

分析:模拟。

直接安找路径走过去就好了,由于是二叉树,正好相应二进制数。

注意:路径的顺序要调整到和树一样在计算。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int x[10],f[10];
int leaf[200];

int main()
{
	int  n,k,t = 1;
	char buf[200];
	while (~scanf("%d",&n) && n) {
		for (int i = 0 ; i < n ; ++ i) {
			scanf("%s",buf);
			x[i] = atoi(&buf[1])-1;
		}
		scanf("%s",buf);
		int m = 1<<n;
		for (int i = 0 ; i < m ; ++ i)
			leaf[i] = buf[i]-'0';
		
		printf("S-Tree #%d:\n",t ++);
		scanf("%d",&k);
		for (int i = 0 ; i < k ; ++ i) {
			scanf("%s",buf);
			for (int j = 0 ; j < n ; ++ j)
				f[x[j]] = buf[j]-'0';
			int v = 0;
			for (int j = 0 ; j < n ; ++ j)
				v = 2*v+f[x[j]];
			printf("%d",leaf[v]);
		}
		printf("\n\n");
	}
    return 0;
}