首页 > 代码库 > POJ 1240 Pre-Post-erous! 解题报告
POJ 1240 Pre-Post-erous! 解题报告
题意：
给出一个m叉树的前，后序遍历求这样的树有多少种。
Solution:
我们知道前序遍历的第一个点一定是根节点，后序遍历的最后一个点一定是根节点。
由此，我们只一要确定对于每一个节点，它有多少个儿子节点，再累乘C（m，k）。
code
#include <iostream>#include <algorithm>#include <string>using namespace std;string sq, sh;int len, ans,m;int Combination (int n, int m){ int ans = 1; for (int i = 1; i <= m; i++) ans = ans * (n - i + 1) / i; return ans;}void make (int l, int r, int t, int w) { if (l > r || t > w) return; int p = 0, i = 0; while (l <= r) { char s = sq[l]; for (i = 0; i < len; i++) if (sh[i] == s) break; int k = w - i+1; make (l+1, l+k-1, i+1, w); l = l + k; w=i-1; p++; } ans*=Combination(m,p);}int main() { while (cin >>m>> sq >> sh) { len = (int) sq.size() - 1; ans=1; reverse (sh.begin(), sh.end() ); make (1, len, 1, len); cout<<ans<<endl; } return 0;}
POJ 1240 Pre-Post-erous! 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。