我来分享一下这个最简单的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