我來分享一下這個最簡單的problem的解法好了 這個雖然是典型的喇賽題，不過對於初入ACM的人來講 是一個很好的磨練腦袋最佳化原理的機會， 因為很多人事實上在玩ACM以前都沒想過opt這碼子事情 我自己的code就不捏他了，我大略提一下我自己寫的這組code考慮到的地方 作者可以想辦法把他給實作出來 :3 1. 事實上你並不需要每次都做出完整的計算。你可以把算過的結果用map存起來 比方說當他餵給你n = 5 那你就被強迫得算出n = 16, 8, 4, 2, 1這些結果 所以事實上你就可以知道n = 5的時候cycle = 5, n = 16時cycle = 4.... 所以我們可以把__當作key, __當作value建表，當下次被餵值的時候可以先查表 (__請自行填空 XD) 2. 有些人可能會問，為什麼用map而不是用vector + find，這又是一個最佳化議題 map實作上是用RB Tree作出來的perfect balanced binary tree 這個東西有個特點就是尋找值的時候是O(log n)，而插入值的時候是O(n) vector的話則是插入值的時候是O(1)好像很棒，可是尋找值的時候卻是O(n) 考量這個case很明顯尋找會遠多於插入，尤其越到後面，尋找的cost會越高 所以我們會使用map(即使他有某方面不太方便的缺點...)而非vector 其實這個還是有更好的解法，就是priority queue，不過這個就先不提了 3. 事實上這個是可以作弊的，我們可以先在自己電腦上先把那張表跑出來 比方說我們可以先跑出一個n = [1, 1000]的時候的cycle表 如果說我們還要再考慮記憶體容量的話，那我們可以取出cycle > 100的n 再另外建一張表(很多不可思議的低記憶體用量+低cpu time就是這樣做出來的) 然後我們可以在考慮一點，我們預先分析(對，別忘了計算不只在ACM上，我們 local端也可以先算)哪些n被跑最多次然後cycle又比較高，那我們可以把他抓出來 然後自己寫一個小程式產生這個table灌到"給ACM吃的程式本體"內 其實除了第三點比較高階以外(事實上這也是很重要的一環) 1 2都是你可以現在就考慮的。 第三點的話基本上我會把他視為作弊 -_- 這個等於是把ACM上的CPU時間先在我們電 腦做掉了，這個說不是作弊有點說不過去 XD 但是事實上很多ACM題目都可以這樣作弊的，而且要作這種弊也是需要高技巧的 :3 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.208.83.250