2021台灣資訊奧林匹亞研習營初選

差點成為最後一次的成果驗收(?
話說也是這個blog滿一年欸，第一篇就是去年初選。

賽前

前一天去打機打了一整天，其實對心態幫助頗大(?
到了晚上也沒那麼緊張。
不過隔天進到了電腦教室還是有緊張感，不過已經還好了。可是在賽前大約15分鐘的時候發生了一件事。
電腦教室很熱，我穿著三件衣服所以想脫，然後我就很順手的把衣服給拖掉，在脫下來的時候我聽到了啪一聲，我的鏡框壞了。
我整個緊張感都上來了，一直想辦法把它弄好，但是他似乎沒救了。到比賽開始5分鐘前我覺得就不喬了(不然越喬越荒)，相信著這影響不了什麼。
所以我就帶著常常掉下來所以得一直重戴又歪一邊的眼鏡，還有因為這件事變得超級緊張的心情開始了

策略

我前幾天規劃出來的策略是

1. 開場花不到20分鐘把每題題目子題看完，同時每題花不超過兩分鐘想直覺的解。
2. 把那些直覺的子題根據確定性與實作難度一個一個拿掉(大約在1:00 ~ 1:30內做完)。
3. 剩下的題目每題想20分鐘，同時開始刻需要資結的題目。

每一個小時都要出去吃東西。
寫出題目或寫不出題目都要喝水上廁所。

第一小時

在20分鐘內把題目都看完了
每題的想法:
pA水題，pB小測資dp，pC可能是怪dp，pD的O(nq)感覺很可做，pE似乎就是炮打皮皮。
同時模板也打完了，花五分鐘把pA給翻綠。
然後開始刻pB的dp，大概花20分鐘後還是過不了範測，把dp的過程print出來後越想越怪，去重看題目才發現看錯了，我以為每個地方的時間函數都是用當前時間t，結果是分開計算。

第二小時

我很快地想到這題跟TIOJ上有一題一樣，而那題關鍵的想法就是枚舉最多取到第幾個(因為回頭肯定不optimal)，然後就用pq拿了30分。
花了五分鐘想想看滿分解，然而沒想法要怎麼優化pq的行為。
把pC重讀了一次，大致列出了轉移式，推一推發現這好像就是二維偏序了，可是要輸出解很麻煩，總之先拿暴力55分之後再補上資結。
寫一寫發現又跟範測兜不上了，所以又去重看了一次題目，發現他的輸入格式比我想得還毒瘤。
花一點時間把輸入處理成二維偏序，然後就上傳看看，WA，此時已經過了一小時半。
我的心態其實已經有點小炸，在比賽過了一半的時間中我卻只拿到130分。
後來發現了一些處理輸入時沒弄好的bug後，還是0分。
出去喝水吃東西上個廁所，回來改點穩一點的寫法，0分。
一直到1:45左右，我的心態已經炸到谷底。
此時我想起zck說過發現自己在原地打轉時就要想辦法跳出，我也才發現我居然到現在都還沒出去吃東西。所以我就出去吃個東西，去廁所安定一下心情。
回來後想到了不知道誰說過不能有0分的題目，所以我就先去拿拿看DE，pD的O(nq)又是有點小煩躁的實作，不過幸好把題目的條件都打進去後就拿到了16分。

第三小時

已經到了最後一個小時了，500分中拿不到150分，可說是最慘的結果。
原本會是這樣想的，但是重新拿到分數後對心態回復蠻多了(上一次拿到分數是一小時前的pB，整場有一小時完全沒分數)。
所以就去寫pE，確定是炮打皮皮後就刻了匈牙利，稍微想了一下該怎麼構策略發現沒想法於是決定就拿24分就好。
寫六分鐘丟上去後吃WA，發現沒輸出策略。
再丟上去還是WA。心態又開始有點不穩了，不過我還是靜下心來好好的看code。
匈牙利已經簡單到不太可能刻爛了，所以應該是其他地方有錯，但這題應該就是炮打皮皮沒錯。
過了大概10分鐘，我就想到了輸出的問題。
在2:27把行尾空格全部去掉後丟上去，24分到手。
我當時整個超氣，輸出嚴格比對到底是怎樣，搞人嗎??我直接被吃掉10幾分鐘。
但此時我想到pC會不會也是這樣的問題，原本我的pC的輸出長這樣:

// id是輸出第一項 nxt代表他的下一項 id為0代表到了結尾 arr[id].i代表第i項的編號
while(id) {
    cout << arr[id].i << ' ';
    id = nxt[id];
}
cout << '\n';

我就改成這樣

cout << arr[id].i;
id = nxt[id];
while(id) {
    cout << ' ' << arr[id].i;
    id = nxt[id];
}
cout << '\n';

然後就把暴力的55分拿到了。火氣整個上來了。
被卡了一個小時居然是這樣的原因。
此時離比賽結束剩下30分鐘，因為在兩分鐘內pC的55分和pE的24分實在有點多(跟我可悲的分數比起來)，所以讓我心態回復很多，我決定好好地把比賽拚完。
看了BCDE，還是決定把pC套個BIT拿滿，畢竟當初寫部分分時就已經用著可以很方便改成資結的寫法。
寫完BIT之後一直吃WA，但我不想放棄，我不想放棄這45分。
一樣把各種東西跟當初的暴力解法比對之後還是找不到bug，所以我就把operator overload的部分改成cmp函式。範測過了
在2:46的時候丟上去，100分。
此時的我雖然開心，但是卻又不安，因為在策略中，我在比賽結束前10分鐘才做到第二點「把開場讀完題的子題一一收掉」，在第三點中我給每題20分鐘時間想，但是已經沒時間了。
最後十分鐘就盯著pB嘗試通靈，但是還是沒想法。

賽後

其實我結束當下整個不安感就上來了，我花了三個小時僅僅只是把基本的分數都拿到，我預估線大約落在280-300up，高中的競賽之路就到這裡結束。
不敢看計分板，戴上耳機後就離開，不過我發現到我沒有眼鏡不太應該在大街上自己走，所以就打開手機然後發現nathan要過來，我才知道大家集體燒雞@@。
總之，看來高中競賽之路還沒結束(?
可是今天的問題都蠻嚴重的，就是我只是剛剛好把基本分給拿完，我的實力還是跟其他人差了一大截，尤其我想題都會想不太到，今天都是看過的題目(pB 二維偏序 炮打皮皮)，遇到沒看過的很容易燒雞。