你好 ( ´ ω ` )

持續更新題目中...

這個網誌的主要目的
是要紀錄一下寫過題目的內容
避免在日後忘記相同題型怎麼寫
像我現在就已經有好幾題忘記我當初到底在寫尛了

此外，也希望幫助到同為南一中的同學
同齡的可能幫不上忙，
但也快要到了升學長的時候
希望到時能藉由這個網站幫學弟們一些忙
(當然不是指把我的code抄去)

預計之後也會放上其他judge網站的解題

沒人看也可以
畢竟原本就打算是讓自己複習用才寫的網誌
但如果有人看到有疑惑或想法的話
也歡迎提問，我是不會討厭的(//▽//)

可以的話還是想要有人看...
想要有人討論阿...

TOJ61

基本上就是DP問題

直接暴力解就好

只是時間會~~很~~長

不過還是沒TLE啦

真是太棒了

跟TOJ416,和某題用到費式數列的一樣

可以用矩陣快速冪優化

61.cpp //DP直觀暴力解 時間超長~

61-2.cpp //矩陣快速冪解 時間壓到近1%

TOJ136

我的作法是一一判斷每個位數的0~9出現次數為幾次

設i為0~9,k為某個位數

其中拆成i小於k,i=k,i大於k,3種狀況判斷

例如21375，

k為百位數,為3 

計算百位數的0~9共出現幾次

i小於k

1~2出現(21+1)*100次 1xx,11xx...211xx

i=k

3出現21*100+75+1次 3xx,13xx...203xx,21300~21375

i大於k

4~9出現21*100次 4xx,14xx...204xx

其中0要注意的是因為少了0xx的部分,所以雖然是i<k

為(21+1)*100-100次

即完成百位數0~9總數的判斷,同樣道理判斷千位數,萬位數...即可

搞了我幾個小時

回頭看其實也是蠻水的

就一些數學

我的邏輯真的不夠清晰...

136.cpp

TOJ416

今天聽學長講課
非常滿足的吸收到很多...太多了點
其中也有講到這題
講到拆成6種狀態我突然就覺得好簡單...
明明之前一直覺得很難地說
不過想當然那麼容易...
也被提示到矩陣快速冪...立刻想到之前寫的
跟TOJ376相似，都是用矩陣快速冪把時間從O(n)壓到O(logn)

沒想到又遇到矩陣題...
而且更麻煩
搞不好這種矩陣題型蠻多的...我可不想再碰到了

不過這題比那題難多了...
大概搞了3個半小時,快崩潰了
矩陣真的很難理解= =

不過也很厲害...明明同屆卻有人能解出來...

總之對矩陣也更理解了
另外也學到了其他很多DP的觀念也有LCS,LIS之類的
有來真是太棒了


關於這題的筆記

總之大概就是這樣吧

很神奇的題目=A=

416.cpp

TOJ11

恩嘛...雖然懂原理了
但實作也很麻煩，遞迴真的很難思考=A=
搞了2,3個小時才搞定
果然我不適合呢:3

最後終於抓到蟲時快要爆炸了
小小的問題怎麼讓我抓了一個多小時的bug=A=
總之終於搞定這題了，很爽

也學會了mergesort了，雖然不知道實際應用如何...
頹廢了整個暑假，感覺都變智障了...


11.cpp


參考影片:Divide & Conquer 03 : Counting Inversion