UVa712 习题6-2 S树（S-Trees）

原题链接： UVA-712

题目大意：

 模给一个序列集合VVI {x1, x2, x3, ....,xn}, VVI中不是0就是1。然后有一个n层的树，每一层同层的都是相同的一个数，这个数取自VVI中， 输入会给出每一层是VVI中的哪一个最后一层是叶子结点，上面是一串给定的数字。从跟结点出发，如果那个结点是0，就往左儿子方向走，如果是1就往右儿子方向走。最后落在最后一层的叶子结点上，输出这个数字。

解题思路：

 在紫书给的题目的一开始说树对应表达式，猛一下感觉很蒙圈，但是再往下看差不多就明白了。跟表达式关系不大。主要是因为通过序列集合VVI {x1, x2, x3, ....,xn}来确定给定表达式（一串给定的顺序）的串内执行顺序。

 不续要建树可以以直接在数组里模拟，然后根据给定的序列顺序来执行表达。最终输出结果。细节上要注意，比如字符转数字的时候记得-'0'。

 

 上午弄一道题弄了一上午（再加上半个下午）最后样例虽然过了但是还是没AC，很无奈啊 _(:3 」∠)_。然后写完这道题就感觉好多了，水题虽然浪费生命但是可以调节心情啊，被难题虐的受不了的时候可以来一道爽一爽，哈哈哈。

代码：

#include<iostream>
#include<cmath>
#include<sstream>
#include<string>
#include<cstring>
using namespace std;
const int MAXLEN = 128 + 10;
int leaf[MAXLEN];
int main(){
	int n, m, len, kase = 0;
	string s,num;
	while (cin >> n && n){
		getchar();
		cout << "S-Tree #" << ++kase << ":\n";
		memset(leaf, 0, sizeof(leaf));
		len = pow(2, n);
		getline(cin, s);
		for (int i = 0; i < len; i++)	leaf[i] = getchar() - '0';
		cin >> m;
		while (m--){
			int x,cur = 1;
			cin >> num;
			for (int i = 1; i < s.length(); i = i + 3){
				int idx = s[i] - '1';
				x = num[idx] - '0';
				if (x == 0)	cur = 2 * cur;
				else cur = 2 * cur + 1;
			}
			cout << leaf[cur - len];
		}
		cout << endl<<endl;
	}
}