題目：點此
描述
小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.uj5u.com/houduan/54931.html
標籤：C++
上一篇：在Android平臺使用SNPE應鏈接libc++庫
下一篇：好久沒了，有認識的人嗎？