GDKOI 2016 總結

前言

這是第一次去GDKOI，本着鍛(bei)煉(nue)的心态出來見世面。但是自從去年參加GDOI去打醬油連獎都沒拿被虐飛（悲傷的故事），我就決定要盡自己所能把比賽做好。可是緊接着的NOIP又是一個夢魇，兩天給虐到270分（悲傷的故事）。一次一次都挂掉了，盡管心裡非常不爽QAQ，卻沒有辦法。上個學期與這個寒假，我惡補了許多知識點，刷了十幾道題。想着去年挺水的，今年應該有300分的。我決定用這一次的KOI來複仇。

Day0

愉快地坐車來到了廣州，在車上欣賞着窗外的風景，聽着歌，睡一覺，腐一會敗，十分惬意。我們小隊隊長神牛Alan帶領着10個人：Alan,doubleZ,doubleZ,howarLi,howarLi,Bigzao,Jimmy H,ch,hxy和本人lyd，我們年級其他部隊有xhm,jy等人。另外很遺憾andy沒有來。我們JZ大部隊在西苑吃了晚餐。這次和NOIP一樣，住在莫泰酒店，離廣州六中非常近。我和doubleZ一個房間，我們是最不腐敗的一個房（據說有人12點才睡），還認真學習了半個鐘（表揚~）。初一二在我們房開會，主要還是講政策問題。我和doubleZ 10:30就睡了（表揚~）。

Day1

早上酒店的爐竈竟然壞了，沒法在酒店裡吃。

考場外我一直在問Alan斜率優化DP，太久沒打快忘了。

因為一些神奇的原因，拖延了10分鐘，8:10，比賽終于開始了。

比賽

今天題目的解鎖密碼是ProblemsAreEasy，我隻想說這絕對是假的。

一開始先看題(我旁邊有一個zuodie的人剛開始比賽就敲起了鍵盤)。

T1，好像挺複雜的。題目要求支援區間查詢和單點修改，要把在區間内的所有子區間的xor和全部算出來。線段樹好像會遺漏一些答案？怎麼計算？暫時不知道。這題我看到模數是100,000,007，是1e8+7！！肯定有不少人會被坑打成1e9+7。

T2，又是數學期望。我們賽前訓練做過一道樹上的期望值的題目，但是和這道題遠不相同。樣例模拟了5分鐘，算對了答案。通過推廣，發現這道題不同走路的順序是會影響答案的。于是我猜應該有一種貪心的政策能定下順序。于是自己推了推，發現怎麼都推不出來（flag：數學太弱）。

我一驚：去年Day1前兩題這麼水，今年是不是要被虐了？

再看T3，好像是排拓撲序然後貪心選取。怎麼會這麼水？想起之前被GDOI坑過，我再看了一遍題。手算幾個點好像都對。

T4，一點思路都沒有。暴力很明顯會逾時而DP又想不到。于是選擇擱置一邊。

于是決定先搞T3。很快碼完了。調過樣例，用手算的點，都過了。然後突然注意到分母可能為0，于是加了特判。出了極限資料，不會爆。

這時候回過頭看T1，突然有一個很簡單的想法，在草稿紙上推了推，直接線段樹維護，感覺好像可以過。我就很興奮地打起鍵盤，打着打着，突然又發現我又推翻了我原來的結論，這樣做很明顯不可行。浪費了15分鐘，還是挺不爽的。盡管經常犯這樣的錯誤，但是還是沒能避免再犯。以後遇到題目，如果有想法，一定要想周全，确定對了再開打，避免浪費時間。這時候想怎麼處理bug，但是并沒有想出來。很可惜地放棄了第一題，決定先打T4的暴力。

思路很直覺，能多暴力就多暴力，但是代碼有點惡心。竟然打了我半個鐘（flag：以後碼程式要快些）。樣例還錯了，原來是數組初始化的問題。改完這道題花了我45分鐘。比預料的長得多。這時候時間不是很多了，這題我并沒有打拍，畢竟暴力應該不會錯的，而且隻能騙30分。

