题解：P1229 遍历问题

思路

首先观察这三种遍历顺序的规律：

中序遍历：左根右（根把子节点隔开）；
先序遍历：根左右（两个子节点挨着）；
后序遍历：左右根（两个子节点挨着）。

如此一来就发现了问题：先、后序遍历的子节点都是挨着的。如果某棵子树只有 $1$ 个子节点，只看先、后序遍历是无法区分出这是左子结点还是右子节点，对应在中序遍历中就会出现两种情况。

所以现在我们只需要统计只有 $1$ 个子节点的子树的数量就可以了。

统计方法

如果一棵子树只有根和

1

个节点，假设根是 A，子节点是 B。表现方式是：

在先序遍历中为根在前：AB；
在后序遍历中为根在后：BA。

刚好是相邻且顺序相反。

按照这个规律，就可以循环找字符串

s_1,s_2

的

\forall i\isin[1,n),j\isin[1,n)

满足

s_i=s_{j+1}

且

s_{i+1}=s_j

的

(i,j)

组合的数量。

代码

CPP

#include<bits/stdc++.h>
using namespace std;

int main(){	
    string s1, s2; 
    cin >> s1 >> s2;
    
    long long ans = 1;
    for(int i=0; i<s1.size()-1; i++)
        for(int j=0; j<s2.size()-1; j++)
            if(s1[i+1] == s2[j] && s1[i] == s2[j+1])
                ans *= 2;
    
    cout << ans;
}

题解：P1229 遍历问题

文章操作

思路

统计方法

代码

相关推荐

评论

题解：P1229 遍历问题