NOIP2015提高组day1第二题解题报告.docVIP

NOIP2015提高组复赛Day1第二题解题报告 B5 2 4 2 3 1 样例输出： 3 数据规模：100% n=200000 60% n=2500 30% 记不住了…… 大概需要什么样的算法 根据数据规模，我们可以大概判断需要多少效率的算法，甚至有的时候可以猜出这题用的是什么算法。对于本题来说，60%大概就是O(n^2)的算法了，一般是裸的暴力回溯或者是暴力广搜，也有用floyd的（我是从NOIP吧上看到的）。 如果要AC的话，算法效率至少要在O(nlogn)以下（log在这里是以2为底不是以10为底）。 然而，本题是有O(n)算法的，下面会讲。 我们还是画个图吧（图可能比较难看，但能看就行） 画画图，就会知道这是在做一件什么事情了。 以样例数据为例： 我们很容易发现，2,3,4，形成了一个环，而1和5，并没有什么卵用…… 所以在环234中，由于每一轮可以把在上一轮知道的信息传给唯一的下一个人，在234环中，就需要3轮，信息才能传到 多画几个图（由于本人很懒，就只画一张特殊情况比较多的小图）： （有木有一种贵圈真乱的感觉）我们可以看出来，于是乎就有各种最短路算法来解决这个问题了，但是我觉得时间复杂度还是有待讨究。说实话我也不知道这些算法能不能AC。比如SPFA算法，原本是O那么问题来了……（是不是觉得越看这个图越不爽了？）但显然，如果用一个数组记录这个点是否被访问过的话，万一从路人搜到环里，不就悲剧了？没有办法形成环的点，就是酱油！ 那既然没用，那还留着干嘛？摔掉！ 然后你会发现， 碰到了2。2的入度不为0，不进行操作。 于是乎，这就成了一个完美的环了。 说白了，就是把初始时入度为对于刚刚第二种图，我也进行这样处理，得到的图是这个样的：我的想法就是看2 4 2 3 1发现第五个人没收到消息所以把他T了这时候1也收不到消息了所以把1也T了就剩下2 3 4三个人所以输出3首先我先说一下，因为是贴吧某个盆友（好吧就是上面引用话的那个人）知道之前的算法，但由于没学过太多图论的算法，不会玩最小环，于是我拿出来讲了。对于样例来说，这也就是刚刚为什么入度为最坏情况：n=for循环：n次总结 接下来是一组最大规模数据的测试：每两个点就组成一个环。 接下来我在我的代码上加个输出运行时间函数（注意：头文件time.h）：clock()。 我就直接用文件输出了：意思是运行共花了36ms，时限是都是1s，也就是1000ms。 再看另一组最大规模数据：所有点组成一个环。 30ms，依然无压力 再来一组（针对除去酱油）：除200000外所有点指向下一个点，200000指向199999。 好吧这个数据就不截图了，我截结果。 41ms，依然没什么压力。 虽然说我在考场测的时候，电脑速度没这么快= =跑这个上面第一个点的时候显示花了300+ms，但这个数量级来看，其实三个极限的点所花时间都差不多，我想NOI机子应该也不会慢到300ms被撑到1s吧？ 代码比较长，单纯的看的画就跳过头文件和read函数（read函数是我加的输入优化，因为已经写习惯了）（看上去有79行其实有用的只有30+行，这是我在家写的，但和考试时写的几乎一样，文件输入输出已注释）（visit数组这里简化成了vis数组了）： #includeiostream #includestdio.h #includealgorithm #includemath.h #includestring.h #includeiomanip #includequeue #includestack #includestdlib.h #includestring #includevector #includemap using namespace std; int read(){ int x=0; bool b=1; char c=getchar(); while(c9||c0){ if(c==-) b=0; c=getchar(); } while(c=0c=9){ x=x*10+c-0; c=getchar(); } if(b) return x; else return -x; } queue int q; int n,ans,father[200001]={},vis[200001]={},ent[200001]={}; 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){ father[