首页 > 代码库 > GDOI_2017 爆零记

GDOI_2017 爆零记

//writeln(‘本来不想写的,但是老师说一定要总结一下,所以。。。’);

(注:全文有关测试点都是从0开始)

今年GDOI和去年一样又炸了,30+10=40,没得奖。

Day 1

做题的时候,首先看到第一题,想了一会觉得有可能是kmp,但是又不会写修改,所以只能打了一下暴力。本来打完暴力信心满满,想着能水个50分,再考场上手算了一下时间效率,大概可以过,此时已经快9点了,赶紧看第二题。

一看第二题,怎么开有一个文件叫game_full.pdf”?打开一看,4页内容!要看到猴年马月。然后我就直接跳过看第三题。WeChat!给定n个字符串,包括小写字母与<(退格),按照要求寻找最长公共子串。第一反应就是暴力水一下,暴力搜索最长公共子串。打完了觉得第二题没看比较浪费,所以看了一些,觉得很meng bi,好像是说在一颗有根树上寻找不再第i个点的子树集合内的最小非负整数(树上每一个节点都有权值),随随便便打了一下,过了样例就不管了。最后剩下的时间还有差不多1.5小时,看了一下第四题,觉得是推公式,但是三角剖分的公式又不会推,所以只能随便打了一下,没抱多大胜算。最后还有1h,回看了一下T1T3测了一下T330%数据,卡了好几秒。T1又不知道怎么产生测试数据,所以没打。最后又回看了一下T2,再重新打了一下,检查了文件名,比赛结束。

讲题。T1果然是kmp,后悔没去看熟。T2听了题解之后说是lca乱搞+启发式合并,不会打啊。T3可以把字符串看成一个tire,用后缀自动机或二分+哈希。T4 DP+推公式解方程+FFT/NTT(SMG)

拿到成绩,30+0+0+0=30,于是复评,T1似乎第3个点是卡了4s多,只好作罢。T3莫名WA,可能是暴力打挂了。

总结一下,T1再考场上时没有算准效率,因为PascalposO(n2)的效率,没有考虑,所以100%的效率大概为O(length(s)n3m),肯定不会过。T2题意太长,没有认真看。T3的话要多拿几个数据测一下,考虑特殊点。T4不会推公式那也只好作罢。

Day 2

一拿到题目,看到第一题就想到BFS,但是爆搜又觉得数据太大,不会过,所以想了一下SPFA,发现可以写。但是我计算了一下效率应该能过,但只是手算了一下时间效率,并没有考虑空间。于是发现已经过去一个多小时,赶紧看T2T2给出n264-1的非负(还是正?)整数,求第i个数与第1i-1个数的二进制中汉明距离(两个等长字符串内相同字符数量)等于3的个数。我想到了xor,但是没想太深,暴力也没打xor,直接把俩数转成二进制再一一比较,效率连30%的数据都过不了。看T3T3又是字符串求把一个字符串转化为目标串的最少操作次数,操作只能将一个字符放到前面的另一个字符前面,就是不能放在这个字符后面。题目最后一句是说有多组数据解,只输出一个解即可,就是说有SPJ,于是我傻逼傻逼地想到了拓扑排序,打了一下发现不对啊,但是只过了两个样例就不管了。T4很长很长,时间不够了,等我理解完题意估计也没时间了,所以我赶紧检查了一下文件名,结束。

讲题。T1BFS,同学告诉我SPFA的边会建的太多,会MLE,于是我发现数组开小了,估计只能30了。T2是将64位二进制分割成4段或8段,然后随机化乱搞。T3 DP乱搞。T4是在一颗点分树上乱搞+强制在线+线段树+具体我也没怎么听...

拿到成绩,10+0+0+0=10,于是又复评,T1竟然第2个点就炸了,莫名WA数组开大之后也一样。T2的话,第0个点是出题人自己手造的,还是WA一堆。

再总结一下,T1再考场上没算空间效率,没考虑SPFA的边很多,极端数据的空间应该开到200*200*200*200*10*4=64,000,000,000,肯定爆。T2没想到暴力可以直接打xor然后判断1的个数。T3没过样例肯定不行。

总的来说,这次还是没有考出真正的水平,两次GDOI都炸了,希望下一次能考出更好。


 

一些题外话——我入了日常坑

Day 0

从汕头到常平才能到东莞,感觉比较远,转了一次车,不过到酒店之后,我就狂背模板,背到被同舍神犇嘲笑,11点多才睡。

Day 1

考完后又被同行神犇嘲笑没算准效率,发现昨天背的东西都没用上,只能坐以待毙。下午发成绩的时候,整个人都不好了。晚上又背了一点模板,想着还是不甘放弃。

Day 2

下午发成绩的时候更不好了,复评的时候还不知道自己到底哪里错了。于是晚上和同学们一起“开心的玩”。

Day 3

去了一个水电厂,以燃烧垃圾产生的水去净化,可以达到饮用水标准,也可以循环利用美化环境、发电,感觉对语文的写作和物理都有帮助啊。然后去了一下湿地生态园,没啥,就走了一圈,回食堂吃了饭然后回了酒店,下午还去了东莞的一家电脑城买了一张手机储存卡,还算便宜,然后去逛了一下超市,买了几瓶水,一天又完了。

Day 4

闭幕式,看了同行各位神犇拿了铜牌,暗自神伤。回汕头到晚上7点钟。

行程结束。

GDOI_2017 爆零记