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