ICPC 2018 EC-Final游记


强行续了一场比赛,打乱了我寒假前的复习、自学的计划2333

day -x

感觉EC的机会还是挺难得的,于是VP了两年的EC,都是银……VP以外我主要就是改题补题,然后那段时间被一些事缠身,再加上成天写题,越来越自闭,不过好在在出发前一天缓过神来了,算是比较积极开朗地踏上了西安之旅。
话说回来,一开始本来和SR是打算考完四级再去的,因而没有和大家一起买机票。但是,考虑到四级可以再考,免费的西安旅游机会可并不多,就毅然决然地翘掉了四级。
我一直向往西安碑林,许多小时候练过的原碑陈列在那里。因此,我打算周五下午去了之后直奔碑林朝圣。
结合我和SR的旅游路线规划,发现飞机其实不如高铁舒适。高铁到西安北站,直接二号线可以到我心心念念的碑林,但是坐飞机的话,虽然路上时间短,但是需要坐公交从市郊的咸阳机场到市里,最后可能到碑林的时间比坐高铁还长。于是我们买了高铁票。
但是,在某y姓人士的极力劝说下,我最终承受不了,撺掇SR改成了机票。

day -1

叫的10座商务车,司机貌似非常晕,费了好大的劲才找到了学校。去机场的路上,还走错调头数次。惴惴不安之中我们好歹是顺利到了机场。然而司机把我们带到了地下车库让我们下车,又走了一段才到了航站楼门口……
飞达咸阳机场以后,我们坐的机场大巴又在路上堵得走不动,等到了小寨已经接近四点了。
到宾馆办好入住之后,一个人出发了。

第一个让我激动的是颜体的地铁站牌。进站之后,发现地铁站的石柱上居然刻着一些仿古的图样。在永宁门站下车,在去碑林的路上还看到了绵延的古城墙。不过粗略一看应该是最近刚刚修缮过,看起来挺新的…
路上还经过了一个类似于文玩街的地方……强行克制住买毛笔的冲动……

然后就到了碑林

这里人很少,正合我意。
第一个展厅里面放了一些四书五经的碑刻毫无吸引力。
第二个展厅里面有多宝塔、玄秘塔和怀仁圣教序。我一直特别喜欢多宝塔的一板一眼的结构和比较劲道硬朗的笔画,小学的时候也尝试练过一段时间,但当时手上功夫太弱并不能出什么效果。不过,虽然我对多宝塔碑较为熟悉,看到原碑还是对我产生了很大的震撼,感觉与刻碑的匠人和书写的书法家的距离一下子拉近了💗刚刚看到矗立着的多宝塔碑时,我不由得兴奋地跳了起来
第三个展厅里有我最想看的勤礼碑。从六岁到十岁,这里面这些字被我临摹了至少四年。站在这块碑前,像是面对着一位熟知已久却未曾谋面的老朋友,回忆如潮水一般涌来。看完了剩下的熟悉的曹全碑、瘦金体、各种墓志之后,我又回到了这块碑前,站到脚被冻得发僵。

在怀着对北京的向往来到了北京之后,在同学的启发下,才发现北京其实并不一定是唯一的选择。选择一个城市并不只是选择工作,也是选择城市的气质、环境、宜居程度。我还是到过的城市太少了……我觉得,西安,就会是一个我愿意常来的地方。

离开碑林,在那条文玩街上买了一份赵孟頫心经的拓片。虽然号称是拓片,墨香很浓、字也是凹进去的,但我觉得这些碑应该不会让人随便去拓吧。

街边随便吃了个肉夹馍,然后想去找家SONY体验店去试一试wh-h800。地图上找了家最近的,进商场之后找了很久,倒是有BOSE和B&O,就是没找到SONY。无奈之下问了一下服务台,得知这里只有SONY电视没有耳机。再见。

感觉就吃一顿很不值,就问了一下在XJTU的江志东有什么好吃的地方,然后他邀请我去找他请我吃。于是,费尽周折找到了站台,又在晚高峰的公交车上挤到变形,终于到了又一个圣地——原JTU。
不过XJTU里面好像没有很多可以膜的地方,而且校园也并不怎么大(当然比小破邮大不少)。江志东请我吃了顿灌汤包,还让我尝到了西安的特色果啤,还让我试了试他的我心心念念已久的dpt-rp1——不过讲真,书写的延迟真是挺大的。还学习到了南苑机场是中国的第一个机场,而且明年就要停运了,北京城里没有飞机场了……

