Skip to content

14118: 【原4118】travel

题目

题目描述

author: Ca. 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4118

Description

我们都很熟悉二叉树的前序、中序和后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历序列,求它的后序遍历序列,相应的已知一棵二叉树的后序遍历和中序遍历序列,你也能求出它的前序遍历。 然而,给定一棵二叉树的前序和后序遍历序列,你却不能确定其中序遍历序列。并且这一现象不仅出现在二叉树中,对M叉树亦如此。

Input Format

输入数据共一行,格式为:m s1 s2 表示该树为m叉树,其前序遍历序列为s1,其后序遍历序列为s2,s1和s2由小写字母构成。 1≤m≤20,且s1与s2的长度相等且不超过26,若它们的长度为k,则前k个小写字母将不重复地出现在s1与s2中。

Output Format

输出可能的中序遍历序列的总数,结果不超过长整型数。

Sample Input

10 abc bca

Sample Output

45

FineArtz's solution

/* travel */
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

long long FACT[21] = {0};

long long comb(long long n, long long k){
    return FACT[n] / FACT[k] / FACT[n - k];
}

int m;
char s1[25], s2[25];

long long travel(char *s1, long long len1, char *s2, long long len2){
    long long ret = 1, p1 = 1, p2 = 0;
    long long child = 0;
    while (p1 < len1){
        for (int i = 0; i < len2; ++i){
            if (s2[i] == s1[p1]){
                p2 = i;
                break;
            }
        }
        ret *= travel(s1 + p1, p2 - p1 + 2, s2 + p1 - 1, p2 - p1 + 2);
        p1 = p2 + 2;
        ++child;
    }
    ret *= comb(m, child);
    return ret;
}

int main(){
    FACT[0] = 1;
    for (int i = 1; i <= 20; ++i)
        FACT[i] = FACT[i - 1] * i;

    cin >> m >> s1 >> s2;
    long long len1 = strlen(s1), len2 = strlen(s2);
    cout << travel(s1, len1, s2, len2);
    return 0;
}

q4x3's solution

/**
 * dfs
 * 一个个找子树
 **/
#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int m;
char s1[30], s2[30];
int C[30];

void init() {
    C[0] = 1;
    for(int i = 1;i <= m;++ i)
        C[i] = C[i - 1] * (m - i + 1) / i;
}

int dfs(int pre, int pos, int len) {
    int cnt = 0, sum = 1;
    for(int i = pre + 1, j = pos;i < pre + len;) {
        int tmp1 = i, tmp2 = j;
        while(j < pre + len - 1 && s1[tmp1] != s2[j])
            ++ i, ++ j;
        ++ cnt;
        sum *= dfs(tmp1, tmp2, j - tmp2 + 1);
        ++ i; ++ j;
    }
    sum *= C[cnt];
    return sum;
}

int main() {
    scanf("%d%s%s", &m, s1, s2);
    if(s1[0] != s2[strlen(s2) - 1]) {
        printf("0\n");
        return 0;
    }
    init();
    printf("%d\n", dfs(0, 0, strlen(s1)));
}

victrid's solution

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long dp[30][30][30] = {};
char pre[30];
char pos[30];
int m;
long long C[30][30] = {};
long long c(int h, int l) {
    if (C[h][l] != 0)
        return C[h][l];
    if (h == l || h == 0)
        return 1;
    else
        C[h][l] = c(h, l - 1) + c(h - 1, l - 1);
    return C[h][l];
}
//It's my fault
//! every digit can appear only once.
long long search(int prep, int posp, int length) {
    int total     = 0;
    long long ans = 1;
    for (int i = prep + 1, j = posp; i < prep + length;) {
        int subpre = i, subpos = j;
        while (j < posp + length - 1 && pre[subpre] != pos[j])
            ++i, ++j;
        ++total;
        ans *= search(subpre, subpos, j - subpos + 1);
        ++i, ++j;
    }
    ans *= c(total, m);
    return ans;
}

int main() {
    scanf("%d %s %s", &m, pre, pos);
    cout << search(0, 0, strlen(pre));
    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
ll dp[28][28][28] = {0}, C[28][28] = {0};
char pre[30], in[30];
ll dfs(int st1, int st2, int l){
    int tot = 0;
    ll res = 1;
    for (int i = st1 + 1, j = st2; i < st1 + l; ){
        int lsti = i, lstj = j;
        while (j < st2 + l - 1 && pre[lsti] != in[j])
            ++i, ++j;
        ++tot;
        res *= dfs(lsti, lstj, j - lstj + 1);
        ++i, ++j;
    }
    res *= C[m][tot];
    return res;
}
void init(){
    m = read();
    scanf("%s%s", pre, in);
    n = strlen(pre);
    C[0][0] = 1;
    for (int i = 1; i <= m; ++i){
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
}
void solve(){
    printf("%lld\n", dfs(0, 0, n));
}
int main(){
    init();
    solve();
    return 0;
}