TOI選訓營第二個禮拜心得~~

Gate 奇幻自衛隊
Gate


TOI一階已經結束三天了,不過之前很累就拖到今天才寫心得。
這次幸運的進了二階,大學也有著落了,但是手機不見了,所以心情五味雜陳。

第二個禮拜的生活

依照前兩次的記憶,我通常第二個禮拜都再耍廢,寫些奇怪的東西之類的。因為之前一模考爛掉,所以第二週都會不知道要幹嘛,要玩也不是要認真也不是。
但是這次來之前做好心理準備了,無論是有入選還是沒入選,都要好好打好打滿,所以這次第二週倒是沒有特別的心情起伏,出了一些廢題,吃飯睡覺,沒網路就打打世紀帝國,發現我還是不太會玩這種要快速反應的遊戲QQ。
第二週的心理輔導課程是壓力,和我第一次來選訓營的心理輔導一樣,這次的課程我覺得比第一週的更符合我們的需求(第一週是維持網路上的人際關係),上完這次課,有些勵志的感覺,課程用一句話總結的話,就是只要你打從心裡認為壓力是你成功的一個助力,那你將可以把壓力轉換成能量。

這次教授因為顏瑞楠的遊說,把CMS又打開了幾天讓我們練習,所以很多人都去把第一週的題目AC掉,可是我不太想要再回去碰了,所以連登入都沒登入XD。

TOI二模

這是我的第三次二模了,這次非常驚喜的,系統是Ubuntu系統而且有附贈Sublime Text3!!!!!雖然因為我不會設定3的編譯設定檔,所以沒辦法用快速鍵編譯執行,但是能用Sublime寫還是很棒,至少手感順很多,編譯就用Terminal,也不會很麻煩。

但是這次的模考出了很多狀況,首先是一開始Judge會莫名的CE和WA,導致很多人寫IOI考古題得到了WA卻找不到BUG。不過這沒有影響到我,為什麼呢?因為Ubuntu一開始沒有網路密碼,所以根本沒辦法連上Judge QAQ,所以我第一個小時完全都在想題目還有寫掉考古題,不過這也算我運氣好吧,要是一開始可以傳,我可能會整個很緊張就爆掉,至少一開始不能連網對我不一定是壞事。
接下來,Judge又無預警的壞了,教授出來說明說是因為硬體出了狀況,所以可能會變成賽後Judge,一說完大家整個大爆炸,可是也沒辦法,這時我還在De PA的BUG,所以也沒時間裡他QAQ。後來Judge暫時修好了20分鐘,教授也決定延長一個小時的比賽時間。然後Judge又壞了,教授決定用另外的機器去開第二個Judge,最後教授叫我們全部人去登入另外一個Judge,時間也只剩一個小時多一點,於是教授又再延長了20分鐘。最後比賽總共比了5個小時20分鐘,真的非常的累。
不過我運氣很好的,幾乎沒有被影響到,不如說如果沒有延長時間我可能會爆炸吧。

第一題,題目是一定要取某一個點的最常嚴格遞增子序列。
題目一開始沒講清楚,導致大家都寫了奇怪的DP,後來加了一個條件才變成現在這樣,於是就變成了水題,可是我卻一直都拿0分,以至於我都寫了N<=15的爆搜了,不過說來奇怪,我寫完爆搜後AC的竟然是最後三筆而前兩筆還是WA,於是我繼續找BUG,後來以為找到BUG,但是還沒傳就發前已經AC了!?!?!?!!?完全不知道發生什麼事,反正這之後分數就一直跑出來XDDD。

第二題,題目給你一個很多三次方程式乘起來的函數$ f(x) $,給你一段X軸上的區間[L,R],要你找出 $ g(x) = f(x)(ax + b) $ 滿足$ g(x) $在[L,R]裡大於0的區間長度和小於0的區間長度比值介於0.99到1.01之間。限定a和b的範圍,請你輸出滿足條件的a,b組數。
這題我最後以0分作收,完全沒有去試。題目作法應該是先解方程式,找出所有的根,然後用前綴跟後綴維護答案,枚舉a,b來檢查答案。比較簡單的15分作法是,把區間[L,R]切成0.01的小塊,用迴圈去做,就可以不用找方程式的根了。最後這題沒有人100,最高分15。
這題我賽中就想到了上面的解法了,但是依照經驗,強烈覺得這題難在做法不是想法,所以果斷跳過。雖然15分沒拿到有些可惜,但是這次分數勉強算夠了。比較要後悔的是一模的很多分數沒拿到。

第三題,給你一個長度$ 10^6 $以內的字串S,S是一個十進位數字,他的每一個子字串Sij也都是一個十進位數字。如果Sij可以被數字M整除的話,就放進集合A裡面,求集合A中的數字總和$ MOD 10^9 + 7 $。
這題前面都可以用餘數來DP,做到N平方的複雜度。但是如果要線性的話,就要分成$ gcd(M,10) == 1, gcd(M,10) != 1 $ 兩種情況來討論。前面那種,可以直接用前綴後綴的預處理去做,複雜度是線性;後面那種,就必須討論一些狀況,不過我還沒理解。關鍵的式子是 $ A mod M - B mod M <=> (A-B) mod M $,其中去的箭頭是對的,但是回來的箭頭就必須要滿足M和10互質才成立。
賽中我直接寫了DP拿了39分的樣子。還有一筆DP,感覺複雜度是對的,可是沒有人用那種拿到分數,全部TLE了,那筆應該是29分。