然後還剩前兩題。第二題又推了好久，依然無果。已經11:20了。我毅然棄療，打完第一題暴力，第二題匆匆打了個水法。

剩下的時間就檢查程式，為了保險，我開了T3的long long。

最後十分鐘，我瞄了一眼草稿紙，突然發現左上角寫着”I64d”，這是比賽開始我為了提醒自己寫上的。但是漸漸就忘了。T3輸入還打着“lld”。于是馬上改成I64d。還是挺險的。

考試結束，Jimmy H大吼：第一題大暴力，第二題大水法，第三題大水法，第四題大暴力（臉皮真厚）。

出考場，我以為就我沒打出T1。然而還是有許多小夥伴表示第一題不會。howarLi表示想出了線段樹維護，于是受到了一群人的嘲諷。

而我和Alan則表示T3可能AC。Alan說要用01分數規劃，和我不一樣。總之考完了就不要過于糾結。

聽課

教室在中大裡面。要坐地鐵。我們發揮團隊優勢，一群人在教室裡腐大敗。

3:00終于開講了。

進入正題，T1有位神犇上去講了，東莞東華的一位大神也上去了，開10棵線段樹，howarLi表示和他的方法一樣，不過他開了31棵（于是他又受到了一群人的嘲諷）。

然後各位出題大神講述自己的經曆（%%%）（還有JZ的師哥OYZH）。

T2是東莞的那位神犇又上去了，随便推了下式子，一個貪心政策就出來了。然後排序，根據排序順序貪心地計算即可。

T3是出題人說是最大權閉合子圖的模型，跑網絡流，我一驚，果然貪心選取是不行的。後來吃飯的時候Crazy告訴我們DP時會有後效性的，能水40分真有些RP成分。

T4是插頭DP模闆題，OrzPhilips，蒟蒻表示不會。

然後出成績了，30+0+40+30=100，T3好歹水掉40分。和我意料相差不大。

今天還算比較穩，暴力分基本拿齊（竟然有個初一的水到110分了）。

晚上

doubleZ帶領一群人去廣州塔了，真有閑情逸緻。

晚上，我和doubleZ玩BOB(battle of balls)，好浪啊！！

還是在我們房開會。

晚上睡得不是很好，醒來了幾次。

Day2

早餐囫囵吃完，時間有些不夠。

我們一直都在猜今天會考的題型，Alan和我又在讨論SA。

比賽

到達考場，又因為某些神奇的原因拖延了15分鐘。

8:15進考場。

今天的解鎖密碼更6：HopeYouCanAK!!

一開始先看題（昨天那個zuodie的人今天依舊）。

T1，好像是博弈論，之前聽說過，但是從來沒接觸過。看到樣例，模拟一下，我發現連樣例我都不知道是怎麼計算出來的QAQ。

T2感覺可做，根據樣例，還有評委熱心的提示，很好懂。但是題目很令人吐槽，許多東西都漏掉了。答案對10007取模（會不會有人打成100007呢）。我又把這個模數寫在了草稿紙上。感覺難點就是要求出一段區間的要求的特征數的總和。這東西我腦子裡突然閃了一下：數位DP。我們以前做過比這更簡單的題目。然後我推了下DP，發現要記錄前導0和第一位比上限小是第幾位。這樣不會爆空間嗎？

T3看到檔案名是necklaces2，就感覺是去年Day1T1的加強版，果不出我所料。隻不過支援删除連續區間，要求最長回文串的長度。但是第二個樣例好像不對。沒有細看。

T4名字叫“國小生數學題”，出題人你又來逗我們了。

看來這道“國小生數學題”很不簡單啊。隻想到了30分做法（其實就是大暴力）。

再看T2，50分做法其實也很簡單，時間複雜度 O(4位數) ，可以壓線過。于是打完了50分。應該是妥妥的了。

我又想T1，整面草稿紙都畫滿了，終于明白了樣例。然而還是一點頭緒都沒有。白白浪費了40分鐘。

