首页 > 代码库 > S-Tree (UVa 712) 二叉树
S-Tree (UVa 712) 二叉树
题目:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=839&page=show_problem&problem=653
思路:当前结点为k,左走则 2k,右走则 2k + 1,得到最后的点,减去前面n层的所有结点,得到的下标对应的0或1就是答案。
/* S-Tree (UVa 712) */ #include <iostream> #include <cstring> #include <vector> using namespace std; const int maxn = 10; int n; char s[1<<maxn], input[maxn]; //输入和查询 int idx[maxn]; //每一层对应的变量 xi vector<char> output; //输出查询结果 int solve(); int main(){ //freopen("input.txt", "r", stdin); int cnt = 0; while(cin >> n && n != 0){ memset(s+1, 0, sizeof(s+1)); memset(idx, 0, sizeof(idx)); output.clear(); for(int i=1; i<=n; i++){ char str[3]; cin >> str; idx[i] = str[1] - ‘0‘; } int m; cin >> s+1 >> m; for(int i=1; i<=m; i++){ cin >> input+1; output.push_back(s[solve()]); } cout << "S-Tree #" << ++cnt << ":" << endl; for(int i=0; i<m; i++) cout << output[i]; cout << endl << endl; } } int solve(){ int k = 1; for(int i=1; i<=strlen(input+1); i++){ int t = input[idx[i]] - ‘0‘; if(t == 0) k = 2*k; else k = 2*k + 1; } //cout << k - (1<<n) + 1 << endl; return (k - (1<<n) + 1); }
S-Tree (UVa 712) 二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。