暑假字符串专题HBU程序设计训练营总结

?点这里

7-5 小字辈 (25 分)

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

9
2 6 5 5 -1 5 6 4 7

输出样例：

 

4
1 9

直接说，我用递归做的，直接超时了，然后空间换时间过了

 

开始捋一下这个题：

知道每个人的父亲是谁，直接顺着往前扒拉，就找到了祖宗，然后再回来从祖宗开始数，这是第几代的。

so，我写了一个找自己代数的递归函数。每个人都跑一次。找出最大的代数，输出代数和最大代数相同的人儿。

int count(int i){
    int coun=1;
    if(zuzong[i]!=-1){
        coun=count(zuzong[i])+1;
    } else{
        coun=1;
    }
    countzu[i]=coun;
    return coun;
    }
} 

 这个递归不停的调用，调来调去，就超时了.....留下了悔恨的泪水

盯着代码想了想，发现找到祖宗的人，又从新不停的找了好几次，想到了用空间换时间，使用一个数组记录祖宗是否已经找到了。认祖归宗后，就别再找了，儿子调用的时候再问起来，就直接说，我是第XX代人，你是XX+1代就行了。

int count(int i){
    if(countzu[i]==0){
    int coun=1;
    if(zuzong[i]!=-1){
        coun=count(zuzong[i])+1;
    } else{
        coun=1;
    }
    countzu[i]=coun;
    return coun;
    }
    else{
        return countzu[i];
    }
}

 

#include<iostream>
using namespace std;
int zuzong[100005];
int countzu[100005];
int count(int i){
	if(countzu[i]==0){
	int coun=1;
	if(zuzong[i]!=-1){
		coun=count(zuzong[i])+1;
	} else{
		coun=1;
	}
	countzu[i]=coun;
	return coun;
	}
	else{
		return countzu[i];
	}
}
int main(){
	int n;
	cin>>n;
	int a;
	
	for(int i=1;i<=n;i++){
		cin>>a;
		zuzong[i]=a;
	}
	int max=0;
	for(int i=1;i<=n;i++){
		countzu[i]=count(i);
		if(count(i)>max){
			max=count(i);
		}
	}
	cout<<max<<endl;
	int flag=1;
	for(int i=1;i<=n;i++){
		if(countzu[i]==max){
			if(flag){
			cout<<i;
			flag=0;	
			}else{
				cout<<" "<<i;
			}
			
		}
	}
	return 0;
}

不要太着急，仔细想想还是能过去的