当前位置:首页 >> 学科竞赛 >> NOIP2015提高组day1第二题解题报告

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


NOIP2015 提高组复赛 Day1 第二题解题报告
By 某蒟蒻 zrw 1. 题目大概描述(因为写的时候题目还没放出来)
几个小盆友们在传递自己的信息(生日) ,并且每个小盆友只会把自己知道的信息传给 唯一的一个人【但是自己可以收到很多信息,并会在收到信息的下一轮把这些信息传给 那个唯一的人】 (单相思 233333) , 问多少轮后自己会收到自己一开始

传递出去的自己的 信息。 输入:第一行一个整数 n,表示有 n 个人 接下来 n 行,每行一个数 j,设这是除第一行外的第 i 行,那么 j 表示第 i 个人只会把信 息传给第 j 个人。 输出:一个整数,表示最少几轮后自己的信息会回到自己手中。 样例输入: 5 24231 样例输出: 3 数据规模:100% n<=200000 60% n<=2500 30% 记不住了??

2. 大概需要什么样的算法
根据数据规模,我们可以大概判断需要多少效率的算法,甚至有的时候可以猜出这题用 的是什么算法。对于本题来说,60%大概就是 O(n^2)的算法了,一般是裸的暴力回溯或 者是暴力广搜,也有用 floyd 的(我是从 NOIP 吧上看到的) 。 如果要 AC 的话,算法效率至少要在 O(nlogn)以下(log 在这里是以 2 为底不是以 10 为 底) 。 然而,本题是有 O(n)算法的,下面会讲。

3. 我们还是画个图吧(图可能比较难看,但能看就行)
画画图,就会知道这是在做一件什么事情了。 以样例数据为例:

我们很容易发现,2,3,4,形成了一个环,而 1 和 5,并没有什么卵用?? 所以在环 234 中,由于每一轮可以把在上一轮知道的信息传给唯一的下一个人,在 234 环中,就需要 3 轮,信息才能传到 多画几个图(由于本人很懒,就只画一张特殊情况比较多的小图) :

(有木有一种贵圈真乱的感觉) 我们可以看出来,1,5,6,成了一个环,而 2,3,4,8,也成了一个环,7,9,是来打酱油的。 那么对于这两个环来说, 因为每一轮可以传递上一轮信息给下一个人, 所以显然是 1,5,6 这个环比较早传完,3 轮。 说白了,就是在图里找最小环。

4. ABCD,你选择哪一个?
于是乎就有各种最短路算法来解决这个问题了,但是我觉得时间复杂度还是有待讨究。 说实话我也不知道这些算法能不能 AC。比如 SPFA 算法,原本是 O(kE)【k 为常数,约等 于 2,E 为边数】 ,到这里估计就是 O(nkE),也就是 O(nE),因为每个点只会指向唯一一 条边,所以边就是 n 条,也就是 O(n^2),不作优化很有可能会炸(请注意我的措辞) 。 贴吧上也有人说是用并查集,据说是可以 AC,但我并不知道他是准备怎么个并查法, 我想应该是不好理解的。

5. 说白了,你还是得走这条必经之路
很明白的一件事情就是,因为一个人只会把信息传给唯一的另一个人,我们就可以用一 个一维数组来存储这个关系。设数组为 father[],那么 father[i]表示就是第 i 个人可以把 信息传给第 father[i]个人,这样很省空间,访问的时间也很省。

6. 那么问题来了……
挖掘机??哦不,优化技术哪家强? 可能很多人到这里就卡住了。 所以我们再把样例数据挖出来看一看:

(是不是觉得越看这个图越不爽了?) 如果说对每一个点进行什么 SPFA 啊,floyd 什么鬼的最短路算法,那 1,5 这两个路人就 根本没用了!而且对于 2,3,4 来说,如果每一个都把环走过去,是十分费时间的。 你要想想,官方可是有一百种方法来卡数据让你 AC 不了的! 但显然,如果用一个数组记录这个点是否被访问过的话,万一从路人搜到环里,不就悲 剧了?

7. 酱油,垃圾,摔掉!
如何处理掉酱油是一大问题,但在处理之前你需要了解什么是酱油,才能处理。 没有办法形成环的点,就是酱油! 那怎么样才无法形成环呢? 煞笔,没有人给他信息他肯定就只有自己一个人的信息嘛,也就没办法形成环,例如样

例中的 5:

那既然没用,那还留着干嘛?摔掉!

