51Nod 算法马拉松28 A题 先序遍历与后序遍历 分治

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

---

题目传送门 - 51Nod1832

---

题意概括

　　对于给定的一个二叉树的先序遍历和后序遍历，输出有多少种满足条件的二叉树。
　　两棵二叉树不同当且仅当对于某个x，x的左儿子编号不同或x的右儿子编号不同。

---

题解

　　我们发现，如果两棵二叉树先后序遍历相同，但是形态不同，只可能是某些节点，只有一个子节点，这个子节点在左边和右边都可以的情况。

　　那么只需要统计这样的节点个数，然后2^tot，高精度即可。

---

代码

#include <cstring>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int N=10000+5;

int n,tot,a[N],b[N],pa[N],pb[N];

int d,x[1005];

void dfs(int la,int ra,int lb,int rb){

	if (la==ra)

		return;

	la++,rb--;

	int p=pb[a[la]];

	if (p==rb){

		tot++;

		dfs(la,ra,lb,rb);

		return;

	}

	int s=p-lb+1;

	dfs(la,la+s-1,lb,lb+s-1);

	dfs(la+s,ra,lb+s,rb);

}

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n;i++)

		scanf("%d",&a[i]),pa[a[i]]=i;

	for (int i=1;i<=n;i++)

		scanf("%d",&b[i]),pb[b[i]]=i;

	tot=0;

	dfs(1,n,1,n);

	memset(x,0,sizeof x);

	d=1,x[1]=1;

	while (tot--){

		int mod=1e9;

		for (int i=1;i<=d;i++)

			x[i]<<=1;

		for (int i=1;i<=d;i++)

			x[i+1]+=x[i]/mod,x[i]%=mod;

		if (x[d+1])

			d++;

	}

	printf("%d",x[d]);

	for (int i=d-1;i>0;i--)

		printf("%09d",x[i]);

	return 0;

}