P1229 遍历问题【洛谷算法习题】

P1229 遍历问题网页链接P1229 遍历问题题目描述我们都很熟悉二叉树的前序、中序、后序遍历在数据结构中常提出这样的问题已知一棵二叉树的前序和中序遍历求它的后序遍历相应的已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历你却不能确定其中序遍历序列考虑如下图中的几棵二叉树所有这些二叉树都有着相同的前序遍历和后序遍历但中序遍历却不相同。输入格式共两行第一行表示该二叉树的前序遍历结果s 1 s_1s1​第二行表示该二叉树的后序遍历结果s 2 s_2s2​。保证至少存在一棵二叉树满足给出的信息s 1 , s 2 s _ 1, s _ 2s1​,s2​中只含小写字母且在某个字符串中不存在相同的字母。输出格式输出可能的中序遍历序列的总数结果不超过2 63 − 1 2^{63}-1263−1。输入输出样例 #1输入 #1abc cba输出 #14解题思路本题核心是二叉树遍历性质规律统计求解前序后序遍历对应的中序序列数量。已知前序和后序无法唯一确定二叉树仅拥有单个孩子的节点会产生两种形态左孩子/右孩子每个此类节点让总方案数翻倍。关键判定规律若前序遍历中相邻两个字符为u, v且后序遍历中这两个字符相邻且顺序为v, u则节点u只有一个孩子是方案数的贡献点。统计这类节点的数量cnt最终答案为2 c n t 2^{cnt}2cnt。由于字符串长度极小暴力双重循环匹配即可算法简洁高效。总结核心逻辑统计只有一个孩子的节点数量每个节点贡献 2 种方案答案为2 22的节点数次方。关键操作遍历前序和后序字符串匹配判定特殊节点、统计数量、快速计算幂次。效率保障字符串长度不超过200暴力匹配无性能压力完美适配题目要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);chars1[233],s2[233];scanf(%s,s1);scanf(%s,s2);ll a0;for(ll i0;istrlen(s1);i)for(ll j1;jstrlen(s2);j){if(s1[i]s2[j]s1[i1]s2[j-1])a;}printf(%lld,1LLa);return0;}