结题报告--hih0CoderP1041
2020-03-17 16:01:36来源:博客园 阅读 ()
结题报告--hih0CoderP1041
题目:点此
描述
小Hi和小Ho准备国庆期间去A国旅游。A国的城际交通比较有特色:它共有n座城市(编号1-n);城市之间恰好有n-1条公路相连,形成一个树形公路网。小Hi计划从A国首都(1号城市)出发,自驾遍历所有城市,并且经过每一条公路恰好两次——来回各一次——这样公路两旁的景色都不会错过。 令小Hi苦恼的是他的小伙伴小Ho希望能以某种特定的顺序游历其中m个城市。例如按3-2-5的顺序游历这3座城市。(具体来讲是要求:第一次到达3号城市比第一次到达2号城市早,并且第一次到达2号城市比第一次到达5号城市早)。 小Hi想知道是否有一种自驾顺序满足小Ho的要求。思路
这里使用dfs序列。以一下树为例:
(图片来源于百度,所以后面又‘#’,懒得删了)
dfs序列:ABDCE。
为方便理解算法,我们把结点写两遍,变成:ABDDBCEECA。
假如小Ho的要求序列是ADC,那么是可行的,那在dfs序列里怎么判断呢?
答:小Ho要求的顶点序列每一个点前面的所有顶点都不在两个此节点中间。
根据这个答案,写出的代码WA0分,样例也过不去,输出全是YES,而应该是YES和NO。
分析一下错误答案。
树:
(原谅我丑陋无比的图)
dfs序:1244552366771
分析一下:3不在两个二之间,3和2都不在两个7之间,所以程序认为它是可以的,可是因为3和7之间夹着一个2,所以不可以。因此,得出结论:不仅要前面的算法,还需要保证一个节点后要么没有子孙节点,有则必须是连续的。
最后,结合粗体字,就是AC代码了
对付多数据的mains发点此
犯的错误
1.数组没初始化(每次都要重新初始化,因为每次都是一棵新的树)
2.重命名了(那个dfsx数组,猜我为啥加个x?)
3.cnt不用每次访问完就++,++一次就行了
4.思路中的第二点我开始没考虑到
5.判断第二个条件时,i和j的初值错了
6.为了调试方便,可以用set(将所有子节点放入set再查找,复杂度O(N),好于两重循环。)
收获
1.再重复那几个字:初始化,初始化,初始化(重要的事情说三遍!!)
2.以后所有名称尽量不要叫“dfs”,因为dfs有:函数、栈、数组(dfs序……),叫“dfs”很容易重命名,同理,bfs也不行。
3.做题时,所有的方面可能开始没考虑到,可是之后一定到考虑到。
4.STL不要省着用!(若想判断你是否省着用STL,看看这题你是否想到了用STL的解法)
原文链接:https://www.cnblogs.com/eason66-blog/p/P1041--hiho.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 2019.3.14解题报告&补题报告 2020-03-22
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 结题报告 2020-03-11
- 结题报告 2020-03-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash