代码长度限制 16 KB
时间限制 100 ms
内存限制 5 MB
给定一棵二叉树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
在这里给出一组输出。例如：
2
1 3 5
方法一：不建树，用vector保存当前路径，并随数据输入不断更新，当长度足够大时保存为候选路径。此方法不稳定，频繁保存为候选路径非常耗时。
方法二：建树，加个父节点。记录当前路径长度，保存为候选路径时只需保存该路径的最终结点。当树建完，由保存的路径的最终结点开始，不断访问他的祖先，就能得到最长路径。
#include<iostream>
#include<stack>
using namespace std;
struct node{
int right;
int left;
int father;
};
int pasw;
int nasw=-1;
int nasw0=-1;
node*a;
void build(int x){
nasw0++;
int s1;
scanf("%d",&s1);
if(s1!=-1){
a[x].left=s1;
a[s1].father=x;
build(s1);
}
int s2;
scanf("%d",&s2);
if(s2!=-1){
a[x].right=s2;
a[s2].father=x;
build(s2);
}
if(s1==-1&&s2==-1){
if(nasw0>=nasw){
pasw=x;
nasw=nasw0;
}
}
nasw0--;
return ;
}
int main(){
int N;
scanf("%d ",&N);
a=new node[N+1];
int x;
scanf("%d",&x);
a[x].father=0;
build(x);
stack<int>r;
for(int i=0;i<nasw+1;i++){
r.push(pasw);
pasw=a[pasw].father;
}
printf("%d\n",nasw);
for(int i=0;i<nasw+1;i++){
if(i!=0)printf(" ");
printf("%d",r.top());
r.pop();
}
return 0;
}
代码长度限制 16 KB
时间限制 100 ms
内存限制 5 MB
给定一个森林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
森林引入总根可以看作树。各种方法的复杂度差不多。但树的储存方式决定代码是否好写。
我用的大儿子+下个兄弟的结构，发现不好写清楚。如果用邻接表的话会清晰很多。
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
struct node{
char c;
int n;
node*son;
node*bro;
};
static node*a;
static queue<node>q;
static int begin=0;
int build(int k){//返回建好后下一个兄弟的下标
int ks=0,kb=k+1;
if(a[k].n==0)a[k].son=NULL;
else{
ks=k+1;
a[k].son=&a[ks];
kb=build(ks);
for(int i=2;i<=a[k].n;i++){
a[ks].bro=&a[kb];
ks=kb;
kb=build(ks);
}
a[ks].bro=NULL;
}
return kb;
}
void prt(){
if(::begin)printf(" ");
else ::begin=1;
printf("%c",q.front().c);
node*p=q.front().son;
for(int i=0;i<q.front().n;i++){
q.push(*p);
p=p->bro;
}
q.pop();
return;
}
int main(){
int n=0;
scanf("%d\n",&n);
a=new node[n];
for(int i=0;i<n;i++){
scanf(" %c",&a[i].c);
}
for(int i=0;i<n;i++){
scanf("%d",&a[i].n);
}
int nb1=0,nb2=0;
while(nb2!=n){
nb2=build(nb1);
q.push(a[nb1]);
nb1=nb2;
}
while(q.size()){
prt();
}
return 0;
}
代码长度限制 16 KB
时间限制 100 ms
内存限制 5 MB
有一条细长的纸带,长度为 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
逆向思维，哈夫曼树。切割纸带就是拼接纸带，每次拼接的代价是拼接后的纸带长度。这样自然就想到哈夫曼树。每次取当前最短的两条纸带拼接，直到剩下一条纸带。逆序输出每次拼接后的长度就是切割过程。
#include<iostream>
#include<stack>
#include<deque>
#include<algorithm>
using namespace std;
long long getm(deque<long long>&q1,deque<long long>&q2){
long long a;
if(q1.empty()){
a=q2.front();
q2.pop_front();
}else if(q2.empty()){
a=q1.front();
q1.pop_front();
}else{
if(q1.front()>q2.front()){
a=q2.front();
q2.pop_front();
}else{
a=q1.front();
q1.pop_front();
}
}
return a;
}
int main(){
int n;
scanf("%d ",&n);
stack<long long>asw;
long long nasw=0;
deque<long long>a;
deque<long long>q;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
a.push_back(x);
}
sort(a.begin(),a.end());
for(int i=0;i<n-1;i++){
long long n1;
n1=getm(a,q);
n1+=getm(a,q);
asw.push(n1);
nasw+=n1;
q.push_back(n1);
}
printf("%lld\n",nasw);
int begin=0;
while(!asw.empty()){
if(begin)printf(" ");
else begin=1;
printf("%lld",asw.top());
asw.pop();
}
return 0;
}
代码长度限制 16 KB
时间限制 100 ms
内存限制 5 MB
两个递增序列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
把序列B当作数组，为B的每个元素匹配一个以序列A为元素的队列，并记录 Bi 与 Bi的队列的队首元素 的乘积Ni（下标 i 是索引），所有的Ni中最小的那个（设为Nk），就是当前的最小乘积。然后让Bk的队首出队，就能维护这个结构，让下一个产生的Nk最小。
证明：Ni是Bi与A中每个元素的乘积中最小的，而Nk又是所有Ni中最小的，所以Nk为当前所有乘积中最小的。
下面的代码有个样例有段错误，但我一直没找到。
#include<iostream>
using namespace std;
struct numb{
int N=0;
int ia=0;
int Nab=0;
};
int main(){
int n=0;
scanf("%d ",&n);
int a[n+1];
a[n]=0;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
numb b[n+1];
for(int i=0;i<n;i++){
scanf("%d",&b[i].N);
b[i].Nab=b[i].N*a[0];
}
int begin=0;
for(int i=0;i<n;i++){
if(begin)printf(" ");
else begin=1;
printf("%d",b[0].Nab);
if(b[0].ia!=n-1){
b[0].ia++;
b[0].Nab=b[0].N*a[b[0].ia];
for(int j=0;j<n-1&&b[j].Nab>b[j+1].Nab;j++){
numb buf=b[j];
b[j]=b[j+1];
b[j+1]=buf;
}
}
/*for(int i=0;i<n;i++)printf("%d ",b[i].Nab);
printf("\n");*/
}
return 0;
}
原文：https://www.cnblogs.com/huangyxblog/p/14838768.html