首页 > 代码库 > [ POJ ][ HASH ] 1635 Subway tree systems
[ POJ ][ HASH ] 1635 Subway tree systems
首先，对于一个树，我们可以有一种压缩表示：
0010011101001011
其中 0 表示向下走，1 表示向上走。于是：
00100111|01|001011
对于每一段的 0 1 出现次数相同，这种hash方法叫 树的最小表示法 。
1635 题目精简大意：给你n对01字符串，判断每一对儿表示的是不是同一个树，方法：
1.定义 cnt, start, end 来记录当前0 1之和是否相等，start，end 记录相等时所得字数的范围。
2.去首尾得到子串，递归进行1步骤直到子串只为“0 1”。
3.所有子串排序组合到一起然后重新替代原串，此时的新str即为最小表示（sort字典序排序）。
4.两串进行比较即可。
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <vector>using namespace std;int n;void dfs(string& str) { if(str.length() == 2) return; vector<string> substrs; int z = 0, start = 0, end = 0; for(int i = 0; i < str.length(); i++) { if(str[i] == ‘0‘) z++; else if(str[i] == ‘1‘) { z--; if(z == 0) { end = i; string substr = str.substr(start + 1, end - 1 - start); dfs(substr); substrs.push_back(‘0‘ + substr + ‘1‘); start = i + 1; } } } sort(substrs.begin(), substrs.end()); str = ""; for(int i = 0; i < substrs.size(); i++) { str += substrs[i]; }}int main() { cin >> n; while(n--) { string str1, str2; cin >> str1 >> str2; if(str1.length() != str2.length()) { cout << "different" << endl; continue; } else { dfs(str1), dfs(str2); if(str1 == str2) cout << "same" << endl; else cout << "different" << endl; } } return 0;}
[ POJ ][ HASH ] 1635 Subway tree systems
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。