NOIP2015 提高组复赛 Day1 第二题解题报告By 某蒟蒻 zrw 1. 题目大概描述（因为写的时候题目还没放出来）几个小盆友们在传递自己的信息（生日），并且 每个小盆友只会把自己知道的信息传给唯一的一个人 【但是 自己可以收到很多信息，并会在收到信息的下一轮把这些信息传给那个唯一的人】 （单相思 233333） ， 问多少轮后自己会收到自己一开始传递出去的自己的信息。输入：第一行一个整数n，表示有 n 个人接下来 n 行，每行一个数j，设这是除第一行外的第i 行，那么j 表示第 i 个人只会把信息传给第j 个人。输出：一个整数，表示最少几轮后自己的信息会回到自己手中。样例输入：5 2 4 2 3 1 样例输出：3 数据规模： 100% n） ：clock()。我就直接用文件输出了：意思是运行共花了36ms，时限是都是1s，也就是1000ms。再看另一组最大规模数据：所有点组成一个环。30ms，依然无压力再来一组（针对除去酱油）：除 200000 外所有点指向下一个点，200000 指向 199999。好吧这个数据就不截图了，我截结果。41ms，依然没什么压力。虽然说我在考场测的时候，电脑速度没这么快= =跑这个上面第一个点的时候显示花了300+ms，但这个数量级来看，其实三个极限的点所花时间都差不多，我想 NOI 机子应该也不会慢到300ms 被撑到 1s 吧？代码比较长，单纯的看的画就跳过头文件和read 函数（ read 函数是我加的输入优化，因为已经写习惯了） （看上去有79 行其实有用的只有30+行，这是我在家写的，但和考试时写的几乎一样，文件输入输出已注释）（ visit 数组这里简化成了vis 数组了）：#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int read() int x=0; bool b=1; char c=getchar(); while(c9|c=0 int n,ans,father200001=,vis200001=,ent200001=; int main() /freopen(“message.in“,“r“,stdin); /freopen(“message.out“,“w“,stdout); n=read(); ans=n; int i,x,j; for(i=1;i=n;+i) fatheri=read(); +entfatheri; for(i=1;i=n;+i) if(enti=0) q.push(i); visi=1; while(!q.empty() x=q.front(); q.pop(); -entfatherx; if(entfatherx=0) visfatherx=1; q.push(fatherx); for(i=1;i=n;+i) if(enti!=0 j=fatheri; x=1; while(visj=0) visj=1; j=fatherj; +x; if(x=ans) ans=x; printf(“%dn“,ans); /fclose(stdin); /fclose(stdout); return 0; 最后呢，祝大家，当然还有自己，明天人品爆发！来自某蒟蒻 zrw