The 14th Blue Bridge Cup Training Camp——Practice and problem-solving stage (disorder stage)-ALGO-380 map drawing
Table of contents
The Sixth - The Thirteenth Provincial Competition
The sixth - the twelfth provincial competition
foreword
During this period of time, I will publish all non-VIP topics on the official website of the Blue Bridge Cup, so that everyone can easily search. All topics will be written in several languages to help you provide an idea. Of course, an idea is just an idea. Don't just look at the answer and think you will, this method is basically difficult for you to grow. Growth is to find your own problem-solving ideas in the process of thinking, and you must first rely on the problem-sea tactics to make your own A certain amount of training in problem-solving thinking. Without this process of quantitative change to qualitative change, you will find that your speed of solving problems that require relatively thinking will be very slow. This thinking process cannot even be drawn in your brain without paper and pen. Outline it, so when we study in the early stage, we learn other people's thinking and transform our thinking into our own mode in our own way. We listen to the tongue, but we rely on quantity to stack the way of thinking. It starts very simply, with a little understanding of data structures, violence, dichotomy, etc., and grows step by step. There are many data structures, generally just a few, such as linear tables, trees, graphs, and others. Sequence lists and linked lists are also linear lists. Of course, stacks, queues, and strings all belong to linear lists. I won’t subdivide them here one by one. The Lanqiao Cup is relatively friendly to junior colleges. For example, three-point enumeration, discretization, graphs, complex data structures, and statistics are not tested. We will find simple questions for one or two hundred, and then proceed For the training of medium topics, when we master the depth search and breadth search and then rely on dynamic programming, we will gradually master various laws, and with the rules, we can boldly grow some more difficult topics. Explain that you must do it step by step, and don't think that you can solve the problem directly, it's just to persuade yourself to quit. Come on, normal heart, step by step forward.
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
answer:
C language
#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;
}C++ language
#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;
}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);
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);
}
}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[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))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 |