day 0

早晨在KFC吃了一顿,感觉不饱,就又去dicos吃了个汉堡。去nwpu的长安校区实在很远,我们坐地铁到了终点站,又在校车上颠簸了挺久,才到了坐落在秦岭脚下,麦田中央的nwpu。
报到的时候发现每个人都有书包,而且比赛的服装比较好看。而且报道的时候还给每个队伍录了一小段视频,像World Final那样。我和SR一起把PY的刘海捋了起来露出了他充满智慧的脑门😄。期待着视频放出来。
报道完之后,碰上俩采访的,杨老师让一队和我们去接受采访。在采访过程中,PY口出狂言:如果我们三个都超常发挥,我们是有实力夺金的!站在一边的我听得鏼鏼发抖。
食堂实在是弄得不大好。只开了两个窗口,只能打几个普通的小菜,还做的并不好吃,和桂电食堂有一拼。看着本校那些人吃着各种好吃的,感觉非常不爽。

在开幕式上碰到了Menci和牛神,得知RUC CS的男女比例3:7,和北航全校的男女比例正好互为倒数233333
试机赛总体打的很迷,我个人很不在状态。感觉很虚。
ECNU的One,Two,Three,AK队坐的离我们很近,发现那支队里居然有个可爱的小姐姐,而且还很野,他们背后的大连理工队伍没来,她就上去敲他们的电脑!

晚饭是杨老师在nwpu的一个朋友推荐的饭店吃的,吃到了久违的凉皮,感觉非常怀念。吃饭的时候月加聊了来年的训练计划,聊了他们当年因为出题太忙耽误训练的一些教训……吃的过程中对面桌上不停传来y哥洪亮的声音,他还时不时跑到我们这桌要和我们唠嗑23333

晚上在温泉酒店,有一个叫PingCAP的公司是比赛的赞助商,在酒店做抽奖活动,而PingCAP的创始人之一是bupt的学长。他对我们很热情,送给我们一人一个纪念U盘,我们也就一直在楼下给他们捧场。在抽奖结束之后,还给了我们一些多余的奖品,看他们的文案貌似工作环境挺不错的!

day 1(终于写到day1了)

问了ST_Saint和fqk,都表示丝毫不慌。我怎么就这么慌呢!!!!

开场南大4分钟过了D,还没反应过来,一堆队伍疯狂过D。我拿过D来一看,感觉好像就是分n,m大小关系输出就行了,然后读入的n+m个数字无关???白读入这种操作我还真是没怎么见过,所以有点怂,就让SR去写。写完之后还是怂,但是SR一拍大腿,说:这么多队都过了,交吧!然后就过了。
接着发现L有一堆队伍过了,看了看题分析了一下,SR感觉差不多就去写了。我不大懂他的具体想法,于是在一边又推了一遍具体做法以防万一。此时根据试机赛的气球颜色提示盯上了G,和PY一起研究G。结果SR写了一会儿L发现不行,我就上去把我的做法写完过掉了。
写完L之后得知F是个计算几何,讨论了一下发现应该就两条切线+一段弧长,SR提供了三维转二维的思路,于是接着上手写了。写完之后交了一发WA了,发现把一个sqr写成了sqrt……改掉之后,三个人又一起手出了几组数据,交上去A了。
接着榜上显示最可做的题目是I,而SR和PY都已经自闭好久了……这破玩意想最短路建不出图,想DP有后效性,三人一起自闭的很欢畅。看着一支支队伍暴过I题,我开始突发奇想,出了一个贪心,PY把我的贪心否了,又结合我的思路又出了一个贪心,也被我否了,我又结合这个思路出了一个贪心,三个贪心写完之后取max可以过样例。然后,按照SR的理论,小范围数据可以精心手造,于是小范围判了个DFS+剪枝。然后心怀梦想地交了一发,刷出来CORRECT的一刻我们三个不由得大声喊*
过掉I之后是rank 70+,本来以为得再过一题才能保住银,然而当继续多线程自闭了一个小时之后,封榜前排名是75。
封榜之后绝望中开始读大模拟H题。读完之后写了二十分钟发现太麻烦了根本写不动。。剩下半个多小时PY打表找规律,我和SR搞C,但根本没什么戏了——封榜前自闭一个小时都不会怎么可能半个小时想出来写完。结束之前写了个乱搞随便交了几发,本赛季最后一场比赛就这么结束了。

