第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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))