记铜尾acmer的省赛之旅

本文最后更新于:2021年6月13日 中午

在我所在的学校是一个ACM弱校(目前是的),没有ACM集训队,自然也就没有专门的实验室以供训练,甚至难以找到两个愿意持续花精力搞算法的同学,想打ACM只能用爱发电。

而我自己也不是一个那么积极上进的人,上课靠水,考试抱佛脚。在没有队友老师监督的情况下,也就只是隔三岔五的做做题而已。

本文单纯记录一下这次的经历,如果有不妥当的措辞请联系本菜狗。

如何评价 2021 年第十三届四川省 ACM-ICPC 大学生程序设计竞赛?

cf_gym补题链接

1. 校内选拔

按照惯例,蓝桥杯初赛的举办在acm之前。

由于这学期负责相关竞赛的老师(ccls)事情有些多,所以直接就把蓝桥杯校内选拔赛(第十二届蓝桥杯大赛模拟赛(第三期))当作了acm校内选拔赛。(按照蓝桥杯的排名来选择参加acm的同学,然后在这些同学中组队)

likeqc同学有写过这个模拟赛的题解,就不重复写了。

吐槽一下有些同学校内选拔成绩和初赛成绩相比也太不稳定了趴

2. 组队

队友1:舒化奶(大学期间最最好的朋友之一,老早就确定的队友,下图被ccls称为小鹏)

队友2:jxx(ccls推荐队友,舒化奶前女友,下图李XX)

两个卷王,综合排名年级第一第二那种。

image-20210606131018861

被学校指定了队友,到这里其实ccls还不知到我的两个队友是前男女朋友,然后有了下面的对话。

image-20210606131036673

编程就好好编程成了我们队后来常说的一句话

3. 分工

image-20210606211327536

在我们完成组队的时候,ccls说我们是全村的希望(感动),原本觉得打差了只是自己难过而已,这样一来还多了一层对不起老师期望了(压力倍增),而且这个时候已经距离比赛只有一个月了(省赛5.30)。

顶着压力,赶紧分工,抱抱佛脚,经过一番讨论(并没有讨论,直接就确定了😂),简单确定了如下分工。

  • 舒化奶:数论、计算几何
  • jxx:DP、贪心
  • 特仑苏:搜索、图论

这个时候还得知川大的校赛在5.21举办,还会开放外校的同学游玩,所以决定各自学20天,然后在川大校赛上训练。(感谢川大,感谢丁丁妹)

4. 训练

4.1 第一场—Sichuan University Programming Contest 2021 Preliminary

一晃眼20天就过去了,时间来到了5.21,比赛时间是从12:00到17:00,本着反正写完会写的题用不了5个小时的想法(菜狗只能做个签到题的样子),我们决定先睡个午觉13:00再开始😂。由于没有实验室可用(有实验室也没空调,火焰山大学没空调可顶不住坐5小时),所以就在学校里找了个奶茶店打。

我们三个之前有过一次数学建模的组队经历,互相还算了解,但是没有一起打过acm,所以上来就开了三线程,自己做自己负责的题目先试试看。

我进入oj的时候已经有很多队过题了,跟榜很快过了签到题,然后开了一个BFS板子题,这个时候舒化奶开了一个最小公倍数的题,jxx开了解方程的题。

从这个时候开始,我们的问题就开始逐渐暴露了。舒化奶的问题是思路没毛病,但是代码实现会被一点小细节卡住,而且难以debug那种。jxx负责的dp和贪心并没有准备好,所以就能做啥就开啥了,但是她做题的思维是深搜,也就是把一个思路想到底,不撞墙不回头那种(甚至撞了墙也不回头)。这个时候他们两个还有情感隔阂,没办法交流的那种。所以我就一哈帮舒化奶debug,一哈听jxx讲思路,就这样持续了两个多小时,板子题我都还没写完,期间jxx居然还写了个巨复杂的1e9复杂度的代码还交了,debug都看了我好几分钟,无语自闭。冷静下来想了一想,发现我没有时间自己写题,所以决定先不看队友的题,把手上的板子题过了再说(早就该过了)。果然静下来马上就过了。

到这个时候离结束已经只差一个小时了,舒化奶的最小公倍数已经wa了五六次了,一开始交了1e16范围能过的代码没过,而且题目没有给出数据范围,我们就以为是需要用高精度来写的,所以让舒化奶抄高精度板子,然后我和jxx推方程。

