The third experiment of JLU2020 data structure
catalogue
The third experiment of JLU2020 data structure
1, Longest path of binary tree
2, Hierarchical traversal of forest
1, Longest path of binary tree
Title:
Given a binary tree T, find the length of the longest path in T, and output the value of each node on this path. If there are multiple longest paths, output the rightmost one.
Input format:
The first line, an integer n, indicates that the binary tree has n nodes, 1 ≤ n ≤ 100000
Line 2, 2n+1 integers, separated by spaces, represents the extended first root sequence of T, - 1 represents the null pointer, and nodes are represented by numbers 1 to n.
Output format:
Line 1, an integer length, which represents the length of the longest path in T.
Line 2, length+1 integers, separated by spaces, represents the longest path on the far right.
Input sample:
A set of inputs is given here. For example:
5
1 2 -1 -1 3 4 -1 -1 5 -1 -1
Output example:
The corresponding output is given here. For example:
10
11
12
Idea:
The first is very basic recursive tree building. Set an array road to save a road. The variable length records the length of the road. There is also an array longroad to save the longest road seen so far, and the variable longlength records the length of the longest road. Every time you encounter a node, save it in the road array with length+1. If you encounter a leaf node, it indicates that the road has come to an end, then compare the length of the current road with the longest road. If the length of the current road is greater than or equal to the length of the longest road, copy the data of the current road to the longest road and update the length of the longest road. In particular, if there are multiple longest roads, the title requires the one on the far right. Therefore, if the current road is as long as the longest road, it should also be updated, because the road is found from left to right.
code:
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *left;
struct node *right;
}node;
void longestroad(node *root,int *road,int length,int *longroad,int *longlength){
if(root!=NULL){
if(root->left==NULL&&root->right==NULL){
road[length++]=root->data;
if(length>=*longlength){
int i;
for(i=0;i<=length-1;i++){
longroad[i]=road[i];
}
*longlength=length;
}
}
else{
road[length++]=root->data;
longestroad(root->left,road,length,longroad,longlength);
longestroad(root->right,road,length,longroad,longlength);
}
}
return;
}
node* build(){
node *root;
int x;
scanf("%d",&x);
if(x==-1)return NULL;
else{
root=(node*)malloc(sizeof(node));
root->data=x;
root->left=build();
root->right=build();
}
return root;
}
int main(){
int n;
scanf("%d",&n);
node *root;
root=build();
int road[100001]={0};
int longroad[100001]={0};
int longlength=0;
longestroad(root,road,0,longroad,&longlength);
int i;
printf("%d\n",longlength-1);
for(i=0;i<=longlength-1;i++){
printf("%d",longroad[i]);
if(i<longlength-1)printf(" ");
}
printf("\n");
return 0;
}
2, Hierarchical traversal of forest
Title:
Given a forest F, find the hierarchical traversal sequence of F. The forest is given by its first root sequence and the degree of each node in the sequence.
Input format:
The first line, an integer n, represents the number of nodes in the forest, 1 ≤ n ≤ 100000
Line 2, n characters, separated by spaces, represents the first root sequence of forest F. Characters are upper and lower case letters and numbers.
The third line, n integers, separated by spaces, represents the corresponding degree of each node in the first root sequence of forest F.
Output format:
1 line, n characters, separated by spaces, representing the hierarchical traversal sequence of forest F.
Input sample:
A set of inputs is given here. For example:
14
A B C D E F G H I J K L M N
4 0 3 0 0 0 0 2 2 0 0 0 1 0
Output example:
The corresponding output is given here. For example:
A M B C G H N D E F I L J K
Idea:
It seems that I know how to write this question, but I can't write it. Finally, I read the ideas of my classmates and wrote them again. This question can be written with or without Jianshu. Here is the way to write Jianshu, which is more easy to understand. Create a vector array. Each array saves the child nodes of the corresponding node, and vector[0] saves the root node of each tree.
Because it is a forest, it is necessary to cycle and build multiple trees. Let's first look at how to build a tree: set a variable poi to point to the node currently under operation. First, put the root node of the tree outside the loop into the array, and then cycle the number of times according to the degree of the node. Let poi add 1 to put the next node (the node must be the child node of the current node, and then it may be the child node of the child node, because it is traversed by the root first) into the child node array of the node, and then recursively call the tree building function to build the child tree. (you can only look at the traversal of one layer. After a subtree is established, the next node is another child node of your own.) So a tree will be built.
How to build a forest: poi is a global variable that points to the node of the current operation. If poi is equal to the total number of nodes n, it means that the forest has been established, so the loop can be set to while (poi < = n). Then we call a function to build a tree.
After the forest is built, it will be very easy, that is, the bfs of trees. For the bfs of a tree, press the root node in at the beginning; For forest bfs, you need to press all the root nodes first, and then the tree bfs. bfs needs to use queues. When a node is encountered, all the child nodes of the node are queued, and they can print out of the queue.
code:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
char ch[100001];
int noderank[100001];
vector<int> forest[100001];
int n;
int poi=1;//Pointer
void buildtree(int m){
int i;
for(i=0;i<noderank[m];++i){
++poi;
forest[m].push_back(poi);
buildtree(poi);
}
}
void buildforest(){
while(poi<=n){
forest[0].push_back(poi);
buildtree(poi);
++poi;
}
}
int main(){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
scanf("%c",&ch[i]);
scanf("%c",&ch[i]);
}
for(i=1;i<=n;i++){
scanf("%d",&noderank[i]);
}
buildforest();
queue<int> que;
que.push(0);
int tmp;
while(!que.empty()){
tmp=que.front();
que.pop();
for(vector<int>::iterator it=forest[tmp].begin();it!=forest[tmp].end();it++){
que.push(*it);
}
if(tmp!=0){
cout<<ch[tmp];
if(que.empty()==0)cout<<" ";
else cout<<"\n";
}
}
}
3, Paper tape cutting
Title:
There is a slender paper tape with a length of L units and a width of 1 unit. Now cut the tape into n segments. Each cutting divides the current paper tape into two sections, and the cutting position is in integer units. The cutting cost is the total length of the current cutting paper tape. The longest paper tape that fails to meet the final requirements shall be selected for each cutting. If there are multiple such paper tapes, any one shall be selected for cutting. How to cut, in order to complete the task, and the total cost is the least.
Input format:
The first line, an integer n, represents the number of segments cut, 1 ≤ n ≤ 100000
The second line, n integers Li, separated by spaces, indicates the length of each segment to be cut, 1 ≤ Li ≤ 200000000, 1 ≤ i ≤ n
Output format:
The first line, an integer, represents the minimum total cost.
In line 2, several integers separated by spaces represent the cost of each cutting when the total cost is the smallest.
Input sample:
A set of inputs is given here. For example:
5
5 6 7 2 4
Output example:
The corresponding output is given here. For example:
54
24 13 11 6
Idea:
The difficulty of this problem is to read the meaning of the problem first. If the width is 1, only the unit length can be cut, so it can only be cut horizontally. The cost of each cut is the length of the paper tape being cut. It should be noted that the input of this question is the result after cutting. Let's find out how to cut it. We have to think that all the results add up to the length of the paper tape at the beginning. Because the minimum cost is required, we use greedy thinking to cut the smallest paper tape every time. But the most important thing to think about this question is to merge the smallest two segments in the Kaufman tree. You can scan the minimum every time or build a heap, but the scan will be blocked, so you choose to build a minimum heap. Take the minimum twice for each operation, and then put the merged node into the heap. I also set up an outer array, and the merged nodes are also put in. The final output is them.
My thoughts on the third and fourth questions are correct, especially this one. However, at that time, there was a problem with the writing of heap operation, so it was not proficient enough. This also led to the operation of the reactor after this experiment being engraved into my DNA.
code:
#include<stdio.h>
#include<stdlib.h>
void down(long long *heap,int hen,int x){
int y=x,z;
long long tmp;
while((2*y<=hen&&heap[y]>heap[2*y])||(2*y+1<=hen&&heap[y]>heap[2*y+1])){
z=2*y;
if(2*y+1<=hen&&heap[2*y+1]<heap[2*y])z++;
tmp=heap[y];
heap[y]=heap[z];
heap[z]=tmp;
y=z;
}
}
void up(long long *heap,int hen,int x){
int y=x;
long long tmp;
while(y>1&&heap[y]<heap[y/2]){
tmp=heap[y];
heap[y]=heap[y/2];
heap[y/2]=tmp;
y/=2;
}
}
long long heap[100001];
long long weight[100001];
long long tmp;
long long min1,min2;
long long max,minmin;
int main(){
int n;
scanf("%d",&n);
heap[0]=0;
int hen=n;
int poi=1;
int i;
for(i=1;i<=n;i++){
scanf("%lld",&heap[i]);
}
if(n==1){printf("%lld\n",heap[0]);return 0;}
for(i=1;i<=hen;++i){
up(heap,i,i);
}
while(hen>1){
min1=heap[1];
tmp=heap[hen];
heap[hen]=heap[1];
heap[1]=tmp;
--hen;
down(heap,hen,1);
min2=heap[1];
tmp=heap[hen];
heap[hen]=heap[1];
heap[1]=tmp;
--hen;
down(heap,hen,1);
minmin=min1+min2;
max+=minmin;
weight[poi++]=minmin;
++hen;
heap[hen]=minmin;
up(heap,hen,hen);
}
printf("%lld\n",max);
for(i=poi-1;i>=1;--i){
printf("%lld",weight[i]);
if(i>1)printf(" ");
}
printf("\n");
return 0;
}
4, Sequence product
Title:
Two increasing sequences, A and B, are n in length. Let Ai and Bj be the product, 1 ≤ i,j ≤ n. please output the first n of the n*n products from small to large.
Input format:
The first line, an integer n, represents the length of the sequence, 1 ≤ n ≤ 100000
In line 2, n integers Ai, separated by spaces, represent sequence A, 1 ≤ Ai ≤ 40000, 1 ≤ i ≤ n
In line 3, n integers Bi, separated by spaces, represent sequence B, 1 ≤ Bi ≤ 40000, 1 ≤ i ≤ n
Output format:
1 line, n integers, separated by spaces, indicating the first N in the sequence product from small to large.
Input sample:
A set of inputs is given here. For example:
5
1 3 5 7 9
2 4 6 8 10
Output example:
The corresponding output is given here. For example:
2 4 6 6 8
Idea:
At the beginning of this problem, my idea was to build a maximum heap. The first n elements of ai*bi are directly put into the heap, and then maintain the heap. Later elements must be compared with the top of the heap, that is, the largest element. If the top of the heap is relatively large, the top of the heap will be changed into the element to be put into the heap. This ensures that there are always n elements in the heap and the first n are small. This method can really be done, but the teacher said it will definitely time out. In fact, I didn't see two monotonous and orderly arrays at the beginning, so I think it won't exceed, but I didn't get much points because of the problem of heap writing.
So still dazzle God, yyds! Think of using structure priority queue to write. First put all the elements in the first column or row (the smallest of n^2 must be in this n number, because the array is monotonous), then put the smallest element out of the heap, put the elements behind this element into the heap, and then find the smallest one. At this time, it is the second smallest one. And so on, just do it n times.
The key to this problem is to think of stacking with structures, and then if you tear them by hand, it may be no problem. But if you use stl, you won't be very good, because you don't know how to compare. After reading the classmate's code, I learned to overload the size comparison operator myself.
code:
#include<iostream>
#include<queue>
using namespace std;
struct node{
int x;
int y;
int data;
bool operator<(const node& p)const
{
return data > p.data;
}
node(int m,int n,int val):x(m),y(n),data(val){};
};
int main(){
priority_queue<node> que;
int n;
scanf("%d",&n);
int *a,*b;
a=new int[n+1];
b=new int[n+1];
int i;
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(i=1;i<=n;++i){
scanf("%d",&b[i]);
}
int *flag;
flag=new int[n+1];
for(i=1;i<=n;++i){
que.push(node(1,i,a[1]*b[i]));
}
for(i=1;i<=n;++i){
node tmp=que.top();
printf("%d",tmp.data);
que.pop();
if(tmp.x<n){que.push(node(tmp.x+1,tmp.y,a[tmp.x+1]*b[tmp.y]));}
if(i!=n)printf(" ");
}
printf("\n");
return 0;
}