总结

三个银结束大学的第一个赛季,也还可以吧。
因为水平没那么强,一直怕打铜,最终还是成功凭借RP苟过了三场比赛。除了ccpc桂林的银比较稳之外,沈阳精准卡线,EC贪心过题,都有很大的运气成分吧。
一队今年没出线,心里也是挺压抑的。也许可以指望下个赛季能出现大腿?毕竟RJJ的WF红利马上就要到期了,如果明年还是进不了WF,以后的ICPC名额可能就比较尴尬了。
过年以后,该好好训练还是要好好训练,下个赛季奔着金牌去吧。
开始准备期末考试了……可能考前就不再研究竞赛了

CCPC2018桂林站游记


选桂林是为了旅游,总体来说,除了没去阳朔有点遗憾以外,旅游得挺不错,而至于比赛嘛,emmmmmm

day -1

沈阳站回来以后一直在咸鱼,不知不觉就混到了周五,该走了。
坐着阿訇叫的七座商务很顺利地到了机场。而在过安检的时候,SR的登机牌名字打的重叠了,折腾了一会才过了安检。
过了安检之后,SR帮我用京东支付买了一瓶饮料,结果他想起来他并没有在京东支付上绑定银行卡,结果仔细一看,原来上一个用他的手机号的人用这个号注册了jd,然后又绑定了银行卡,又开通了短信验证码支付,于是乎SR就可以不费吹灰之力地随便刷。这个号码的上一个主人还真是大意……而且在他的京东账号里并没有手机号等联系方式,只有收货地址。打算写封信告知一下2333

飞机餐不大好吃……不过也没抱多大期望。飞机落地之后,一个中年男子来问我们是不是参加程序设计竞赛的,我们很惊奇……然后他热情地自我介绍,并且给我们每人发了一张名片,原来他是机械工业出版社的编辑人员。想起我们书包里一本本厚厚的黑色的书,瞬间产生了很亲切的感觉~
穿着毛衣上的飞机,一下飞机,立马热成狗。从北飞到南就像穿越了时间……到酒店换上夏装之后,我们就出去玩啦~

我们住的地方离象山很近,SR和阿嘤队打车去,我和PY骑车去。街头充满着桂花香,还真是很久没有闻到过了。好感++
象山景区挺小的,登山的台阶很陡峭,但是山并不高。在象山最高点有个观景台,而从观景台望下去,视野里充满了煞风景的小房子。不过这也不是个专门的旅游度假区,也是没办法的吧……
在象山的观景台可以看到东边的群山,和我印象中北方的远山的轮廓大不相同。那些山都是奇形怪状,出来的轮廓也是充满了导数剧烈变化的点。盯着远山看了一会,就下山了。

出了景区之后,我们去追随阿嘤队吃吃吃。他们先去吃了一家米粉,然后去了一家烧鹅店。我们就也去了一家米粉店,尝了尝传说中的桂林米粉,真的挺好吃。米粉口感很嫩,配的那些小菜,酸豆角之类的也符合我的口味,很不错。在桂林前前后后我大概吃了七八碗米粉吧……
然后烧鹅店。烧鹅也挺好,皮很酥脆,但是肉质比北京烤鸭嫩很多。不过我最后还是没尝出来啤酒鱼有什么啤酒味……整体来说,吃吃吃的方面,比沈阳站全程M记好多了。

吃完之后,又去了日月双塔公园,登上去看了看;然后去了个步行街,什么都没消费……回到了宾馆。

day 0

七点半起,想等人一起吃饭,饿着肚子等了一个小时才和阿訇、PY去吃早饭。

快到中午的时候,我们去了桂电。
桂电的校名应该是中石题写的。学校挺旧挺小,和小破邮本部挺像的。而食堂的饭实在是说不上好吃,于是我们把剩下的饭票全都换成了果汁。15元的饭票,换2.5元的果汁,食堂的这笔帐真是爆赚。
在食堂遇到了南老师、汪神、晨神和可爱的佳蔚哥哥姐姐。没选上南京站真是挺遗憾的,如果能去南京站的话就能遇见Menci、牛神、恒妹了。

