51Nod-1832-先序遍历与后序遍历

ACM模版

描述

题解

官方题解的思路十分的清晰，所以先看看官方题解：

也就是说决定树的种类的是只拥有一个儿子的结点个数 ct ，最后结果为 2ct 。由于这里的总结点数十分大，所以这里的结果将会是一个大数，那么我们顺其自然的引入大数，当然，如果你害怕不够快，可以再加上一个快速幂，当然，不加也是稳稳的，当然，剩下的就没有啥了……看看代码体会一下吧~~~需要熟练掌握先序和后序遍历的性质。

代码

#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;
}