首页 > 其他分享 >洛谷 P1827 [USACO3.4] 美国血统 American Heritage(后序遍历)

洛谷 P1827 [USACO3.4] 美国血统 American Heritage(后序遍历)

时间:2022-10-04 21:00:39浏览次数:94  
标签:遍历 洛谷 后序 int 前序 American USACO3.4 P1827 中序

https://www.luogu.com.cn/problem/P1827

题目大意:

已知前序中序遍历

求后序遍历。
输入 #1 
ABEDFCHG
CBADEFGH 
输出 #1 
AEFDBHGC
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
string a,b;
void dfs(int l1,int r1,int l2,int r2)
{
    if(l1>r1||l2>r2) return ;//如果超过了界限,说明已经跑完了,可以返回去了
    for(int i=l1;i<=r1;i++)//中序遍历从左到右
    {
        if(a[i]==b[l2])//找到根节点
        {
            dfs(l1,i-1,l2+1,l2+i-l1);//递归左子树
            dfs(i+1,r1,l2+i-l1+1,r2);//递归右子树
            cout<<a[i];
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        //给定前序中序遍历,求后序遍历
        cin>>a>>b;
        int l=a.size();
        dfs(0,l-1,0,l-1);//全树区间,前序遍历从左到右,中序遍历从左到右
    }
    return 0;
}

标签:遍历,洛谷,后序,int,前序,American,USACO3.4,P1827,中序
From: https://www.cnblogs.com/Vivian-0918/p/16754460.html

相关文章

  • 洛谷 P7931
    以下标为横坐标,值为纵坐标,建立坐标系。然后会发现每个点的后继在其右上方。按照每个点LIS大小来分层,以样例\(3\)为例:注意到同层之间一定满足\(x\)递增\(y\)递......
  • [题解]洛谷 P4930、BZOJ 4221
    洛谷P4930考虑\(\varphi\)有什么性质,设\(x\)的质因数分解为\(\prod_{i=1}^mp_i^{a_i}\),那么\(n=\varphi(x)=\prod_{i=1}^m(p_i-1)\times\prod_{i=1}^mp_i^{a_i-1......
  • 洛谷 P4186
    首先对于一棵子树,肯定是放在这棵子树中深度最小的叶节点。那如何分析子树中深度最小的叶节点深度够不够小呢?我们看到,我们关注叶节点深度是为了看它能不能在Bessie从根......
  • 洛谷 CF550C Divisibility by Eight(DP/数论)
    遇事不决,小学数学。https://www.luogu.com.cn/problem/CF550C题目大意:给你一个位数不超过100的非负整数N(不含前导0)。你的任务是判断这个数字能否通过去掉其中......
  • 【树上背包】洛谷 P4516 [JSOI2018] 潜入行动
    P4516[JSOI2018]潜入行动省选/NOI-、树上背包计数题意略设状态为\(dp[u][j][0/1][0/1]\),u点子树放了j个装置,u点有没有放装置,u点有没有被监听的方案数。对......
  • 洛谷 P8557 炼金术 题解
    题目大意给定\(n\)种金属,放进\(k\)个熔炉,要求最终每种金属都要能从熔炉里拿出来,求熔炉炼金的方案数对\(998244353\)取模。分析从金属角度考虑。不难发现对于每......
  • 洛谷 P3388 【模板】割点(割顶)
    题目链接:https://www.luogu.com.cn/problem/P3388 【模板】割点(割顶)题目背景割点题目描述给出一个$n$个点,$m$条边的无向图,求图的割点。输入格式第一行输入两个......
  • 洛谷 P4840 解题报告
    洛谷P4840解题报告STEP1.题目大意求字符串\(S\)的所有循环同构中本质不同的回文子串数量的最大值。数据范围$|S|\leq1.5e6$STEP2.思路分析看到回......
  • 洛谷P3375 kmp字符串匹配
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inti,j,k,la,lb,kmp[1000005];chara[1000005],b[1000005];signedmain(){  scanf("%s%s",......
  • 洛谷 P1506 拯救oibh总部(DFS / 染色法)
    https://www.luogu.com.cn/problem/P1506题目描述给定n*m的图形,由*和0组成。让我们求出被*四面包围了的0的数量。输入#1450000000*000*0*000*00输出......