直接翘掉了开幕式,去了比赛现场。硬件一切正常,然而我们对面坐着一支pku队,背后一支hust队,蒟蒻瑟瑟发抖。
试机赛的提米比较奇怪,沈阳站放了三道签到题,而这场放了一道签到,一道挺难的期望,一道挺难写的模拟,一道挺奇怪的猜结论乱搞题。一开始读错了期望题,和SR自闭了一会,发现样例都过不了,于是扔掉之后分头开搞。乱搞题由SR带病做,猜了个奇怪的结论交上就过了。签到题我粘了最大流模板过了。此时还有半个小时结束,貌似唯一可过的就是写简单的python解释器那道模拟题。
我写完了表达式求值以外的部分,发现不会表达式求值。PY也只有模糊的一点印象…被一道初学栈的标准例题卡住,真是丢人呢……

试机赛结束,SR、yjz和gzz、Yousiki出去愉快地玩耍,PY和jiangshibiao等一众绍一同学出去愉快地玩耍,扔下弱省弱校的我孓然一身……在学校里逗留一会,发现我打不上车,只好提着换出来的一袋子果汁、背着词典走回了宾馆……桂花香真好闻++

晚上想再看看表达式求值,竟看不懂。想想第二天也不可能考,就大胆地扔下不管了。

day 1

早晨还是很凉快的。
开场秒了G,想抢一血,写完直接交,结果WA了。改了几个地方交了几次还是不行,就把电脑让给SR写D,然后和PY对着代码自闭。SR的D过掉之后,我又改了下还是WA。最后SR想了想指出了我的想法的问题:应该枚举差分数组gcd的所有质因子,然后依次看看调整到各个质因子的整数倍需要多少次操作。改完之后总算过了。签到题-4,好大一口锅……
然后就跟榜写H、J。H的想法比较简单,我和SR大体统一一下他就去写了,结果过不掉。此时我和PY对着J自闭,我猜了个结论,然后他接着猜了个结论,感觉靠谱,他就去写了,过掉了。
H题本来的写法比复杂,讨论的情况较多。我灵机一动,发现可以直接从’a’无脑枚举到’z’依次判断也并不会超时,写一发,代码也很短,直接就过了。后来得知阿嘤队这道题代码接近100行……
H过掉之后一起对着A自闭。。。感觉A过的人挺多的,但是不知道自闭了多久,也没有进展……此时有人过了L,发现是个计算几何讨论题。SR大力讨论了一发,然后让我去写了。我写的同时他们对着C自闭。
这个计算几何并不涉及什么特别的算法,就是简单的一些操作组合组合,不过写完之后还是挺长的。然而WA了一发,于是把电脑让给SR让他写C。
SR对C的推进也不怎么顺利,我对着代码找了一会错误之后,改了点东西,还是过不了。我又着重考虑了边界情况,抽出来几种单独判掉,终于A了。此时已经封榜,离结束还有大约50min。
SR继续搞C,我也和他们一起看题意,听听做法感觉还挺靠谱的,但是写完之后就是过不了。我们三个一起想办法X掉这个做法,叉叉改改,改了又叉,而最后想到的改法需要线段树,已经没时间写了。于是随机胡交了十几发,比赛结束了。

感觉这次应该比较稳,但是还是心里有点虚。最后结果一出,我们rk31,如果罚时少点就能Au了……

总结

这场发挥的还可以吧,这个排名感觉也比较符合场上的状态。现在主要的问题就是中后期的推进,这还需要好好训练,提升水平,才可能过掉难题,过掉金牌题。


ICPC2018沈阳站游记

只能选两站,怀着去旅游的心理选了桂林,然后无脑跟阿嘤队选了沈阳。当时没发现两站是连着的……

day -x

闲下来的时候就是准备模板,重学了一些好东西,但是没做多少题。感觉脑袋变得不太灵光了。
队伍集体训练几乎没有,唯一一次是vp了2017沈阳站,结果我clone的比赛是从uva上拉的,没数据,一交就过……花五个小时打了场假比赛。

day 0

高铁八点发车,得五点半从村里出发。我们早早下去,在甲子钟冻得瑟瑟发抖。
结果褚大哥睡过了??
结果阿嘤他们楼的宿管大妈失踪了??
奔跑的阿嘤队↓

走到沙河站,腿都冻麻了。。

换了换座位和阿嘤队坐一起,大约十二点到的沈阳,一路扯扯皮很快就过去了。
出站之后打车去酒店,在沈阳打车好便宜!!
在某家M记吃午饭,一位店员大妈对我们说:麦当劳就愿意招你们东北大学的学生,因为你们素质很高!我们没敢承认我们其实是素质低的北邮学生O_O
发的参赛服在淘宝上可以搜到

