wikioi 1029 中序遍歷總數
來源：程序員人生 發布時間：2014-10-17 05:02:13 閱讀次數：3479次
題意：給出前序遍歷和后序遍歷，求總共有多少種中序遍歷的可能。
思路：
對于一個節點，當且僅當它僅有一棵子樹時，在保證先序和后序相同的前提下，才可能有不同的中序(它的子樹可在左或右，所以有2種)；
此時必有a[i+1]==b[j-1]（為什么）//i是節點在先序中的位置，j是它在后序中的位置；
因此只要找到這種節點的個數設為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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
