GDOI2016总结

前言

第一次GDOI,收获了很多。
这几天下来的生活有趣而精彩,尽管我没有高级的腐败工具,但是还是通过偷抢拐骗各种方法满足了腐败的欲望了。
BUT,参加GDOI可不是为了玩耍,而是去提升自己的实力,磨炼自己,正如我们的“liyun”同学说的来这里是为了超越自己。
好了,不多说了,讲讲这几天的行程吧。

day0

中午从学校出发,经过两个多小时乏味的行程后,终于来到了肇庆。
出发前,为了弥补没有高级腐败工具的遗憾,我在家里下载了N多部美剧,准备用U盘插到酒店的电视上看。
走进我的房间后,第一时间我就冲到电视旁,经过初步观察,竟然没有USB口!!!
刚开始,不敢相信这残酷的现实的我认为,USB口只是有点隐蔽罢了。于是我拿出手电筒(不要问我为什么带手电筒来,无聊而已),把电视搬了出来,打开手电筒各种寻找,经过了10多分钟的努力,最后我还是无奈地认命了。。。我B~神马破电视,上个世纪的吧,连USB口都没有!
幸好,我的室友带了手机,于是我腐起了他的手机,来泼灭我心中的怒火。
祸不单行,当我腐了两个小时的大败后,我决定去隔壁逛逛,发现隔壁的同学们居然不见了!我和舍友讨论了一下,一致认为,他们都去吃饭了,狠心地抛弃了不清楚情况的我们,s
t。最后,只能用泡面充饥了,呜呜呜~

day1

早上,房间的电话竟然只能打不能接,结果morning call打不进来,最后在7:00被接送车的警告声吵醒了。
(不得不说,早餐的肉包挺好吃。)

T1

显然是一道数学题,我在草稿纸上乱搞了几分钟没想出来,果断跳到了第二题,后来打了个O(n)爆搜,想坑个50分,结果爆零了。
题解:找N中点和三等分点,就是n1和n2了。听了题解,简直想去**,O(1)的复杂度,而且还是在平面直角坐标系中搞搞就出来的!据说有个初一的水法二分居然水个100分,天理难容啊!

T2

要找最大最长子串,刚看到题目时还挺开心滴:前几天才学了kmp,居然能派上用场了!但当我再次认真地看一遍时,我瞬间崩溃了,竟然还能在区间调换字符的位置,还搞个p啊,区间还那么多。接着,我想了想,发现区间是可以合并滴,也就是说最多只有2000个区间。然后我想到了一个大水法,搞一个字母前缀和,对比区间中字母的个数,O(26·n^2)。接着我浪费啦2h去搞这道题,最后因为细节太麻烦,忍痛放弃了,~~o(>_<)o ~
题解:dp

T3

题目很神奇,正如打开题目的密码所说,有毒啊。
看了半天才看懂题目,样例数据恶心到算不下去,果断放弃。
题解:没听懂~~

T4

这道题故事很精彩,我看地津津有味,没想到他笑里藏刀,复杂得连暴力都不想打。
题解:树链剖分+可持久化;听了等于没听,听懂了还是不会打。

晚上

腐了整晚。

day2

T1

题解:把图分成2·lim层,搞一遍最短路就可以了。
明显是大水,一开始我还把他想复杂了,当成费用流,由于不会打费用流,于是我把大部分时间去想第二三题了,没有认真想第一题,暴力了个二十分。唉,我的80分飞走了╮(╯▽╰)╭,“被水淹没,不知所措”。

T2

感觉明显是个暴力,这不过调了1h才调完,刷了40分。
题解:搜索加上各种恶心的优化。

T3

这道题60分的k<=100,想了个水法,首先把图变成一棵树,O(nk)把树上对答案的贡献求出来,接着再把原来删掉的边搞回进去,求出新增的贡献,再判一下重。不过判重部分没想清楚,只打了个暴力。
题解:乱搞,别问我,反正我不懂。

T4

一道恶心的不能再恶心的题目了。
题解:同上。

晚上

首先感谢真的李腪同学的赞助,在他的手提电脑的帮助下,我的辛苦终于没有白费,看了几部我下载的美剧。

day3

早上各种玩+旅游;
下午被虐。

day4

有趣的比赛生活就结束了,又要回到学校的恐怖生活了。

总结

一、看题不能用太多时间,否则会耽误打题的时间。
二、对第一题不要想得太复杂,总之不会太难的。
三、想到水法一定要打,打暴力要想各种优化,“暴力出奇迹”!。
四、要有一个良好的心态,不能太自信,也不能总是想着会被虐。

原文地址:https://www.cnblogs.com/chen1352/p/9026685.html