51Nod-1832-先序遍历与后序遍历
发布时间:2020-12-14 05:03:21 所属栏目:大数据 来源:网络整理
导读:ACM模版 描述 题解 官方题解的思路十分的清晰,所以先看看官方题解: 也就是说决定树的种类的是只拥有一个儿子的结点个数 c t ,最后结果为 2 c t 。由于这里的总结点数十分大,所以这里的结果将会是一个大数,那么我们顺其自然的引入大数,当然,如果你害怕
ACM模版 描述题解官方题解的思路十分的清晰,所以先看看官方题解: 也就是说决定树的种类的是只拥有一个儿子的结点个数
代码#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_LEN = 666;
struct BigInt
{
const static int MOD = 10000;
const static int DLEN = 4;
int len;
int a[MAX_LEN];
BigInt()
{
memset(a,0,sizeof(a));
len = 1;
}
BigInt(int v)
{
memset(a,sizeof(a));
len = 0;
do
{
a[len++] = v%MOD;
v /= MOD;
}
while (v);
}
BigInt operator * (const BigInt &b) const
{
BigInt res;
for (int i = 0; i < len; i++)
{
int up = 0;
for (int j = 0; j < b.len; j++)
{
int temp = a[i] * b.a[j] + res.a[i + j] + up;
res.a[i + j] = temp % MOD;
up = temp / MOD;
}
if (up != 0)
{
res.a[i + b.len] = up;
}
}
res.len = len + b.len;
while (res.a[res.len - 1] == 0 && res.len > 1)
{
res.len--;
}
return res;
}
void output()
{
printf("%d",a[len - 1]);
for (int i = len - 2; i >= 0; i--)
{
printf("%04d",a[i]);
}
printf("n");
}
};
const int MAXN = 10010;
int n;
int ct = 0;
int a[MAXN];
int b[MAXN];
int get_id(int l,int r,int num)
{
for (int i = l; i < r; ++i)
{
if (b[i] == num)
{
return i;
}
}
return -1;
}
int calc(int num)
{
if (num == 1)
{
return 1;
}
if (num == 2 || num == 0)
{
return 0;
}
return 0;
}
void dfs(int a_l,int a_r,int b_l,int b_r)
{
int len = a_r - a_l;
if (len == 1)
{
return ;
}
a_l++;
b_r--;
int x = 0,cnt = a_r - a_l,id,ar,br;
while (cnt != 0)
{
id = get_id(b_l,b_r,a[a_l]);
ar = a_l + (id - b_l + 1);
br = id + 1;
x++;
dfs(a_l,b_l,br);
cnt -= (id - b_l + 1);
a_l = ar;
b_l = id + 1;
}
ct += calc(x);
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < n; ++i)
{
scanf("%d",a + i);
}
for (int i = 0; i < n; ++i)
{
scanf("%d",b + i);
}
dfs(0,n,n);
BigInt res(1);
for (int i = 0; i < ct; i++)
{
res = res * BigInt(2);
}
res.output();
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |