JLU2020数据结构第三次实验
目录
一、二叉树最长路径
题目：
给定一棵二叉树T，求T中的最长路径的长度，并输出此路径上各结点的值。若有多条最长路径，输出最右侧的那条。
输入格式:
第1行，1个整数n，表示二叉树有n个结点， 1≤n≤100000.
第2行，2n+1个整数，用空格分隔，表示T的扩展先根序列， -1表示空指针，结点用编号1到n表示。
输出格式:
第1行，1个整数length，length表示T中的最长路径的长度。
第2行，length+1个整数，用空格分隔，表示最右侧的最长路径。
输入样例:
在这里给出一组输入。例如：
5
1 2 -1 -1 3 4 -1 -1 5 -1 -1
输出样例:
在这里给出相应的输出。例如：
10
11
12
思路：
先是非常基础的递归建树。设置一个数组road用来保存某一条路，变量length记录该条路的长度，还有一个数组longroad保存目前见到的最长的路，变量longlength记录最长路的长度。每遇到一个结点就把它保存在road数组里并length+1，如果遇到一个叶子结点，说明该条路已经走到了尽头，那么就比较当前路与最长路的长度，如果当前路的长度大于或等于最长路的长度，那么就把当前路的数据复制到最长路里并更新最长路长度。特别的是，若有多条最长路，题目要求的是最右边的那条，所以如果当前路跟最长路一样长时也要更新，因为找路是从左往右找的。
代码：
#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;
}
二、森林的层次遍历
题目：
给定一个森林F，求F的层次遍历序列。森林由其先根序列及序列中每个结点的度给出。
输入格式:
第1行，1个整数n，表示森林的结点个数， 1≤n≤100000.
第2行，n个字符，用空格分隔，表示森林F的先根序列。字符为大小写字母及数字。
第3行，n个整数，用空格分隔，表示森林F的先根序列中每个结点对应的度。
输出格式:
1行，n个字符，用空格分隔，表示森林F的层次遍历序列。
输入样例:
在这里给出一组输入。例如：
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
输出样例:
在这里给出相应的输出。例如：
A M B C G H N D E F I L J K
思路：
这题貌似知道怎么写，但又不会写。最终还是看了同学的思路写了一遍。这题可以建树写也可以不建树写，这里说下建树的写法，更加通俗易懂。建立一个vector数组，每个数组保存对应结点的子节点，vector[0]保存每棵树的根节点。
因为是森林所以要循环建立多棵树。先看如何建立一棵树：设置一个变量poi指向当前正在操作的结点。先把在循环外将树的根节点放进数组，然后该节点度为多少就循环多少次，让poi加1把下一个结点（该节点一定是当前结点的子节点，再往后可能是子节点的子节点，因为是先根遍历）放入该节点的子节点数组，然后递归调用建树函数去建立子树。（可以只看一层遍历，一个子树建立完后下一个结点就是自己的另一个子节点了。）这样一棵树就建完了。
怎么建森林：poi是全局变量，指向当前操作的结点，如果poi等于结点总数n时说明森林建立完了，所以循环可以设置为while（poi<=n）。然后调用建立一个树的函数。
森林建立完毕后就很轻松了，就是对树的bfs。对于一个树的bfs一开始现将根节点压进去；对森林的bfs则需要把所有的根节点先压进去，然后就是对树的bfs了。bfs需要使用队列，遇到一个结点把该节点的子节点全部入队，自己出队打印就行了。
代码：
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
char ch[100001];
int noderank[100001];
vector<int> forest[100001];
int n;
int poi=1;//指针
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";
}
}
}
三、纸带切割
题目：
有一条细长的纸带,长度为 L 个单位，宽度为一个单位。现在要将纸带切割成 n 段。每次切割把当前纸带分成两段，切割位置都在整数单位上，切割代价是当前切割纸带的总长度。每次切割都选择未达最终要求的最长纸带切割，若这样的纸带有多条，则任选一条切割。如何切割，才能完成任务，并且总代价最小。
输入格式:
第1行，1个整数n，表示切割成的段数， 1≤n≤100000.
第2行，n个整数Li，用空格分隔，表示要切割成的各段的长度，1≤Li≤200000000，1≤i≤n.
输出格式:
第1行，1个整数，表示最小的总代价。
第2行，若干个整数，用空格分隔，表示总代价最小时每次切割的代价。
输入样例:
在这里给出一组输入。例如：
5
5 6 7 2 4
输出样例:
在这里给出相应的输出。例如：
54
24 13 11 6
思路：
这题比较难的是要先把题意读懂。宽度为1，只能切割单位长度，所以就是说只能横着切。每次切割的代价是被切割的纸带的长度。要注意的是这一题输入的是切完后的结果让我们求怎么切。我们得想到所有结果加起来就是一开始的纸带长度，因为要求最小代价，所以就用到了贪心思维，每次取最小的纸带切。但这题最重要的是要想到是在考哈夫曼树，每次取最小的两段合并。每次取最小可以扫描一遍也可以建堆，不过扫描大抵是会被卡的因此选择建一个最小堆。每次操作做两次取最小操作，然后将合并的那个结点再放入堆中。我还设置了一个外数组，合并后的结点也放进去，最后要输出的结果就是他们了。
自己第三题和第四题思路都正确了，尤其是这一题。不过当时因为堆操作写的有问题导致没做出来，所以就是熟练度不够。这也导致这次实验后堆的操作刻进我的DNA里了。
代码：
#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;
}
四、序列乘积
题目：
两个递增序列A和B,长度都是n。令 Ai 和 Bj 做乘积，1≤i,j≤n.请输出n*n个乘积中从小到大的前n个。
输入格式:
第1行，1个整数n，表示序列的长度， 1≤n≤100000.
第2行，n个整数Ai，用空格分隔，表示序列A，1≤Ai≤40000，1≤i≤n.
第3行，n个整数Bi，用空格分隔，表示序列B，1≤Bi≤40000，1≤i≤n.
输出格式:
1行，n个整数，用空格分隔，表示序列乘积中的从小到大前n个。
输入样例:
在这里给出一组输入。例如：
5
1 3 5 7 9
2 4 6 8 10
输出样例:
在这里给出相应的输出。例如：
2 4 6 6 8
思路：
这题我一开始的想法是建一个最大堆，ai*bi前n个元素直接入堆然后维护一下堆就行了。再往后的元素，得跟堆顶也就是最大的元素比较，如果堆顶比较大的话就把堆顶变为将要入堆的元素。这样能保证堆里始终有n个元素并且是前n小的数。这个方法确实是可以做出来的，但老师说这样一定会超时。其实我一开始没看到是两个单调有序的数组所以认为这样不会超但还是因为堆写的有问题部分分都没拿到多少。
因此还是炫神，yyds！想到用结构体优先队列来写。先把第一列或第一行的所有元素都放进去（n^2个数里最小的一定在这n个数里，因为数组是单调的），然后把最小的元素出堆，并把这个元素后面的元素入堆，再找最小的，此时就是第二小的了。以此类推做n次就行了。
这题比较关键的是想到用结构体堆，然后如果是自己手撕的话可能没问题。但如果用stl的话就不太会了，因为不知道怎么比较。看了同学的代码学会了要自己重载一下比较大小的操作符。
代码：
#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;
}