# The 14th Blue Bridge Cup Training Camp——Practice and problem-solving stage (disorder stage)-ALGO-380 map drawing

## The 14th Blue Bridge Cup Training Camp——Practice and problem-solving stage (disorder stage)-ALGO-380 map drawing

The 14th Blue Bridge Cup Training Camp——Practice and problem-solving stage (disorder stage)-ALGO-380 map drawing

foreword

draw a map

C language

C++ language

Java language

Python language

Summarize

The Sixth - The Thirteenth Provincial Competition

The sixth - the twelfth provincial competition

## draw a map

resource constraints

Memory limit: 256.0MB C/C++ time limit: 1.0s Java time limit: 3.0s Python time limit: 5.0s

Problem Description

Recently, WYF is preparing to visit his point card factory. The manager of WYF Group needs to help WYF design the "sightseeing" route. Now, cyanogen trash knows a few things: 1. The point card factory of WYF constitutes a binary tree. 2. There are n factories in total. 3. He needs to list the points on the tree by postorder traversal before he can draw the map. Fortunately, recently his subordinates gave him the data of pre-order traversal and in-order traversal. However, Cyan Garbage has to help Zexuan solve some problems recently, so he doesn't have time. Please help him and complete this task for him. Due to some special requirements of cyanide waste, the WYF tour route will be a post-order traversal of this tree.

input format

There is an integer n in the first line, indicating that there are a total of n factories. The second line contains n integers, indicating preorder traversal. The third line contains n integers, indicating in-order traversal.

output format

Output a total of one line, including n integers, for post-order traversal.

sample input

8 1 2 4 5 7 3 6 8 4 2 7 5 1 8 6 3

sample output

4 7 5 2 8 6 3 1

Data Size and Conventions

0<n<100000,. Guarantee that pre-order traversal and in-order traversal are legal, and both are 1~n

## C language

```#include <stdio.h>
int a,b,c,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;
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;
}```
copy

## C++ language

```#include<stdio.h>
#include<math.h>
#include<algorithm>
int n,m,i,j,k,ans;
int sl,sr,a,c,b,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];
ss(0,s,a);ss(s,n+1,a);
pr(a);
return 0;
}```
copy

## Java language

There are different methods for scanning input content, but the usage is the same as Scanner.

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

public class Main {

/*
* Directly obtain the subsequent traversal array through the pre-order traversal array and the in-order traversal array
*/
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);

for(int i:pre)
{
int loc = map.get(i);
while(!s.isEmpty() && set.contains(s.peek()-1) && set.contains(s.peek()+1))
System.out.print(s.pop()+" ");
}
}

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);
}
}```
copy

## Python language

It is relatively concise, but requires a good understanding of some Python syntax, especially familiarity with list comprehension.

```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)
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))```
copy

## Summarize

There is no result that can be obtained without paying. We are all moving forward with heavy loads. The final result has a certain relationship with our innate brain power, but a large part of it depends on our acquired efforts. About 5 months, the event of really brushing the questions is only 2 months. In 2 months, recall whether you have really brushed the questions seriously. If you really exhausted all your energy to work hard, then I believe your final score It will definitely satisfy you, come on.

## The Sixth - The Thirteenth Provincial Competition

All the topics have been explained, and the most difficult ones have supporting videos. The video provider is Mr. Gong Jiayi of the 2020 class.

Group C of the 6th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123284163

Group C of the 7th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123285783

Group C of the 8th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123302677

Group C of the Ninth Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123303285

Group C of the 10th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123319090

Group C of the 11th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123320205

The first set of Group C of the 12th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123413141

The second set of Group C of the 12th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/123413271

Group C of the 13th Java Provincial Competition

https://laoshifu.blog.csdn.net/article/details/128891276

## The sixth - the twelfth national competition

All questions have solutions, some of the 10th questions are not the optimal solution, and at least 20% of the data is run.

Group C of the 6th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123440705

Group C of the 7th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123442982

Group C of the 8th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123443626

Group C of the Ninth Java National Competition

https://laoshifu.blog.csdn.net/article/details/123443908

Group C of the 10th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123444946

Group C of the 11th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123445601

Group C of the 12th Java National Competition

https://laoshifu.blog.csdn.net/article/details/123446589

Posted by mobilephp on Thu, 16 Feb 2023 19:27:29 +1030