然後時間不是很夠了，我飛速打完T4暴力，30分資料範圍的程式連樣例都過不了。但是試了幾個小資料好像是對的，然後就沒有理它了。

時間有些緊，但是我還是選擇穩一些，打T3暴力， O(len4) ，水20分。但是打完居然還錯了，調了20分鐘才過第一個樣例（flag:打程式一定要細心）。但是第二個樣例還是不明白原因，抱着沒什麼時間打了改了又容易錯而且目前還不知道哪裡錯了的心态，我毅然決定棄療（一開始看題，就一定要看清楚，多看幾次題目，千萬不能看錯題）。

這時候沒什麼時間了，我回來檢查程式。

無意中瞄了一眼草稿紙，猛然發現一個神奇的數字：10007。唉，這是啥？再一看黑闆，一切都恍然，于是驚險地把T2的模加上（看來這次比賽的政策還是不錯的，重要的東西要寫在草稿紙上，至少這方法對我挺管用的）。

然後最後的10分鐘，檢查檔案名，都沒有錯誤，繼續磕T1，還是無果。

出考場了，Alan，howarLi，xhm都表示打出了T2的數位DP并且有可能切掉。此時的我悲痛欲絕，因為我早已想到數位DP的解法。對于我卡的那個地方，Alan表示隻需要用01狀态記錄第i位的前一位是否小于上限，我表示智商都被Day1耗盡了，Day2隻帶了一雙手去。

這透露出來我思考問題的能力還不夠，昨天開會時我還說過，對于一個想法，既不能太大膽，也不能太保守。今天的我是太保守了，面對一個困難，根本沒有去思考如何解決，就把這個想法放棄了。

聽課

感覺今天要跪了。

心情較為壓抑，好在有各位小夥伴，我還是高興地去聽講了。

直接進入正題吧。

T1又是東華的那位巨犇上去講的。這是我博弈論的第一題。其實對于這類題的通解是基于貪心思想的搜尋，每次搜尋都盡可能取最大（或最小），通過局部最優解推出全局最優解。然後可以加一些剪枝。

因為某些原因，T4先由主評委評講。

一開始，他給國中同學普及了逆元等知識（感覺被大神鄙視了）。

緊接着直接出來一大坨式子推演（flag:數學很重要），可惜聽不懂。

T2是最簡單的了，直接數位DP就好了，這裡不多說。

T3的講評十分熱鬧，幾乎成了紀中的專場。一開始，World_Wide_D上去盜用Samjia的稱号講了一個manacher+回文樹，但是有個漏洞，然後又是東華那位大神上去，說SYP用腳趾頭想出了一種反例，迅速推翻了結論。接着各位大神接連上去，分享了自己的方法。大概就和World_wide_D的差不多。twilight用桶排寫出了 O(n) 的複雜度，比标算還優（%%%）。

心情不好，因為馬上就要開學了QAQ。

評委說，請中山紀念中學派若幹個代表（龐大的隊伍）上來領取你們的成績。

最後，我以0+50+20+0告終。T3過掉的竟然是第4,5個點，如果比賽時能加上雙回文串的判斷，這樣就能多水三個點了。令我比較滿意的是T2如願拿到50分，可是T4的暴力至今不知道哪裡錯了。

可憐的XHM第二題打錯模了（驗證了我的預料）。昨天那個初一的今天又水到90分了（%）。看來，打好優美的暴力和水法也是一件重要的事。

賽後

兩天是100+70=170分，本來以為沒有AU了，最後國中AU分數線是140分（為什麼這麼低？）

%%Alan230拿到了全省國中第五。

這次比賽，我的表現還算可以，至少沒有跪掉（大神勿噴）。

初二，時間還夠，這也算是一次很好的鍛煉。不僅僅是知識，而且是心态、政策。

其實，比賽的偶然性很大，一次比賽并不能說明什麼。

好好做好每一次比賽，GDOI也要更加給力。

路途很遙遠，要一步一步，踏踏實實地走。

自己選擇的路，就算跪着也要走完！