TOJ376

吶...
TOJ還是不給submit，
不過我感覺是沒問題了，就先放上來吧

這題主要算是math題吧
我到現在還是搞不太懂就是

這題基本上最直觀的解法就是直接加上去
結果還是TLE...
仔細看數字有到百億...

我看學長AC的時間是零
又想到費氏數列其實是有公式的
就開始往「是否能直接帶入公式」的方向思考
讓時間從O(n)變成O(1)

結果一直爬文阿
已知費氏數列的公式了，費氏數列合的公式怎麼求也不知道
浪費了兩三張計算紙感覺都在耍白癡，像是寫了好幾行得出了s(n-1)+f(n)=s(n)之類的廢話

後來觀察了一下，突然發現s(i)=f(i+2)-1，就莫名其妙發現的規律
用程式跑幾個大數字也正確就是了
像前5項的和(1+1+2+3+5)=第7項(13)-1=12

然後就想說很高興的帶公式直接O(1)得解
結果發現一個致命問題...
不知道怎麼取mod...
又試了一段時間，結果還是放棄了阿...公式解>口<


不知不覺打了一堆幹話:3
總之後來發現了，原來費氏數列還有一種求法是O(logn)
來源網站
參考了一下，就實作看看，原理甚麼的不懂
畢竟我根本沒學過矩陣

然後就做出來了...
時間的話跟直接加比起來,當n=100000000(億)，
相加耗費2秒多，矩陣只要不到0.001秒
看來是沒問題了...

搞了一個晚上終於解決，只是原理不知道心就是有點癢癢的

比較一下費氏數列我已知的三個解法
1.加法 : O(n) ,易實作,足以應付大部分狀況
2.公式解 O(1) ,應該不會用到,而且不夠彈性,像這題就想不到方法取mod(可能是我太笨QQ)
3.矩陣 O(logn) ,數字特別大會TLE才需要用到(約超過10^8)

376.cpp(不能完全AC，但可以參考

更新(7/4
TOJ修好後發現一堆問題
可惡...果然沒那麼順利...
結果又爬了一堆文
硬生生地把矩陣的算法之類的搞懂
...
真的有夠麻煩...
反正...終於AC了...
376-2.cpp(AC正解版

TOJ169

TOJ掛掉好幾天了...
都不能更新好困擾...
如果附檔有錯就算了吧...

DP問題...
受夠了阿...
我這題當初大概想了一整天吧

後來看看其實也就這樣...
只是真的很難去想到就是...
也不然啦...只是實作很多沒注意到的地方出現bug...

我當時的思想:
1.暴力解的話，要得知第i根的狀況，最多必須掃過i-1根的值，然而->嚴重TLE

2.
仔細觀察，其實不必
舉  1 3 4 5 2 為例
當我們判斷到第4根(假設前面都判斷完了，並得到正確答案)，
判斷和前面4的關係就好，
5大於前面的4，所以5的答案等於4的答案+1(多了4)，也就是2(4的答案)+1=3
若判斷到2，2小於等於前面的5，所以答案為0

這樣是不是比暴力解快呢?

然而--->WA!!

我想也是，沒那麼輕鬆嘛...

甚至連範例都會錯就是

3.

以1 10 2 4 3 5 7為例

正解是0 1 0 1 0 3 4，然而用第2種思想卻得到0 1 0 1 0 1 2 ??

恩...仔細觀察相信馬上就會發現原因，

當我們要得到第i根的答案時

我們必須還要判斷擋住i-1根的那個棒棒是否也會擋住第i根，

如果會，那才可以直接第i根的答案=第i-1根的答案+1

如果不會被擋住，我們還要把前面的再吃掉才行

至於擋到第i根的棒棒找法也很好找，答案為0代表前一個擋到，答案為1代表前兩個擋到

拆成步驟的話(直接跳到第4根

1 10 2 4 3 5 7

5>3，吃掉3的答案，並判斷擋住3的那根會不會擋住5

1 10 2 4 3 5 7

5>4，沒被擋住，所以也要吃掉4的答案，也要判斷擋住4的那根

1 10 2 4 3 5 7

5<=10，被擋住了，因此不吃掉10的答案，也不用繼續判斷了

最後5的答案就是3的答案(0)+4的答案(1)+吃掉3和4(2)

也就是0+1+2=3

基本上就這樣，而已，知道實作方法，程式碼寫起來也不長

只是DP真的有夠煩惱

169.cpp

TOJ168

嗯吶...

就跟紀錄最大值的程式一樣，只是多了記錄次數的需求

基本上也算DP問題啦

只是基礎到大家不把它當DP了...

輕鬆拿分的水題

後面的169才是真正麻煩的DP

168.cpp

TOJ162

不想多加解釋...

就是水題

if判斷複製貼上就好

162.cpp

TOJ16

一直考慮這要不要放在水題
我當初錯超多次的
不過後來看這不是超簡單...
我之前是沒想過放在陣列索引值儲存的方法
我是直接把每兩個數總和丟進去陣列...真慘...
基本上要注意的點
「這兩位手上一定要拿一部份的手提袋」
還有他輸出非常多(百萬，請不要用endl，會TLE
請改用\n，我也是第一次知道endl會導致TLE
從此之後要拚速度偶而就會用\n

嘛...我還是認為他是水題啦
只是那個陷阱真的有夠討厭>口<
另外還有加強版的我過不了就是QQ

16.cpp