离结束最后半小时,舒化奶又wa了两次,找不到办法直接放弃了,jxx这个题推出了一个线性方程组,直接上了高斯消元板子,但是直到结束也没有调出来正确答案,就这样以两题结束了第一次模拟。

结束之后我又看了看舒化奶的最小公倍数的题,抄板子就完了,感觉应该不会有问题才对,然后自己写了个交了,ac,一对比发现舒化奶输出答案没换行。

赛后总结:

  • 我应该不管其他事先把能过的题先过了再说
  • 舒化奶需要注意细节
  • jxx写代码前应当先计算复杂度
  • debug耗时多,第二场12:00开始

4.2 第二场—Sichuan University Programming Contest 2021 Final(team)

第二天我们开始已经是12:30了,照样跟榜快速过了个递推序列的前缀和题。

然后就记不清了😂😂😂,反正比第一场更自闭了,发现我大部分时间都在为队友的代码debug,于是商量后定下我写代码,他们两个翻译题目以及提出思路的战略。

4.3 第三场—2019四川省赛模拟 - Virtual Judge (vjudge.net)

第三场模拟,向ccls申请和学校里选拔出的其他几个队一起模拟一下历年比赛,本来准备模拟2020的,但是死活没找到哪个oj有题,最后用了2019。

19的题是做过一次的,但是当时太菜,很多题都没读懂,基本上可以说是全忘了,拿来模拟也是可以的。

众所周知19四川省赛是阅读理解专场,开场我一个英语渣直接愣住,没几个是看得懂的,所以开场一直在看榜,翻译直接交给两个英语学霸队友。

直到20多分钟后,看榜找到了签到题是B题,舒化奶很快翻译完给出了题意,简单写了一发暴力枚举每个方向的多边形就交了,结果wa了两发才过,两罚都是粗心小错误,而且这个时候发现另一个队伍wa了一发就过了,排名在我们前面,心态有点慌张了。

调整了下心态,jxx翻译完H题给出题意,想了一下感觉是个贪心,把时间排个序就能过。然后写完给舒化奶和jxx看了看感觉没问题就交了,结果又得了个wa。又看了看代码,确实没找到问题,感觉可能jxx给的题意有问题,这阅读理解题目我也看不太懂啊,泪目,然后复制到有道直接翻译了(道歉),发现jxx的翻译确实有漏洞,还是可以贪心,但是需要排序时间和次数两个序列,加了一行sort又交了,ac。这个时候时间才过1小时多一点点,按照19省赛的排名算的话,这个速度的两题队已经有个铜了,哈哈哈哈,心态一下就舒服了。

然后舒化奶又给出了A的题意,A是模拟自走棋,刚出的时候还沉迷了不短时间,第一版代码写了个unordered_map<pair<string, int>, vecotr<int> >这样的结构来通过{名字:等级}映射所在棋盘上的位置,然后发现pair不能放在unordered_map的key位置,然后第二版代码写了个二维的哈希+vector来映射unordered_map<string, unordered_map<int, vector<int> > > ,交了两发,得了两个wa,实在是找不到错误,持续到比赛结束。期间还开了个博弈,但是我当时还不怎么会博弈,舒化奶也还没看到博弈,推不出结论,只能作罢。

第二天又把这个代码拿出来看了看,发现输出的答案序列每一个后面都有空格,然后把最后一个后面的空格去掉又交了一次,ac,woc,过分,这也卡。。。。

自以为应该是能过3题的😂,而19年3题队有个银了,所以打出了”保铜争银“的口号。

jxx总结了我们这三场比赛出现的问题,机场路幼儿园一队避坑指南,准备后面按照这个指南避坑。

5. 热身赛

热身赛前一天在火车上睡了不少时间,再加上当时遇到个因为自己傻逼造成的烦心事,本来就不太困,结果越想越睡不着,又搞了个傻逼操作(捂脸.jpg),然后直接就通宵了。

早上5点多还没睡着,不想继续躺着就起床了,想着再看看线段树,结果也一点没看进去😭😭😭。ccls安排我们下午13:30去民大报到,就一上午都在酒店无所事事,也没有困意。

下午报道发现是有发放午餐券的,没机会用了血亏。

