3019: 【普及/提高-】【P1229】遍历问题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
输入
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。
输出
输出可能的中序遍历序列的总数，结果不超过长整型数。
样例输入 复制
abc
cba样例输出 复制
4提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int ans;
char a[ MAXN ],b[ MAXN ];
int main(){
cin >> a >> b;
for ( int i = 0 ; a[i] ;i++ )
for ( int j = 1 ; b[j] ;j++ )
if ( a[i] == b[j] && a[i+1] == b[j-1])
ans++;
cout << (1 << ans) << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
long long ans = 1;
cin >> s1 >> s2;
for(int i = 0;i <= s1.length()-2;i++) {
for (int j = 0;j <=s1.length()-1;j++) {
if(s1[i] == s2[j]) {
if(s1[i+1] == s2[j-1]) ans *= 2;
break;
}
}
}
cout << ans;
return 0;
}