题目:
描述
小hi和小ho准备国庆期间去a国旅游。a国的城际交通比较有特色:它共有n座城市(编号1-n);城市之间恰好有n-1条公路相连,形成一个树形公路网。小hi计划从a国首都(1号城市)出发,自驾遍历所有城市,并且经过每一条公路恰好两次——来回各一次——这样公路两旁的景色都不会错过。
思路
这里使用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的解法)
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600191.html