快半年沒更新blog了 來更新一下好了
這半年間經歷了不少事情
像是在初選結束之後 CF rating又回藍了
資訊之芽的兩個階段也結束了
在這之間競程能力不知道增強了多少 不過至少對於亂砸資料結構這點應該是有所進步
而久違的這篇文來更一下上資訊之芽的心得吧
資訊之芽第一階段
第一階段的資訊之芽的內容大多還是比較簡單的內容
從第一週到第七週分別是
一、資結 (Stack, Queue, Linked List)
二、複雜度、樹
三、Flood Fill、Heap、基礎圖論
四、枚舉
五、貪心
六、分治
七、DP (Part 1)
這些內容對已經學了一年競程和演算法的我來說 難度其實不太高
不過還是學到了不少東西
像是複雜度的嚴格定義和證明、Heap的合併、各種分治
也有遇到一些滿有趣的題目
NEOJ 788 (等價於 CF526F Pudding Monster)
然後第一階段的階段考不算太難 (pA, pB都裸題 pC是倍增法 pD有趣的分治 pE類似重心分治)
運氣很好的拿到了全場第二430分 (只輸破台的超強PixelCat)
第一階段的手寫作業大部分也都只是一些小證明等等 (雖然我都寫很爛)
不過第一階段以上機和手寫都 A+ 結束了
資訊之芽第二階段
第二階段的內容就比較困難了
分別是
九、DP (Part 2)
十、DP (Part 3)
十一、最小生成樹、歐拉迴路、哈密頓迴路、拓樸排序
十二、圖連通性、BCC、SCC
十三、隨機
十四、分塊
前兩週介紹了更多的DP，Part 2比較偏向各種背包的統整，Part 3則是一些簡單DP優化方式
這兩週遇到比較有趣的題目就是 TIOJ 1676 - 烏龜疊疊樂 了吧
第一次寫有線段限制的斜率優化 (雖然我還是砸了多兩個log的李超線段樹)
圖論的部分倒是比較沒有遇到什麼問題
而最後兩週所教的隨機和分塊都是以前沒什麼碰過的東西
隨機的部分很多真的很神奇，明明看起來很唬爛的作法，機率算起來就是正確的
而分塊也是 很多人應該讀過我之前寫的那篇分塊吧 我以為分塊就是拿來做那種題目的
結果他的變化比我想像的多很多 像是值域分塊、操作分塊等等 可以做的事超級多
有的問題看起來跟根號、分塊無關，將問題分成大於根號和小於根號去思考，就能解決了!
真的很神奇
而隨機 在 Virtual BOI 2018 Day 2 的某一題 我也成功在Virtual的當下寫出隨機解
第二階段的隨機和分塊真的讓我收穫良多
儘管後來的階段考打得不是很好 該拿的分數都沒拿到
不過學到很多
比較可惜的是從第十一週之後就改成線上了
優秀結業
而最近也收到了資芽的優秀結業證書
我覺得資訊之芽對於打競程的選手來說是一個可以打好基礎又能學到東西的課程
不只是學到了東西，也認識了不少人