然后你会发现,1 也是个酱油,接着摔: 碰到了 2。2 的入度不为 0,不进行操作。 于是乎,这就成了一个完美的环了。 说白了,就是把初始时入度为 0 的点删掉,并且把指向的点的入度减一,如果减完后指 向点的入度也为 0 了,那么就按照刚刚那个操作继续下去,直到找到减完后入度不为 0 的点。

对于某些比我还弱的人的科普: 入度:在图中,对于某一个点,通向这个点的边个数就是入度。同样,相对 的出度,就是从这个点出发向另一个点的边的个数。比如样例中 5 的入度为 0,出度为 1;1 的入度为 1,出度为 1;2 的入度为 2,出度为 1。
当然,设一个 visit[]数组表示这个点是否被访问过是个不错的选择,因为之后有用。将 入度为 0 的点的 visit 设为已经访问过。

对于刚刚第二种图,我也进行这样处理,得到的图是这个样的: (是不是觉得舒坦很多了呢?) 如果还是没有理解,看看下面这一小段文字: “
我的想法就是看 2 4 2 3 1 发现第五个人没收到消息 所以把他 T 了 这时候 1 也收不到消息了 所以把 1 也 T 了 就剩下 2 3 4 三个人 所以输出 3 ”——引用贴吧

ID

诗仙 Eric 的比较通俗的话

对于删除点和边的话,dfs(深度优先搜索,简称深搜)和 bfs(广度优先搜索,简称广 搜)都可以使用,效率应该也不会相差太多。我是喜欢拿 queue 装逼的人,于是乎用 了广搜。 最坏情况,n=200000,1 指向 2,2 指向 3??一直到 199998 指向 199999,199999 指向 200000,200000 指向 199999,O(n),不会超时。 好了,关于“打酱油”的问题就解决了,那么剩下的就是专心解决最小环问题了。

8. visit 数组出奇迹
要知道,总是会有一个不经意的细节,影响到了结果。这就是 FLAG 的力量。 所以说,屎可以乱吔,FLAG 不能乱立。 ↑以上均为扯淡。 首先我先说一下,因为是贴吧某个盆友(好吧就是上面引用话的那个人)知道之前的算 法,但由于没学过太多图论的算法,不会玩最小环,于是我拿出来讲了。 说实话,我也没学过多少图论的算法→_→ 刚刚已经讲过了,这个图用 father 一维数组存是很省空间的,调用也很省时间。 于是乎就是查找入度不为 0 的点(其实到这个时候应该已经只剩下入度为 1 的了,因为 每个点只有可能在一个环内,可以去稍稍画几个图证明一下) ,然后利用 father 数组调 用环(这个和并查集有异曲同工之处) 。 但如果查找到每个点都调用一次环,那最坏的查找情况可是 O(n^2)。 说好的 O(nlogn)呢? 不要打架,不要打架,visit 好处都有啥,谁说对了就给他! 对于样例来说,访问完 2 这个点和 2,3,4 这个环,3,4 两点也就都访问过了,因为同一个 环长度肯定是都一样的,所以没有必要再去搜 3,4 两点。 那么就用 visit 数组来记录这个点是否有访问过,当访问一个环的时候,每次访问到一 个点,就将其标记为已经访问过,下次 for 循环到这个点时就可以跳过,省时间。

这也就是刚刚为什么入度为 0 的点需要设成该点已访问过的原因——酱油哪有你出场的 份嘛。 最坏情况:n=200000,1 指向 2,2 指向 3??199999 指向 200000,200000 指向 1。 for 循环:n 次 while 查找:n 次 还是 O(n)

9. 总结
我是做过一些往年的提高组 day1 第二题的题目,但我想这次应该是最容易的了(然而 这次的第 3 题写个暴力都瞬间爆炸【然而我并不会写,只会看特殊数据骗 30 分】 ) ,也 就意味着大家都要靠明天的题目来拉分了 (FJ 的某方立了个 FLAG 说 FJ 有人把第 3 题 AC 了他就直播吔屎 23333) (集体 230 的节奏) 。 这题我觉得,真的,画图是关键(我记得我以前的竞赛老师王老师经常说的一件事情就 是数形结合) ,多画图,多模拟,就很容易找到需要解决问题的方法。我这么弱一二两 题也总共花了大概 1 个小时没到半就做完了。个人认为这样的算法在这题里应该算是最 高效的算法之一了,因为除了最后的查找以外,已经没有什么重复计算的地方了。而且 应该也算是最容易理解的算法了,要 AC 应该没什么问题。至于其他的算法,我太弱, 理解不了。 顺便附带被贴吧大神举反例后的打脸截图(代码也随后放) :

