wikioi 1029 中序遍歷總數(shù)
來源：程序員人生 發(fā)布時間：2014-10-17 05:02:13 閱讀次數(shù)：3475次
題意：給出前序遍歷和后序遍歷，求總共有多少種中序遍歷的可能。
思路：
對于一個節(jié)點，當(dāng)且僅當(dāng)它僅有一棵子樹時，在保證先序和后序相同的前提下，才可能有不同的中序(它的子樹可在左或右，所以有2種)；
此時必有a[i+1]==b[j-1]（為什么）//i是節(jié)點在先序中的位置，j是它在后序中的位置；
因此只要找到這種節(jié)點的個數(shù)設(shè)為x，ans=2^x。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main()
{
char s[27],ss[27];
scanf("%s%s",s,ss);
int i,j,len=strlen(s),rr=strlen(ss),ans=0;
for(i=0;i<len;i++)
for(j=0;j<rr;j++)
if(s[i]==ss[j]&&i>0&&s[i-1]==ss[j+1])
ans++;
ll cnt=1LL<<ans;
cout<<cnt<<endl;
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
