S-Trees UVA - 712 (二叉树模拟)

忘是亡心i 2022-02-26 13:30 200阅读 0赞

题目太长不贴了:[https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=653][https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_653]

解题思路:

每一次查询的结果就是按照Xn顺序得到的二进制数转成10进制,然后根据10进制数去叶子节点中查找对应的数,把所有查询结果按顺序拼接在一起得到的就是答案

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string.h>
    #include <string>
    #include <math.h>
    using namespace std;
    const int MAXN = 10;
    int kN,kM;
    int numHash[MAXN];  //索引
    //首先根据X建树,然后根据二进制计算
    int sindex = 0;
    //二进制转10进制
    
    int BTOD(string num) {
    	int res = 0;
    	int temindex = 0;
    	for (int i = num.length()-1; i >= 0; --i) {
    		res += (num[i] - '0') * pow(1.0*2, temindex++);
    	}
    	return res;
    }
    
    int main(){
    	while(cin >> kN){
    		if(kN == 0) break;  //如果等于0,退出
    		string tempStr,ordStr,numStr;
    		string nodeStr;
    		string resStr;  //结果
    		for(int i = 0;i < kN;++i){
    			cin>>tempStr;
    			ordStr+=tempStr[1];  //父亲结点
    		}
    		cin >> nodeStr;  //读入叶子结点
    		cin >> kM;
    		for(int j = 0; j < kM;++j){
    			memset(numHash,0,sizeof(numHash));
    			cin >> numStr;
    			for(int k = 0; k < numStr.length();++k){
    				numHash[k+1] = numStr[k]-'0'; //索引
    			}
    			string ten;
    			for(int v = 0; v < ordStr.length();++v){
    				ten += numHash[ordStr[v]-'0']+'0';  //按顺序得到二进制数
    			}
    			int tindex = BTOD(ten);
    			resStr += nodeStr[tindex];
    		}
    		printf("S-Tree #%d:\n",++sindex);
    		cout<<resStr<<endl<<endl;
    		 
    	}
    	system("PAUSE");
    	return 0;
    }

[https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_653]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=653