接下来是一组最大规模数据的测试:每两个点就组成一个环。

接下来我在我的代码上加个输出运行时间函数(注意:头文件<time.h>) :clock()。

我就直接用文件输出了: 时限是都是 1s,也就是 1000ms。 再看另一组最大规模数据:所有点组成一个环。

意思是运行共花了 36ms,

30ms,依然无压力 再来一组(针对除去酱油) :除 200000 外所有点指向下一个点,200000 指向 199999。

好吧这个数据就不截图了,我截结果 。 41ms,依然没什么压力。 虽然说我在考场测的时候,电脑速度没这么快= =跑这个上面第一个点的时候显示花了 300+ms,但这个数量级来看,其实三个极限的点所花时间都差不多,我想 NOI 机子应该 也不会慢到 300ms 被撑到 1s 吧?

代码比较长,单纯的看的画就跳过头文件和 read 函数(read 函数是我加的输入优化, 因为已经写习惯了) (看上去有 79 行其实有用的只有 30+行,这是我在家写的,但和考 试时写的几乎一样,文件输入输出已注释) (visit 数组这里简化成了 vis 数组了) : #include<iostream> #include<stdio.h> #include<algorithm> #include<math.h> #include<string.h> #include<iomanip> #include<queue> #include<stack> #include<stdlib.h> #include<string> #include<vector> #include<map> using namespace std; int read(){ int x=0; bool b=1; char c=getchar(); while(c>'9'||c<'0'){ if(c=='-') b=0; c=getchar(); } while(c>='0'&&c<='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[i]=read(); ++ent[father[i]]; } for(i=1;i<=n;++i) if(ent[i]==0){ q.push(i); vis[i]=1; } while(!q.empty()){ x=q.front(); q.pop(); --ent[father[x]]; if(ent[father[x]]==0){ vis[father[x]]=1; q.push(father[x]); } } for(i=1;i<=n;++i){ if(ent[i]!=0&&vis[i]==0){ vis[i]=1; j=father[i]; x=1; while(vis[j]==0){ vis[j]=1; j=father[j]; ++x; } if(x<=ans) ans=x; } } printf("%d\n",ans); //fclose(stdin); //fclose(stdout); return 0; }

最后呢,祝大家,当然还有自己,明天人品爆发! ——来自某蒟蒻 zrw


更多相关文档:

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

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...

NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组day1第二... 8页 免费 NOIP2015提高组参考答案 1页 免费 ©...

NOIP2015提高组复赛试题Day1

第 2 页共 6 页 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 2.信息传递 (message.cpp/c/pas) 【问题描述】 有n个同学(编号为1到n)正在玩一个...

NOIP2015普及组复赛试题解题报告word版第一二题满分程序

全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 NOIP2015 普及组复赛试题解题报告 word 版 第一二题满分程序 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组一...

NOIP2015提高组复赛试题Day1+Day2纯Word版

第 2 页共 12 页 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 2.信息传递 (message.cpp/c/pas) 【问题描述】 有 n 个同学(编号为 1 到 n)...

NOIP2015提高组题解zkp蒟蒻的题解

第一题 幻方 纯模拟 第二题 信息传递 对于每一个未访问过的节点,访问其父节点...NOIP2015提高组复赛试题... 6页 免费 NOIP2015提高组复赛试题... 6页 免费...

NOIP2015普及组解题报告

NOIP2015普及组解题报告_学科竞赛_初中教育_教育专区...对于第 1 组至第 2 组数据,1 ≤ n ≤ 100, ...NOIP2004普及组复赛解题... 8页 免费 Noip2008普及...

NOIP2014提高组复赛试题day1+day2

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育...然后枚举第二个人,在 list[color[i]] 中用二分...©2015 Baidu 使用百度前必读 | 文库协议 | 网站...

noip2015提高组复赛试题答案

第2页共6页 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 2.信息传递 (message.cpp/c/pas) 【问题描述】 有 n 个同学(编号为 1 到 n)正在玩一...
更多相关标签:
noip2014提高解题报告 | noip2016提高组day1 | noip2015提高组day1 | noip2014提高组day1 | noip2012提高组day1 | noip2013提高组day1 | noip2011提高组day1 | noip2016解题报告 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com