###### tags: `資訊之芽心得文`
# 2020資訊之芽 . 幼芽的成長日記(2)
## Day.9、10 暴風
### 進階動態規劃
二階開始了
課程也變得更加困難
今天的課程聽得好痛苦QwQ
尤其是位元DP，完全跟不上講師的速度
後面複習時，總算漸漸有了頭緒

這次的手寫作業史上最難
歸約法、NP-hard、3-SAT、…
完全不知道怎麼寫證明
第二堂課的講師其實有提到這些東西
他也說之後可能會要大家證明
原來他埋了這麼深的梗OAOAOAO

#### 作業進度QuQ：幾乎沒什麼進展
## Day.11 小雨
### 進階圖論
經過前兩周的摧殘後
我終於在今天得到救贖
相較於動態規劃，圖論不僅好理解
實作上也順手許多
（一定是我還沒接觸到更深的知識
總之今天算是把之前略聽過的東西
全部學習得更紮實

這次的手寫作業真的好有趣><
BIT好好寫，只是能有的地方感覺不是很多QQ
(聽說有個東西較zkw線段樹
(實用性跟code複雜度介於線段樹跟BIT之間(?

#### 作業完成度>u<：手寫：剩一題證明題 / 上機4/7題
## Day.12 彩虹
### 計算幾何
先前就對這主題很有興趣
（把幾何圖形用電腦表示!?
並且研究過好多次向量
利用純記憶的方式學習它
因此每每學過之後都會忘記
直到今天才真正搞懂那些運算的意義
內積、外積、線段平行、線段相交等等

手寫作業則是介紹了hash演算法
還好這部分已經有一些背景知識
寫起來格外輕鬆
（殊不知這是之後上課的伏筆
#### 作業完成度OuO：手寫：剩一題證明題 / 上機5/8題
## Day.13 綠葉
### 線段樹
以前碰線段樹的時候
知道它在幹嘛、知道它可以O(log n)區間操作
但是就。是。不。會。實。作QuuQ
（線段樹啊線段樹為什麼你這麼冷漠QAQ

今天上完這堂課後
總算跟他培養出好感情了
我們之間終於有了好的發展
但是要到摯友的等級
還要走好長一段路呢！

禮拜五的時候發生了一些小插曲
班上另一位資芽的同學
寫線段樹WA了一整個晚上
在課堂上繼續寫時寫到爆氣、翻桌
後來試著看他的code
然後莫名其妙改了一些東西就好了(!?
（看來他們之間默契不太好：（

其實這也算是競程這條路必經的過程吧
總是會卡住、挫折
熬夜debug結果還是不得其解
那種手抖、挫敗、的憂鬱的歷程對我來說很有共鳴
畢竟我不是那種一路AC的天選神才
（我吃過的WA跟TLE比AC多非常多
而這些困境真的要有夠強大的意志力才撐得下去…

#### 作業：沒有手寫 / 上機：4/6題
## Day.14
### 歡樂團體賽
團體賽！！！！！！！>u<
聽說這是往年資芽都有的傳統
學員組隊打比賽，1~3人
採ICPC制，3小時8題
我跟很電很電的joy還有柏瑄組隊><

先來講解題的情況
開場沒多久，joy就已經把所有題目看完了
每當我看完一題，還在思考或是正要寫的時候
joy已經把它結束掉了（電電電電電電電電電電）
柏瑄雖然比較晚到，但是他也很成功的貢獻一題
終場以AC六題拿下這次的第二名（joy凱瑞了5題Orz）
而我呢？完全的躺分仔OAOAOAOAOAOAOAO
（一題都沒有寫的廢物QuQ…）
發獎品的時候，我真的太心虛，根本沒資格拿…
拿著他拍完照以後就不斷的塞給他們兩個人
儘管如此，這場比賽至少讓我有了些經驗
坐在joy旁邊，能夠近距離觀察他的解題方式還有寫code的速度（真的好快OAO），算是學到一些比賽的經驗了吧(?

題目的部分，講師們真的很用心XDDD
看到題敘好多日麻就會一直想到YP好好笑XDD
（日麻大師Orz）
最讓我印象深刻的是π筆測資那題XD
題目是一個很難的數學題
但是輸出的答案竟然要mod 2而且只有[π]筆測資(π=3)
那當然是猜答案囉XD
joy把它認領走後，接著就是瘋狂亂猜
最後丟了47筆才AC XDDDDD好好笑
但就算吃了這麼多penalty他依舊輾壓其他題目
拿下全場第二 \(-- --)/ /(\_ \_)\ \(-- --)/
總之今天這場比賽真的很歡樂~

## Day.15 小樹
### 隨機演算法
這堂課據講師說是最輕鬆的一堂
教大家如何騙過水測資X)
有些題目看似需要很高深的演算法
但是其實隨機就可以唬爛過去XD
（居然連最近點對也可以隨機OAO
當然還是有正經的部分
除了隨機還學到了雜湊函數、rolling hash等壓縮資訊的演算法

因為是最後一堂資訊之芽
講師們也在下課後約吃晚餐
跟講師們聊天聊得很愉快
也發現了他們的一些小秘密 :P

兩周後就是最終的認證考了
由於第一次慘痛的教訓
這次考試我不抱任何期望
就隨緣吧～
反正拿0分我也無所謂
## 驗收時刻 – 二階認證考
### 小樹的考驗
=== **賽中** ===
開場先打開所有題目
雖然真的比上次友善許多
但是我腦袋仍舊一片混沌
看完pA以後的半個小時真的在耍智障
隨便寫了個最小生成樹丟上去顯然大假解
結果後面才真正看懂題目
大概知道做法的方向
但是拖太久時間了，懶得想完整細節+重寫code
於是跳過（記取上次教訓
（1hr flied away）
題目都看完了後（對，我看題目就是要這麼久QuQ
決定先撈pD子題
但是我跟線段樹不太熟，擔心刻爛
所以寫了O(n^2)水水解丟上去->70分
（暴力解就可以拿超過一半分數，這真的很賺欸
再來從pE下手
疑似想到正解，然後就開始寫
這一寫就是一個小時… （我的線段香蕉相交QwQ
（寫到一半突然被前面砸鍵盤的人嚇到
加上之前作業沒有認真寫->第一次寫凸包
寫完以後丟上去，只有50分OnO，重點是只卡一筆小測資！！！
（1hr remaining）
在那邊修修改改code然後一直WA
就這樣你瞪我我瞪你快15分鐘
最後還是放棄了，到這裡也快要砸鍵盤了，但還是冷靜了下來\
跑去寫pC，看能不能撈分
想用個背包解決掉子題，但是code真的寫太慢
剩兩分鐘就放棄了
（05:08 P.M.）
這時又跑回去看pA
往下滑題本，看啊看，看到第一子題
莫名其妙發現輸出0就可以拿到10分XDDDDDDDD
（在最後30秒丟上去XDDDD好爽
然後比賽就結束ㄌ
=== **結果** ===
分數：悽慘的130分／500分。排名：居然有8。
備註：林柏瑄(180)＆林哲宇(沒看到)兩位都把我踩在腳下m(\_ \_)m

=== **賽後題解** ===
聽完題解感想：真的是扼腕扼腕加扼腕啊OAOAOAOAO

講師講pB時我也跟著往下滑題本
（講師：那麼現在來講1、2子題怎麼做
（我：看到mod <= 1e7
大水分啊OAOAOAOAO因為逃避問題60分就去了qwq
只要枚舉1e7+1個字串就好了我到底在想什麼QwQ
還什麼可能要觀察hash函數的性質，最好是啦
其實這題題解真的很酷
利用上課講過的生日悖論
只要枚舉的字串數在sqrt(mod)之間
就有50%的機率找到兩個hash值相同
白話一點，就是有一半的機率會AC

pC要用到換零錢的greedy性質加上DP性質
（這還不是正解ㄛ
出這題的講師是greedy的講師
他真的把我們電焦了（這題沒有人滿分
這題O(n^3)題解難到用講的也不會有人聽得懂
索性就把有關題解的論文放到社群上
（皓神Orz
電電電電電電電電電電電電電電電電電電電電電電電電電電電

pD線段樹，聽說有人被卡常數(?
pE聽完才發現我大假解OAOAOAOAOAO
可以拿到pE第一子題50分
是因為那是三角形一定是凸的
為甚麼簡單多邊形會有凹的啦QWQ

看到這裡的你
一定會想說怎麼沒有pA呢
沒錯你猜對了
我還是不會pA QuQ
所以我想求問各位大神
有沒有人知道pA怎麼做><

=== **心得** ===
二階認證考就這樣結束了>\_<
我覺得這次的狀況比上次好很多
心情上至少沒有上次那樣緊張
精神也還算穩定
但是能力仍然偏差，反應也很遲鈍@@
（一場比賽花超過1/6的時間看題目(\_ \_)||||）
最大原因還是缺乏練習＆經驗
因此我打算利用暑假時間開始刷題（立flag
希望之後能變得越來越強>///<

## 結語
恍惚之間四個月就這樣過去了
2020資訊之芽就在大合照後謝幕
一開始升高一的暑假第一次與C++邂逅
接著培訓時狠狠地被講師還有同學電，讓我看清一切
最後下學期進入資芽，大量密集課程+作業
不斷讓我向上成長，從幼芽長成一棵樹
經過16周，我感受到自己增強不少
終於能夠稍微看見班上同學們的車尾燈，與他們談論演算法
更甚至由自己解說演算法的原理
然而往上一看
有許多人依舊在我看不到的山峰上
因此即使資芽結束了
我也要繼續努力
期許自己也能在這競賽的舞台上發光發熱！

最後
謝謝joy那場團體賽願意讓我躺分
見識到了真正高手的思維，讓我大開眼界
謝謝wiwi願意讓我在半夜的時候戳你問題
不管是手寫還是上機作業
都因為有你的幫忙才能拿分><
謝謝你願意教我>///< wiwihorz
最重要的是
謝謝資芽的團隊，尤其是講師
這16周準備了這麼多豐富的課程
包括那場好玩的團體賽
還有幫助我們解答任何疑惑、甚至幫我們處理bug
這段時間，你們辛苦了！:pusheen_love:
=== 幼芽日記 第二部 終 ===