第四題,給你40個數字,你可以從這些數字中挑一些子集A,請你計算滿足子集A中的數字的乘積%P為1的子集數量,也就是有多少子集的乘積除P的餘數是1,這裡保證P是質數。
這題我賽中其實沒有想到關鍵,只是亂報搜加亂用餘數DP,拿到了72分,其他人有些寫正解的,也只拿了72分XD,所以我運氣很好。
正解解法是,從中間剖一半,前後各有$ 2^{20}-1 $個數字,分別稱為集合A和B。因為P是質數,我們可以保證存在模逆元,而一個數字乘以自己的模逆元將會變成1(MOD P的情況下),所以問題轉化成,對A的每個元素,檢查B中有幾個數字是自己的模逆元,如果先把B中的數字都取模逆元,就變成對A中每個元素檢查B中有幾個數字等於自己。另外,又有一個定理,就是$ AB^{-1} == A^{-1}B^{-1} $,所以我們可以先對後半段20個數字取模逆元,再枚舉乘起來放入HashTable中,這樣複雜度就變成O(N)了。

第五題,IOI 2015 Day2 Horses,因為一模考古題有點慘,這次考前很認真的記了一次寫法,而且這題我一開始就是自己想清楚而且沒有什麼BUG就AC的題目,所以這次只CE一次就AC了,CE是因為init()打成Init()。

比了這麼多次,心得就是,比賽還是要靜下心來,把能夠拿的分數拿到,不然要是卡再某一題,可能就會爆炸了。其實這次,我的分數主要都是靠小測資拿到的,所以會拿小測資真的很重要,最後幾筆就靠喇分和最後剩下的時間再慢慢想正解,這真的很重要。

手機不見QQ

考完模考可能是太爽了,從師大上了回宿舍的公車,下車後手機就從口袋中消失了,客運公司說手機不再車上,我又沒有開網路,所以這次手機就真的不見了,以至於我現在都還在鬱卒。打電話去把他停話、去警察局報案,接下來就看運氣啦,不過應該是沒救了。

有大學念了

說來奇怪,之前想了很多,做了很多,總是很激動的覺得考試制度很爛啊、很想上大學啊,可是發現上了二階後有大學了,卻突然一股不真實的感覺,其實我到現在還是不太相信自己有大學了。看著買好的指考參考書還有原本的讀書計畫,突然都好像用不到了,倒是原本打算放到7月再寫的Project,現在好像都必須要開始動工了。不過這個真的太難接受了,所以我決定再繼續耍廢一下~。
不過讀書真的很單純,就讀就好,可是現在不用讀書後,耍廢也不知道要幹嘛了。現在的工作好像就是寫程式打LOL看動畫,可是我卻想要先把原本打算寫完的數學學資寫完,真是超詭異的。

Gate

這此一階看的就是這部啦。畫風還滿不錯的,雖然是後宮可是主角卻是大叔。故事大概就是,日本境內突然出現了一個傳送門,連結到了一個異世界,異世界人就跟開港前的中國一樣愚昧無知,被日本人打爛了。可是這次日本人沒有大舉侵略反而想要好好的外交一下(根本是日本自衛隊的廣告嘛XD),不過異世界的帝國當然是跟開港前的中國一樣不但很廢還耍一堆小手段,總之這部就是看現代科技超猛敵人快嚇死很爽這樣XDDD。當然還有很多細節跟劇情,妹子賣萌的片段也不少,而且主角是個外表看似肥宅,戰鬥力卻過於常人的日本特戰隊隊員XDD(特種部隊的樣子)。
總之如果喜歡後宮還有爽番的話,這部五顆星。

鄰座的怪同學

這是去一階前看的,不過一階在看Gate所以等回來後才看完。
好像是2012年的動畫,在網路上看到就跑去看了,我好像意外很喜歡看少女漫畫系的動畫QAQ。
反正沒什麼特別的就是又有一個好學生跟一個壞學生,結果好學生很迷惘壞學生沒那麼壞,然後在一起這樣XD。
不過這部還有加了一堆有的沒的,可是鋪了一些梗卻沒有收完,結局也好像沒有結局一樣,感覺就是要拍第二季結果沒拍一樣…。
不過好笑的地方還是都滿好笑的,很好看,可是沒有結局QQ,也許可以去看漫畫或是小說。

總結

這篇打了好長啊,總之,高中弄了那麼久的資奧終於進了二階很開心,手機掉了很傷心,接下來除了拚一下之外,一些專案也要開始動工了,現在離7月還有90天,這九十天可以讀完指考也可以寫完很多程式,希望我可以好好利用別人無法擁有的這些時間。