报完到没多久就开始热身赛了,我们那个机房是远程主机,键鼠都有一些延迟,着实有点不爽,还有题目只发了一份。

A、B题都挺简单的,很快就过了,C很快也找到了思路,写了一发直交,得了个wa,找不到原因就开了D,算了算复杂度感觉暴力枚举就行,写了发dfs交了,又得了个wa,然后就是将近一个小时的debug,最后也没找到问题。

结束之后问了问前面的ZJUT7队C思路,发现是漏了个特殊情况,可惜。

然后看了看D,又发现D可以用next_permutation写,可能会好调试一点?

打完就去民大食堂干饭了,由于jxx不去食堂吃,所以我们多了一张餐券,用这张多的餐券整了25的西瓜😂,另外餐券值25,餐盘饭怕是最多值十二三块,有点亏。

吃完晚饭在民大逛了一圈,统一的建筑风格真好看,还有没见过这么大只的鲤鱼。

回酒店趴床上继续打acwing周赛,结果就做了一个题,然后贼困就睡着了,醒来已经22点。点了个外卖吃完继续睡,就又睡不着了,泪目,睡着大概又是两三点了。

6. 正式赛

早上6点多起床,贼困,状态很差。

在酒店吃了个早饭就去民大了,正式赛给换了个没啥键鼠延迟的教室(好评)。

坐在位置上之后贼紧张,作为全村的希望,而且不知道下一次还会不会参加,说不定这次就是退役赛了,慌的一批。

开始之后我就开始打常用,同时把代码框架写出来复制A~M个,我才复制到D题,这个时候舒化奶给出了A的题意,貌似很简单,我就写了一发,直接就交了,果得了个wa,我还有点懵逼,心想这怎么会wa呢?然后舒化奶指出交到了D题上,我什么都没想,又一波操作,submit->select problem->A,又交了,然后得了个out empty。打开dev一看,A写在了D里面(因为我刚刚在复制D的框架,然后就把A直接写在了D上,然后交题自动识别D.cpp到D题上我也没注意,第二次直接忘了写在了D里面,又交了A,A只有框架),然后冷静了一下交了一发ac。整个过程完全没有想起来我们还有一个“避坑指南”,可见状态之差。

这个时候心态已经崩了,本来写的挺快排名在同题目数里面应该还比较靠前,结果因为我状态问题wa了两发(给队友道歉),ac了A之后冷静两一两分钟,稳定了一下情绪。

很快舒化奶又跟榜给出了K的题意,想了个贪心的思路,一把ac,心态稍微好了一点点。

然后jxx给出了本场唯一一个阅读理解题H的题意,题目很长,但是写起来还蛮简单的,wa了一发,很快发现了坑点,第二发过了。这个时候大概距离开始两个多小时。

紧接着舒化奶就给出了唯一一个博弈的题意(出题组说是披着博弈外衣的思维题),想了一下,猜了个结论讲给舒化奶听,好像没什么问题,然后写完就交了,有一个wa,很快就发现是没用long long导致的,改了就ac。泪目,尽是这种问题。

这个时候距离结束还有两个小时,jxx给出了M的题意,很快有了思路,但是计算复杂度发现大于了1e8,不敢写(后来发现题意又给错了)。

然后舒化奶给出了最短路题目的题意,一眼看出是多源汇最短路问题,想着用Floyd写,但是板子居然带错了,我的锅,抱歉抱歉😭😭😭。然后也没注意看数据范围,源点只有100个,多源汇BFS就可以过的题,最后没写。

随后舒化奶给出了A的题意,还快找到了结论,有一个映射不太好写,两个小时硬写了两三版代码,没debug过。

比赛结束工作人员让每队派两个同学去礼堂颁奖,我们算了算排名,封榜前就是铜尾了,一度不想去礼堂。

想着去看看其他大佬的风采还是去了颁奖典礼,没想到还能有个铜,大家都是没打破封榜不过题定律啊。

image-20210613115630739

现在想来A、M、最短路着实可惜,状态正常的话应该是能过两个的,虽然6题还是铜。

感谢两位队友在紧张复习考研期间陪我打一次acm。由于不好的状态给队友带来了不佳的竞赛体验,抱歉抱歉。

最后就是回想起一开始的目标”保铜争银“最后变成”保铁争铜“有点难受。

image-20210613000652662


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!