두 갈래 나무 2를 두루 돌아다니다 (제목 출처:nkoj:3909)

시간 제한: - MS;공간 제한: 65536KB;평가 설명: 1s;

문제 설명은 대문자로 구성된 두 개의 문자열 (길이는 26을 초과하지 않음), 하나는 두 갈래 나무의 앞차례 역행 서열, 하나는 두 갈래 나무의 중간차례 역행 서열을 나타냅니다. 이 두 갈래 나무의 뒷차례 역행 서열을 계산해 주십시오.

형식 입력

두 줄, 두 문자열은 각각 앞 순서와 중간 순서가 흐르는 순서를 나타낸다

출력 형식

한 줄, 문자열

샘플 입력

ABGKLMCHJF BLKMGAHCJF

샘플 출력

LMKGBHFJCA
하나의 기초적인 트리 유형의 응용은 간단하게 말하면 앞의 순서를 알고, 중간의 순서는 뒷의 순서를 구하고, 뒤의 순서는 뒷의 순서를 알고, 중간의 순서는 앞의 순서를 구하는 것을 보충한다.

생각:

왜냐하면 앞의 배열 방식은 뿌리, 왼쪽, 오른쪽이기 때문이다.중순 배열 방식: 왼쪽, 뿌리, 오른쪽;전번을stringa에 저장하고, 중번을stringb에 저장하면 우리는 알 수 있다:root=a[0];이때 중서는 좌우 트리 두 부분으로 나뉘어 왼쪽 트리의 루트와 오른쪽 트리의 루트를 찾는다.왜냐하면 먼저 왼쪽 나무부터 찾고 왼쪽 나무를 찾으면 오른쪽 나무를 찾습니다.마지막 출력 후순.
예: 만약에 a='ABC', b='BAC', 루트='A', 이때 b는'BA'와'AC'두 부분으로 나뉜다.A에서 B는 A 뒤에 있는 첫 번째 문자이기 때문에 B는 A의 왼쪽 트리입니다.이때 b에는 C만 남았다.C가 A의 오른쪽에 있기 때문에 C가 A의 오른쪽 나무다.
그러면 해법이 뚜렷해진다. 앞의 순서와 중간의 순서를 통해 나무의 형상을 얻어 뒷순서를 구한다.
코드는 아래와 같다(응··오류가 있어... 그런데 어디 시리즈가 틀렸는지 모르겠어. 큰 놈이 고쳐줬으면 좋겠어...

#include
#include
#include
using namespace std;
char a[1005],b[1005];
int t,tree[28][4],yes,maxn;
bool s[28];
void print(int x)
{
	if (0maxn)
		maxn=qt;
		s[a[i]-'A'+1]=1;
		yes=0;
		if (pan(a[gen],a[i]))
		tree[a[gen]-'A'+1][3]=qt;
		else
		tree[a[gen]-'A'+1][2]=qt;
		tree[qt][1]=a[gen]-'A'+1;
		if (yes==0)
		gen=i;
	}
	return ;
}
int main()
{
//	freopen("ceshi.in","r",stdin);
	int i;
	cin>>a;
	scanf("
");
	cin>>b;
	t=strlen(a);
	s[a[0]-'A'+1]=1;
	for (i=0;i<=t-1;i++)
	if (b[i]==a[0])
	{
		check(0,i);//  ； 
		break;
	}
	check(i,t-1);// ； 
	print(a[0]-'A'+1);
	return 0;
}

 
이 코드가 유난히 길다(emmm가 확실하다), 틀렸다(내 문제겠지···) 그래서 더 간단한 방법이 없을까?답은 중간에 나무를 세우는 과정을 생략하고 뒷순서를 직접 출력하는 것이다. 여기서 우리는 귀속을 운용했다.코드를 먼저 넣고 해석(응, AC 가능)

#include  
using namespace std;  

const int maxn = 10000 + 5;
char s1[maxn], s2[maxn];
int a, b, ans;
void build(int n, char *str1, char *str2) {
	if(n <= 0) return;
	int s = strchr(str2, str1[0]) - str2;
	build(s, str1 + 1, str2);
	build(n - 1 - s, str1 + s + 1, s + str2 + 1);
	cout << str1[0];
}
int main() {
	cin >> s1 >> s2;
	int len = strlen(s1);
	build(len, s1, s2);
	cout << endl;
	return 0;
}

확인:
s1 저장 전 순서, s2 저장 중 순서, s1과 s2의 길이가 똑같기 때문에 우리는 s1의 길이만 측정하면 된다.주 함수는 대략 입력-측장-출력으로 나눌 수 있으며, 관건적인 부분은build 함수에 있다.
먼저 매개 변수 부분을 보면 n은 현재의 루트 노드(root)를 대표하고 *str1은 지침 함수이며 str1의 특정한 길이의 문자이며 *str2는 같은 이치이다. (잘 모르는 친구는 먼저 지침을 이해할 수 있다.)
첫 번째 단계: n==0시에 돌아왔습니다. 이때 대표는 왼쪽 아들이나 오른쪽 아들을 찾았습니다.
첫 번째 단계를 만족시키지 못하면 두 번째 단계를 실행합니다. str2에서str1의 첫 번째 문자의 위치를 찾고 s에 존재합니다. (주: 되돌아오는 것은 주소입니다. str2를 빼면 되돌아오는 문자가 있는 위치를 의미합니다.)그리고 귀속 함수-->왼쪽 나무 찾기-->나그네 나무 찾기.//이 과정은 사실상 은형으로 나무를 세우지만 보존하지 않는다.
3단계:str1의 현재 첫 번째 문자를 잃었습니다.//뒤에 있는 세 가지 조작은 실제적으로 트리에 대한 출력 후 순서의 조작이다. 만약에 중간 순서나 앞 순서를 출력하려면str1의 위치를 바꾸면 실현할 수 있다.(또는 두 개의 귀속 함수 뒤에 있기 때문에 출력 후 순서emmmm라고 할 수도 있다.)
텍스트 설명이 명확하지 않을 수도 있습니다. 다음은 거리를 설명합니다. (그림을 삽입하지 않는 저는 아마 문자로만 qwq를 사용할 수 있을 것입니다. 양해해 주십시오.)
intmain: 이미 알고 있는 전순: ABDEC, 중순: DBEAC, 측정된 길이 len=5;함수 진행하기;
build(1(root)): (전제: n=5, str1="ABDEC", str2="DBEAC") n>0으로 인해str1[0](A)를 찾아 s=3을 얻는다.귀속 1 들어가기;
build(1(left): (전제: n=3, str1="BDEC", str2="DBEAC") n>0 때문에str1[0](B)를 찾아 s=1을 얻는다.귀속 1 들어가기;
n=0이 될 때까지 위의 작업을 반복합니다(즉, D를 찾을 때).
build(2(left): (전제: n=0, str1='EC', str2='DBEAC') n=0, return;(n=1,str1='DEC','str2='DBEAC')의 위치로 돌아가서 귀속2에 들어갑니다.
build(2(right)): (전제: n=1-0-1=0, str1='DEC'+0+1='EC', str2='DBEAC'+0+1='BEAC') 인n=0, return;반환(n=1,str1='DEC','str2='DBEAC'), 출력.
상술한 조작을 반복하다 (대략 과정은 이렇다)
요약:
매번 코드를 쓸 때마다 제 코드가 이렇게 아름다워요. 그리고 현지 AC가 WA를 제출해서 어렵게 한 문제를 냈는데 다른 사람이 물문제qwq라고 했어요.자신의 귀속은 여전히 비교적 부족하다. 아무래도 문제를 많이 풀어야 할 것 같다emmmm.그러나 코드 기초가 강하지 않은 경우도 있다. 평소에 쓰는 블로그가 너무 적어서 경험이 부족하다.