题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=653
题目意思:
给一颗二叉树,每层有一个值,1向右走,左向左走,给你一串每层的值,让你求出最后的结果。
解题思路:
记住树的层次结构,记住树的各Xi代表的值,注意检索最后结果是,可以用向右就乘以2,向左就乘以2减1来处理,从而求得最后结果下标。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) using namespace std; char save[10]; int result[150],tree[10],path[10]; int ans[150]; int main() { int ca=0,n,m; while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) { scanf("%s",save); sscanf(&save[1],"%d",&tree[i]); //记住每一层代表的数字序号 } int limit=(int)(pow(2.0,n*1.0)+eps); for(int i=1;i<=limit;i++) scanf("%1d",&result[i]); //记住最后的结果集 scanf("%d",&m); printf("S-Tree #%d:\n",++ca); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%1d",&path[j]); //每一个序号对应的值 int last=1,depth=1; while(depth<=n) { if(path[tree[depth]]) //这里是关键,如果是1则乘以2,否则乘以2减1 last=last*2; else last=last*2-1; depth++; } printf("%d",result[last]); //最终得到结果 } printf("\n\n"); } return 0; }