第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-380 绘制地图

#include <stdio.h>
int a[100001],b[100001],c[100001],k=0;
void fac(int l,int r,int t,int map[])
{
	if(l<=r)
	{
		int j=t-(r-l);
		int i=map[a[j]];
		c[k++]=b[i];
		fac(i+1,r,t,map);
		fac(l,i-1,t-(r-(i+1)+1),map);
	}
}
int main()
{
	int i,n,map[100001];
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]),map[b[i]]=i;
	fac(1,n,n,map);
	for(i=k-1;i>=0;i--)
		printf("%d ",c[i]);
	return 0;
}

#include<stdio.h>
#include<math.h>
#include<algorithm>
int n,m,i,j,k,ans;
int sl[100005],sr[100005],a[100005],c[100005],b[100005],s;
void ss(int l,int r,int fa)
{
	if (l+1==r)return;
	if (c[a[i]]>=r||c[a[i]]<=l) return;
	int lo=c[a[i]],de=a[i];
	if (c[fa]==r) sl[fa]=a[i]; else sr[fa]=a[i];
	i++;
	ss(l,lo,de);
	ss(lo,r,de);
}
void pr(int o)
{
	if (sl[o]!=0) pr(sl[o]);
	if (sr[o]!=0) pr(sr[o]);
	printf("%d ",o);
}
int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for (i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		c[b[i]]=i;
	}
	i=2; 
	s=c[a[1]];
	ss(0,s,a[1]);ss(s,n+1,a[1]);
	pr(a[1]);
	return 0;
}

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;

public class Main {
	
	/*
	 * 通过前序遍历数组和中序遍历数组直接得出后续遍历数组
	 */
	public void poCons(int[] pre, int[] mid)
	{
		Stack<Integer[]> s = new Stack<Integer[]>();
		Set<Integer> set = new HashSet<Integer>();
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for(int i=0;i<mid.length;i++)
			map.put(mid[i], i);
		
		set.add(-1);
		set.add(pre.length);
		for(int i:pre)
		{
			int loc = map.get(i);
			set.add(loc);
			s.add(new Integer[] {i, loc});
			while(!s.isEmpty() && set.contains(s.peek()[1]-1) && set.contains(s.peek()[1]+1))
				System.out.print(s.pop()[0]+" ");
		}
	}
	
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] pre = new int[n];
		int[] mid = new int[n];
		
		for(int i=0; i<n; i++)
			pre[i] = scan.nextInt();
		
		for(int i=0; i<n; i++)
			mid[i] = scan.nextInt();
		
		new Main().poCons(pre, mid);
	}
}

class BTree:
    left = None
    right = None

    def __init__(self, v):
        self.val = v

n = int(input())
front_input = list(input().split())
front_seq = []
for i in range(n):
    front_seq.append(int(front_input[i]))

mid_input = list(input().split())
mid_seq = []
for i in range(n):
    mid_seq.append(int(mid_input[i]))
root = BTree(front_seq[0])
idx = 0
stack = [root]
for i in range(1, len(front_seq)):
    val = front_seq[i]
    node = stack[-1]
    if node.val != mid_seq[idx]:
        node.left = BTree(val)
        stack.append(node.left)
    else:
        while stack and stack[-1].val == mid_seq[idx]:
            node = stack.pop()
            idx += 1
        node.right = BTree(val)
        stack.append(node.right)

s = []
res = []
cur = root
while cur or s:
    while cur:
        res.append(str(cur.val))
        s.append(cur)
        cur = cur.right
    if s:
        cur = s.pop()
        cur = cur.left

res.reverse()
print(" ".join(res))