题解：P1030 [NOIP 2001 普及组] 求先序排列

Doraeman · 2025-08-25 20:18:23 · 题解

这道题是求先序排列，和 P1827 [USACO3.4] 美国血统 American Heritage 非常相似（那道题求后序排列）。

请看我关于 P1827 的文章，并自行举一反三。
此处给出 AC 代码 + 注释。

代码

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

void dfs(string x, string y){
    if(x.size() > 0){
        char root = y[y.size()-1];
        cout << root;

        int k = x.find(root);
        dfs(x.substr(0,k), y.substr(0,k));
        dfs(x.substr(k+1), y.substr(k,x.size()-k-1));
    }
}

int main(){
    string mid, back;
    cin >> mid >> back;
    dfs(mid, back);
}