Solve

USACO 3.4.2 Heritage

题目解答

分治策略：首先根据常识凡是中序+前序，中序+后序均可确定唯一二叉树。前序+后序不可确定。因此我们根据中序+前序先构造出二叉树，然后输出即可。构造方法是：因为前序遍历的第一个一定是根，那么接着找到根在中序遍历的位置。在中序遍历中左边的就是左子树。右边的就是右子树。然后下放左右子树和相应的前序遍历接着做，直到没有左右子树为止。(如图)

USACO 3.4.2

运行结果

Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.000 secs, 2932 KB]
Test 2: TEST OK [0.000 secs, 2932 KB]
Test 3: TEST OK [0.000 secs, 2932 KB]
Test 4: TEST OK [0.011 secs, 2932 KB]
Test 5: TEST OK [0.011 secs, 2932 KB]
Test 6: TEST OK [0.000 secs, 2932 KB]
Test 7: TEST OK [0.011 secs, 2932 KB]
Test 8: TEST OK [0.011 secs, 2932 KB]
Test 9: TEST OK [0.011 secs, 2932 KB]
All tests OK.
YOUR PROGRAM (‘heritage’) WORKED FIRST TIME! That’s fantastic
– and a rare thing. Please accept these special automated
congratulations.

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<fstream>
#include<cstring>
using namespace std;
ofstream fout ("heritage.out",ios::out);
ifstream fin ("heritage.in",ios::in);
struct String{
    int len;
    char word[27];
}str[2];
struct subteee{
    char key;
    int lch,rch;
}tree[27];
int tot=1;
void backout(int pos){ //后序遍历
    if(tree[pos].lch) backout(tree[pos].lch);
    if(tree[pos].rch) backout(tree[pos].rch);
    fout<<tree[pos].key;
}
void find(char work[],int len, int pos,int index){ //构造二叉树
    tree[index].key=str[0].word[pos];
    char temp[27];
    for(int i=0;i<len;i++) if(work[i]==tree[index].key){
        if(i!=0){
            for(int j=0;j<i;j++) temp[j]=work[j];
            tree[index].lch=++tot;
            find(temp,i,pos+1,tot);
        }
        if(i!=len-1){
            for(int j=i+1;j<len;j++) temp[j-i-1]=work[j];
            tree[index].rch=++tot;
            find(temp,len-i-1,pos+i+1,tot);
        }
        break;
    }
}
int main()
{
    fin>>str[1].word>>str[0].word;
    str[1].len=strlen(str[1].word);
    str[0].len=strlen(str[0].word);
    find(str[1].word,str[1].len,0,tot);
    backout(1);
    fout<<endl;
    return 0;
}

后记

本文是百度空间的移植，附：全部USACO题目解答。