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也要更加给力。

路途很遥远，要一步一步，踏踏实实地走。

自己选择的路，就算跪着也要走完！