习题6-2 S树（S-Trees，UVa 712）

本文主要是介绍习题6-2 S树（S-Trees，UVa 712），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/UVA-712
分类：树
备注：水题
思路：回想例题的经验，直接建树就是了，我认为那些$x_i$都是干扰做题的，无视就好了。隐约觉得有些地方没注意到，以后再看吧。

代码如下：

#include<iostream>
#include<string>
using namespace std;
int n, query, kase, lson[1 << 7], rson[1 << 7];
string line, out;
void Build(int root, int depth)
{if (depth == n - 1){lson[root] = line[(root << 1) - (1 << n)] - '0';rson[root] = line[(root << 1 | 1) - (1 << n)] - '0';return;}lson[root] = root << 1; rson[root] = root << 1 | 1;Build(root << 1, depth + 1);Build(root << 1 | 1, depth + 1);
}
void dfs()
{int key = 1; string out; getline(cin, out);for (int pos = 0; pos < n; pos++){if (out[pos] == '0')key = lson[key];if (out[pos] == '1')key = rson[key];}cout << key;
}
int main(void)
{while (cin >> n && n){getchar();cout << "S-Tree #" << ++kase << ":\n";for(int i=0;i<2;i++)getline(cin, line); Build(1, 0);//建树cin >> query;getchar();while (query--)dfs();cout << "\n\n";}return 0;
}

这篇关于习题6-2 S树（S-Trees，UVa 712）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---