现在的位置: 首页 > 综合 > 正文

2014 ACM/ICPC 上海区域赛小记

2018年01月14日 ⁄ 综合 ⁄ 共 1854字 ⁄ 字号 评论关闭

想想时间还是过得很快的,一个星期前的这个时候我真的很害怕,担心又被我弄成西安Regional那样。然后Shanghai Regional的名额还是我死皮赖脸地像coach求来的(大一的小盆友们以后机会还多,我们可是最后一次了BLABLA)所以那一阵子压力很大。><然后两只队友一个在忙出国申请一个是研究生天天泡在Lab里都木有时间刷题,有一次发个WeChat问题两个人都不理我,那一刻真的很想哭。

十一月中旬考完final就开始刷hdu oj,每次看到求逆元的题都很难过,总觉得要是暑假好好刷题西安Regional也许就不打铁了BLABLA,然后我刷题的速度又很慢,经常一题卡一天,感觉好多题就算会写等我写出来调对也都过了五个小时了额=。=于是比赛前hdu过题量还是两位数。。捂脸

热身赛的感觉除了D题其他都不会做,然后D的两个随机数还是Kaiyu GeGe猜出来的(把座位号敲进去@@),A题求多个圆的交集,我只会求两个圆的,于是就束手无策了,B先要求个最小环然后再求出满足一个公式的数,表示只会做前半道题==我的想法是用BFS枚举,debug好久之后Kaiyu GeGe发现标记了经过的边就回不去了,So。。我又犯逗了额。晚上回宾馆翻模板翻到了最小环的代码,就是用Floyd。。。觉得热身赛状态好差啊,不过靠着D最后还挤到了银牌区。><西安那场热身赛还在铜牌区呢,结果TAT

第二天我们一直找签到题,结果等了十几分钟board都没有过题,还以为board出问题了==二十多分钟有队伍过了J,于是我们就去看J,我对这种智商题一看就晕啊,Kaiyu GeGe的想法先让所有人都平手,然后后面的分去补前面的分,写了一发结果WA了,他还让我给他找个测试数据,结果我当时正在开B,给的数据有问题。。。又成了猪队友呜呜呜。。赛后Kaiyu GeGe说就是分各种情况讨论神马,比如胜的得分>负的得分>平的得分,胜的得分>平的得分>负的得分等等,然后还要分奇偶讨论。

B题我看了好久居然没看懂题意,还是贝贝看的题。后来感觉特别像判断点在不在多边形内部的方法,顺时针绕过+1,逆时针绕过-1,然后通过mod 4判断绕了几圈。N*M<=1e6,我就按照N=M=1e3来算复杂度,一个testcase是1e7,结果我开始没看到T=100,直接写了个暴力然后TLE了,赛后Kaiyu GeGe说如果是1e6*1的matrix直接不就到1e10了么。。唉又脑残了,第二次发生了比赛时算错了复杂度==
 B后来我是打算计算格子的每个边顺or逆时针绕过了几次,不过本地就有bug没时间调了,在回来的路上我想了想这种方法还是会T,之后和Kaiyu GeGe讨论了一下觉得是用二维线段树or二维树状数组,不过参加了闭幕式的贝贝说最后的题解里没提到啥数据结构>< 求问哪位ACMer愿意告诉我B咋做啊%>_<%

Kaiyu GeGe在三个小时的时候过了J,然后他开始看I,I之前贝贝在看的时候以为是背包,不过她的想法不管是空间还是时间都会超。Kaiyu GeGe觉得是贪心,然后他问我有没有什么数据结构可以log n插入新的数,我告诉他map可以自动排序,查找是log n的,我就起到了这么点作用,就去继续看B了。Kaiyu GeGe这一题一直在WA,我中途就没管这道题一直在卡B。。。中途我还在想是不是又要打铁了回去会不会被教练PIA飞。。。%>_<% 后来Kaiyu
GeGe的I没有再WA变成TLE了,他说map排序太慢,应该用树状数组,那个时候已经不剩多少时间了,感觉挺没希望的。后来Kaiyu GeGe又改了一发在291min返回了YES。。赛后他说他木有用树状数组,只是做了个手脚(#‵′)

比赛就这么结束了,拍了几张照片就匆匆忙忙赶飞机去了。

感觉自己又逗了五个小时。。。花了那么久的时间刷线段树的题,比赛时碰到了还木有想出来,而且二维线段树我也不会>< 之后看终榜我对Kaiyu GeGe说过了B就是银了,他不屑地说过五题还是金了呢。。。咕~~(╯﹏╰)b 黑的漂亮。。

赛后发现上海的题目被吐槽的挺多的,我只能说自己无比幸运,靠学长单挑过了两题水到了铜牌。。。我又木有起到什么作用呜呜呜,刷了那么久的题最后还在赛场上坑了队友呜呜呜。。。果真还是男生更腻害~~~╮(╯▽╰)╭

之前刷的题就当为我们队攒人品了!

回来之后还开森了好几天,其实挺没出息的。。拿个铜高兴那么久。。目测大粗腿队友都木有感觉了。。Kaiyu GeGe真的好腻害~不愧为学长╮(╯▽╰)╭

哎明年还是想再战一年啊~~~



抱歉!评论已关闭.