【习题 6-3 UVA - 536】 Tree Recovery

在这里输入题意

【题解】

递归题

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 300;

string s1, s2;

int n, idx;

int g[N][2];

int dfs(int l, int r) {

	int temp = l;

	for (int i = l; i <= r; i++) {

		if (s2[i] == s1[idx]) {

			temp = i;

		}

	}

	idx++;

	if (l <= temp - 1) {

		g[(int)s2[temp]][0] = dfs(l, temp-1);

	}

	if (temp + 1 <= r) {

		g[(int)s2[temp]][1] = dfs(temp + 1, r);

	}

	return s2[temp];

}

void dfs2(int x) {

	if (g[x][0]) {

		dfs2(g[x][0]);

	}

	if (g[x][1]) {

		dfs2(g[x][1]);

	}

	cout << (char)x;

}

int main() {

	#ifdef LOCAL_DEFINE

		freopen("F:\\c++source\\rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0), cin.tie(0);

	while (cin >> s1 >> s2) {

		memset(g, 0, sizeof g);

		n = s1.size();

		idx = 0;

		dfs2(dfs(0, n - 1));

		cout << endl;

	}

	return 0;

}

巴特西

【习题 6-3 UVA - 536】 Tree Recovery

最新文章

热门文章