结题报告–hihoCoderP1041

0
11

题目:点此

描述

小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的解法)

<

发布回复

请输入评论!
请输入你的名字