dwjshift's Blog

GDOI2014 度假记

| Comments

原文发表时间:2014-05-04
反正这次五一去的就当度假了>_<

day0

到了锦盛感觉很多想吐槽的……晚上吃完饭回到酒店发现走在前面的同学被两个熊孩子拉住了,于是就开始了oier大♂战♂熊孩子。打了会cod,大概10点就洗洗睡了。

day1

T1一眼快排。
T2第一眼看成了usaco灌水,敲了最小生成树,没过样例,看了看发现原来不是……然后又想,会不会是状压dp?但是n,m是50啊!于是又逗了,写了费用流,依旧没过样例……再看了看,特么是!于是就一眼了- -
看T3T4的时候挺开心的。T3:哦,数据结构,应该会捉吧。T4:哦,矩乘啊,又把水题调到最后?
第二次看的时候就傻了……T3:我擦, 还带gcd。T4:数据范围500是什么心态?!
于是在这两题之间徘徊。认定T4不会捉了,于是直接写了快速幂,这题我自始至终都没有怀疑过是否满足结合律,最后自然是爆0了。T3想了很久依旧不会捉,看着剩40分钟了就暴力了事吧。最后静态查错没发现什么问题。
结果是100+100+20+0。正解:T1快排,T2状压dp,T3离线+线段树,T4神乱搞。

day2

花了挺久时间才看懂全部题。
T1一眼能看出是dp,但yy了很久依旧没想出复杂度科学的做法,于是写了复杂度是的奇怪dp,最后居然暴力出奇迹……听完题解感觉自己秀逗了。
然后T2太丧病暂时不想写……于是想了想T3,假设两个字符串分别为a和b,那么必定有(前缀完全相同除外)。对于b的每个前缀,求出最长的j使,这个可以用kmp来搞,反过来也要求一遍。然后枚举i,如果的最长的j加起来等于i的话这个就可能是答案。对拍了一下,发现不对,因为有可能算多了导致加起来大于i,所以应该是要找对于的j,……有没有两个加起来等于i才行。但是那样复杂度太慢了。权衡了一下,这样做如果不刻意卡的话正确率也不低,这题肯定是要卡暴力的,不可能又卡时间又卡正确率,于是就这么算了。
接着剩下40分钟赶紧去写T2……最后没调完。
T4什么也没写真是太不值了。
结果是100+0+70+0。正解:T1dp,T2随便选个数据结构,T3扩展kmp+dp,T4各种图论乱搞。
晚上打三国杀+玩奇怪的游戏>_<

day3

就不多说了,没一题会的,T1想了很久断定是传统暴搜,然后就一直优化这题了,最后居然还全WA了……
0+20+0+0=20就这么滚粗了。
出来听说T2拆开后就费用流随手切……sad
晚上继续打三国杀+玩奇怪的游戏>_< 接着打战地到12点多就睡了。

day4

颁奖典礼然后聚餐然后就滚回广州了。
GDOI的收获:认识了若干神犇,补完了一半的冰菓,……好像没了?
然后五一也过了,翘课季也过了……又得去滚文化课了

GDOI

Comments

comments powered by Disqus