《NOIP2015提高组day1第二题解题报告》由会员分享,可在线阅读,更多相关《NOIP2015提高组day1第二题解题报告(8页珍藏版)》请在金锄头文库上搜索。
1、NOIP2015 提高组复赛 Day1 第二题解题报告By 某蒟蒻 zrw 1. 题目大概描述(因为写的时候题目还没放出来)几个小盆友们在传递自己的信息(生日),并且 每个小盆友只会把自己知道的信息传给唯一的一个人 【但是 自己可以收到很多信息,并会在收到信息的下一轮把这些信息传给那个唯一的人】 (单相思 233333) , 问多少轮后自己会收到自己一开始传递出去的自己的信息。输入:第一行一个整数n,表示有 n 个人接下来 n 行,每行一个数j,设这是除第一行外的第i 行,那么j 表示第 i 个人只会把信息传给第j 个人。输出:一个整数,表示最少几轮后自己的信息会回到自己手中。样例输入:5 2
2、 4 2 3 1 样例输出:3 数据规模: 100% n) :clock()。我就直接用文件输出了:意思是运行共花了36ms,时限是都是1s,也就是1000ms。再看另一组最大规模数据:所有点组成一个环。30ms,依然无压力再来一组(针对除去酱油):除 200000 外所有点指向下一个点,200000 指向 199999。好吧这个数据就不截图了,我截结果。41ms,依然没什么压力。虽然说我在考场测的时候,电脑速度没这么快= =跑这个上面第一个点的时候显示花了300+ms,但这个数量级来看,其实三个极限的点所花时间都差不多,我想 NOI 机子应该也不会慢到300ms 被撑到 1s 吧?代码比较长
3、,单纯的看的画就跳过头文件和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()
4、; 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