感觉太蠢于是就无视规定没穿,结果就是我们只得在观众席上观看开幕式……快结束了才把我们放进去打热身赛。
热身赛三道题,一人切一题,很快写完了。每个人都写了一会儿代码,适应一下键盘,总体感觉海星。
热身赛前刚刚发的饭票,打完之后就被SR弄丢了。找了好几个志愿者,最终终于又要到了一份。中间遇到了一个志愿者,给我们留下了很大的心理阴影。
“你们哪个学校的?”
“北邮的。”
“北邮儿的?”(表情突变)
“大几的?”
“大一的。”
“北邮曾经给了我很大的伤痛。”
“那有个你们大二的学姐。”
本以为他和北邮怎么苦大仇深,听到这的我一脸黑线==

学校准备的自助还是很好吃哒哒哒~

本来立下flag,此生不碰2-sat。结果没有2-sat板子,不得已又看了一眼。结果发现我在考场上离正解只差三行代码,顿时感觉十分难受。

睡不好

day 1

睡不好

将头发梳成大人模样,穿上一身帅气夕阳红老年装。
M记里基本全都是ACMer。

九点钟,比赛开始了。
题面都很长,我找了一道题面看起来最短的C题开始读题,题意还是比较好理解的,就是将前k个数字冒泡排序之后序列的LCS\ge n-11…n的排列个数。我一开始考虑按照排序之后不在LCS里面的那个元素的大小与k的关系和位置是否在前k个分类,每种分类写出一个式子来算一算发现不对。后来发现四种情况中有两种情况会出现重叠,想了想发现没什么办法,就扔给SR跑路了。
与此同时,PY跟榜切掉了签到题,因为把==写成=查了很长时间(初学者*1)

SR拿着我的式子改,我写暴力让他找规律,最后找到了规律,开始写。写完之后WA了。原因是没加Cases#。加上之后WA*2,原因是n==k的情况是特判输出的,那里每加Cases。改完之后WA*3,我又看了看题目发现k可能>n,于是把特判的条件改了改,终于过了(初学者*2)。

当时我们rk30左右,寻找下一个突破口。
SR之前看的n\le 10^{18}的约瑟夫问题,满足\sum\min(步长,步数)\le 10^6,我和PY拿过来,翻开白书和具体数学,结合经典问题的递推思路开始想,但并没有什么结果。
PY又读了一道维护平面内满足到某个点欧式距离为给定值的整点的题目,貌似暴力可搞,我打个表发现所有完全平方数至多有一组平方和的划分方法,于是就写。写完之后TLE。原因是1000组数据每次memset大数组(初学者*3)。改成时间戳之后WA,发现时间戳写错了(初学者*4)。改完之后还是WA,发现打表的时候内层循环把i++写成j++,出来了错误的结论(初学者*5)。不过好在改过来之后所有数字总的划分数不多,于是就改成用vector存每个数字的两个平方数的划分方案。终于过了。
此时又从rk80+回到了rk30+,但是由于罚时爆炸,三题垫底。此时还有不到两个小时。

封榜前没再写题,第一次感受到离开手机查词之后的无助。词汇量太小,而翻词典翻的太慢,被各种卡题意。最后掉到了rk45,感觉这个罚时,很虚。

封榜后全队一起约瑟夫希望保住一块Ag,SR想出了一种挺靠谱的方法,是一种细节多的让人lao kuo teng的方法,按照我的理解,在50min内写完并且A掉是比较难的。但是孤注一掷,就让SR写吧。我和PY在一边双排自闭。在一旁看题,也没有想出哪道题有什么好写的方法。到最后SR写不完了,我们三个在悲伤中自闭完了剩下的十分钟。

比赛结束之后,我们不想看滚榜,打算直接去找家火锅店狂吃一通发泄一下。看着封榜后后面队伍的交题记录,我已经做好打铁的准备了…然而还没找到火锅店,fqk告诉我们卡线Ag了…

月加队打的很自闭,和我们一起卡线Ag了…

阿嘤队封榜之后也没过题,最后还是一个Ag…

总结

说实话,这块Ag真是给我一种白捞的感觉。。打成这样,各种初学者的低级错误。。只能感谢各位轻虐了…
和外校交流发现我们队训练少的可怜,像中大南大,并不能签到NOI比较靠前的选手,但是上大学以后刻苦训练最后能和清北叫板。等桂林打完,这个慌忙的赛季结束,该好好想想以后的路怎么走了。