dwjshift's Blog

GDKOI2014 水题记

| Comments

原文发表时间:2014-02-27

day0

晚上打了1小时cod10,真是作大死。然后又去看了看后缀数组和线性筛的模板,好像确实派上了点用场(大雾

day1

早上临走前灌了一杯茶。去到学校发现今年人好多……
做题顺序1-2-3-4-3-2。
T1一眼题,直接写了个分解质因数然后div乱搞就弄出来了。一开始复杂度算错了还写了线性筛预处理质数……
然后去做T2,一开始没看到是一棵树,就往网络流去想,不过太弱没想出来。
接着又去搞T3,看题的时候觉得蛮可做的,一开始往主席树去想,没想出来,又想了想分块乱搞,还是没想出来……前前后后想了差不多40分钟,于是就先留着,去水T4暴力了。
T4暴力水完又回来想T3。最后什么也没yy出来,就写了个乱七八糟的优化暴力,各种常数优化后3W的数据跑了5s,就希望出题人能给个1W的点,最后还是没有……
然后终于看到T2是一棵树了……想了想树形DP,但是万万没想到可以直接忽略油量,最后什么也没写。
剩下半个小时就检查了- -其实也没查出什么。最后该拿的分都拿到了。100+0+30+40=170。
下午听完讲课没什么感觉,但T3没懂为什么不用快速幂……晚上又去问了hsl各种问题,原来T3是用逆元搞就直接修改,出题人不讲真是坑爹。他又跟我说T1很多人跪了,我这破分能到20名左右,于是我就挺高兴地洗洗睡了。

day2

早上国际惯例灌了一杯茶。
做题顺序1-2-3-4-2。
第一题一开始看的时候脑残了,以为又是差分约束,码出来后发现样例都过不了……多想想发现这不就是记忆化搜索水题吗……
第二题如果没修改的话就直接是贪心一眼题了。但是加上修改就挺麻烦了。一开始想着看看能不能用堆,但是显然不行。然后又想了想其他数据结构,上厕所的时候发现可以用线段树搞:每个区间维护两个东西,一个是,表示这个区间所有的的和;另一个是,表示这个区间需要的最小内存。我为了省事就直接按来建树,动态开点,复杂度
看第三题发现跟后缀数组的一些题挺像的,然后略微想想后就写了个后缀数组出来,又求了height数组,连用线段树维护height都写好了。但是突然发现之前学后缀数组的时候没认真看怎么搞多子串匹配,不会用了……只好改成kmp暴力,复杂度1亿,本来希望能水过50%的,结果第7个点才开始TLE,但是4,5,6都迷之WA了……
第四题看完直觉:不可能做出来(大雾 于是就写了个暴力,还忘了判环,就爆0了。
接着还有时间,感觉第二题不太放心,于是又回去对拍第二题,一开始WA了,发现是暴力写挂了……改好后又WA了,剩下15分钟,吓尿了,发现EDchecker真的ED了……又改好后好不容易AC了。接着又试了试极限数据,直接没输出,再次吓尿。一调试发现是爆了maxlongint,改好后就考试结束了。真是锻炼心脏。
最后还是基本该拿的都拿了,100+100+30+0=230,就第三题有点遗憾……
下午讲课真是太有感觉了。章文杰上去讲了四道题听得我整个人都斯巴达了。听完第四题感觉这做法真是太神了(hsl:“最后一题送分的啊”)。

正解

day1:T1分解质因数乱搞。T2树形dp/上下界最小费用最大流(那个段雷讲的不带上下界的网络流似乎是错的)。T3莫队算法(其实这题是有在线做法的,好像是分块乱搞)。T4自动机。
day2:T1拓扑排序+dp/记忆化搜索。T2线段树。T3后缀自动机/后缀数组。T4巧妙地转化然后水dp(放在T4简直丧心病狂!)。

Comments

comments powered by Disqus