你好 ( ´ ω ` )

持續更新題目中...

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

此外，也希望幫助到同為南一中的同學
同齡的可能幫不上忙，
但也快要到了升學長的時候
希望到時能藉由這個網站幫學弟們一些忙
(當然不是指把我的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

TOJ426

這系列終於放上來了阿可惡
可是等很久了阿
甚至想說該不會就不放上來了

嘛...隨便啦
先挑簡單的水題吧

這題當時好像有人直接印出就是...

只要好好觀察就好，剩下的就注意格式

開一個N*N的陣列
1在左上角
接著重複
(1)往右一格
(2)左下到底
(3)往下一格
(4)往右上到底
當(1)和(3)出現問題時(只有開N*N，沒辦法往右往下的時候)
就分別改成往下一格和往右一格

最後步驟(1),(3)就會到達最後一格右下角，設個if判斷

大概就是這樣
整體不難，就是要觀察一下
也有其他很多解，這只是其中一種

426.cpp

TOJ203

...

203.cpp

TOJ400

...

很簡單啊這題...

恩...

不過我覺得我寫的不夠滿意就是，

感覺有些地方可以再改進...

這題也算是偏水題吧，不過我想有空也可以複習一下

就歸類在math吧

400.cpp

TOJ77

水題:3

77.cpp

TOJ387

看起來稍微複雜
但也是水題啦:<
就沒什麼隨便寫寫的水題啦

387.cpp

TOJ341

是水題沒錯
但是有夠麻煩的
把那個亂七八糟式子完全沒問題的照做比想像中難
吃了好幾個WA = A=
反正題目沒問題，測資也沒問題
通常就是哪裡粗心沒注意到才會WA
...
總之有夠麻煩的
但如果正式比賽考這種還是會很爽啦

341.cpp

TOJ339

水題

339.cpp

TOJ337

也是水題
基本上就直接輸出就好，應該也沒什麼演算法

發現之前沒有寫IO優化Rank蠻後面的

337.cpp

TOJ331

水題懶得筆記

331.cpp

TOJ253

水題..水題...到處都是水題...
照題目輸出就好啦

253.cpp

TOJ261

糞題，垃圾垃圾垃圾
呸
沒講清楚多筆測資
當大家都會讀心喔
聽說陰謀論的陰謀指的是緞帶長度沒有非正整數的
我看多筆測資才是真正的陰謀吧=A=


261.cpp

TOJ184

恩...

這要說是大數運算嗎

定義上也是算吧，

不過也他的A必定是10^n，這就輕鬆很多了

簡簡單單的水題

要做完整的大數相乘也是可以啦...

不過題目都這樣了，只要在B後面補零就好了，順便判斷正負數

184.cpp

TOJ181

就照題目輸出的水題
當作打發時間吧:3
這種題目看了真的覺得很舒服
181.cpp

TOJ18

就判斷迴文
也不知道是誰發明這種題目的
後來那種最長子字串迴文，單錯誤迴文...就很麻煩
嘛...
反正這題是水題...

18.cpp

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正解版