ICPC2017青岛站记录

第一场ICPC比赛,就遇到这样的题目,真的很难受。。

出发

11月3号中午12点,我们再次离开地大,坐上了前往北京南站的出租车。不同于上次的大文豪,这次的司机显得正常了许多,车窗外是北京还算晴朗的天空,不论怎么说,这次去青岛,大家还是抱着一颗想拿银牌的心去的,而这也隐隐约约在每个人的心头蒙上了一层不算厚的阴影。

第一次坐动车,感觉很开心,看了一会BBC的Blue Planet,想了想自己这几天做的题,然后就美滋滋的和三星看完了秒速五厘米,看完之后本来好点的心情变得很不好,还好之后复习了一会线段树,头脑体操练习了一道线段树的经典题目。

抵达

到达青岛,瞬间一扫所有的不快,虽然时间已至七八点钟,但我们依旧能够感到清爽的空气和声音,大海的声音。撒着欢地跑向一片漆黑的海边,开开心心的照相之后,我们乘上了前往中国石油大学的隧道公交。

原本看到隧道公交的图,我以为穿过大海的隧道周围是透明的,可以看到在海里游动的鱼,然而事情并不简单,他和穿过大山的隧道并没有什么区别,略失望,不过我们下榻的地方可以说是很不错了,非常舒适。

简单收拾一下之后,我们找到一家疙瘩汤的店。谁能想到,这竟然是我这辈子吃得第二贵的一顿饭,达到了惊人的人均一百二十元,想想肚子里的墨鱼饺子,疙瘩汤,炖鱼还有青岛一厂的啤酒,拍拍肚皮,心疼是肯定的,但吃得确实是很不错,味道很好。

回到旅馆,泡澡睡觉,郝进刷了好长时间的剧,在他泡澡的时候,我们两个都睡着了。。

不过,凌晨一点五十,我竟然醒了过来,本来想转身继续睡,但还是忍不住打开了斗鱼,看了将近一个小时的暴雪嘉年华,不得不说今年的新内容还是非常不错的,新的CG也很吸引人。

扯远了,第二天八点半起床,和三星出去找海,郝进去和小姐姐在金沙滩漫步,不得不说青岛确实是个好地方,排了两个多小时的队,顺利签到,下午热身赛,凭手速一举进入金牌区,然后一步一步掉了出来,很皮,晚上回到旅馆,做了会题,洗了个澡,很早就睡了,

正赛

早晨吃过饭之后,我们便很早来到了赛场。很快找到两道签到题,第二题的表达还是有问题,还是要好好锻炼一下。不论怎么说,第一道题做完之后,银牌区,第二题做完就掉到铜牌区了,搜索了一遍有没有其他能做的题,好像只有字符串能做,这道很坑的题必将成为一道我终身难忘的题目。

题意是这样的,给n个字符串,要求取出每个字符串的某个后缀,按顺序连成一个字典序最小的字符串。大多数人的通过方法是n^2加后缀,猜想应该和我们最开始用的方法一样————从后往前,挨个建立后缀数组,然后依次向前贪心,通过修改后缀数组的板子直接得到新加入字符串的最小字典序位置,这样是n^2的复杂度,我们直接T了,不过后来发现可能是我做的板子确实有一些小问题,在概念的地方有一些模糊不清,这直接导致了我们三发re。

抽搐了几个小时之后,三星想到只需要比较2 * L的长度即可确定,然而他没有想到,这样贪心似乎有一定的后效性,我想到从2 * l的位置往后寻找,找到第一个不同的字母补到字符串结尾,但这样的复杂度似乎又很容易被卡住,我直接想到压缩,但三星没有听我的,他想到了更加简洁的方法,敲完交,Accept。

在接下来的半个小时里,确定有铜牌的我们,开心的吃光了发给我们的午饭,并开始计划在群里待会该怎么说。。。

总结

这次ICPC现场赛说到底还是让人很开心的。一方面青岛这个地方确实让人有一种说不出的舒服,不论是空气、大海还是阳光,似乎都在滋养者生活在这片土地上的人们,这里的车是我第一次看到过得主动为行人让路的汽车,这至今让我感到惊叹。到了比赛的部分,题目的劣质让很多人烦恼,也让我们可能是错失银牌,但最终的铜奖也不算有很多的遗憾,赛前立了个不得了的flag————如果拿了银牌就跟家里要一台switch,怕是拿不到了,哈哈。

已经打过了两次现场赛,还好暂时没有拿铁,还有一丝庆幸,十一月底的南宁赛区一定要好好准备了,三周的时间,是我们的优势,也同样是劣势,一定要把握住机会,争取能更进一步吧。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注