2022-ICPC-合肥-参赛小结
本文最后更新于 494 天前,内容如有失效请评论区留言。

[toc]

赛程回顾:

来之前在车上看了下开幕式,十点十几到清水河,下车后也带着耳机听了下开幕式,然后转了一圈感觉食堂应该都没有开门,就去商业街找超市,先去易购买了一个蛋黄派,再在旁边的红旗连锁超市找到了costa咖啡,遂买了,10:50左右到达了考试地点,队友已经到了。等待考试开始,11:15左右开始登录,手机机位调整了好几次,考前20min cyl和syz跑去打印了一下k短路板子,考前又换了个摄像机架,考前1min,收到了反扣在桌子上的考试题目。

拿到题目后,开始快速扫描题目,发现A是签到,前大半部分都是关于中科大和ICPC的介绍,最后一段才是题,读出题意后觉得是签到后就先上机写了,syz和cyl在旁边推答案,推出答案后在9min通过了此题。此后syz在39min过了H,开场还不错

我和cyl都读了B和G,G感觉是什么不会的贪心,B我和cyl一开始都没读懂题意,之后cyl才读出是算x/y的期望,但究竟怎么算一直卡在它x>y后能reset时间不知道该怎么处理,cyl提出可以考虑当前成功的贡献,可能是+x,也可能是+l(l < x),推出了个答案是min(x/(py), 1)的答案,看着比较离谱,果真交上去也WA了。cyl又对G提出了个“反悔贪心”,和我们讲了后,我懵懵懂懂,syz理清了思路开始实现,实现细节也卡了一会,最终调试了几次过了样例,交上去WA了,又改了几处交上去还是WA。感觉这个贪心不太可靠,队友又想出了个二分 + 拓扑排序的东西,二分答案后,每次找度为1的数,选它,如果每个数至少出现在了2天,则一定有解。我在草稿本尝试构造无解的反例,失败,感觉结论应该是正确的。syz实现后交上去后WA了。此时我延续cyl对B的思路,推出了B的答案表达式,感觉很对,上机开写,写出来后过了样例,和cyl之前写的随机模拟有1个数据相差较大,让我再检查下有没有错,果真发现min的对象取错了,改了两次后和随机数据吻合很好,交上去后WA了。我不理解,又想了十多分钟后,抱着对精度问题的一线希望,改了下long double和除法顺序,cyl提示我输出到15位小数,交上去过了,终于打破了2题的僵局,此时已经过去了2.5小时,我们赛场上决定只看PTA上的过题数,不看榜。换机后我看了下K,查了下字典,quarantine是隔离的意思,很明显的线段树,强制在线,需要动态开点,思路不难想,但维护的标记有点多。队友又改了下二分,交上去终于没有WA了,但很遗憾的TLE了。队友造数据测试,发现极端数据下需要14s,把vector的位置改了下又只需要4s+了,我看1e6的数据量,去码了一个fread快读,还是需要4s+,交上去还是TLE了。15点过的样子,我开始上机写K,发现需要维护的标记比我想象的要多,pushup和pushdown也挺难写的。写了接近半小时,把最艰难的pushup和pushdown基本写完了。在此同时,队友抛弃二分,积极切换思路,认为G肯定有更简单做法,想出了并查集+判环的做法,并替换我上机实现,写完了过不了样例2,cyl思索了一下叹息感觉做法又假了,真让人心如死灰,好在syz感觉还有救,改了两下,终于通过了此题。此时是16:07,还剩不到1h,我全力写K,syz和cyl看J和M。写K的时候我感觉我思路已经很清晰了,精神也很集中,不过由于维护的变量实在太多了,由于是动态开点,加上l,r一个结点总共要维护10个信息,中途不小心把变量搞混了,又得改下pushdown,心理只能暗暗叫苦,Dev上写tr[now].l容易自动补全成tr[now].L也很烦。还剩半小时,队友决定放弃剩下的题一起来看K,16:39我写完了K,却发现样例读不进去,dev调试显示n, m读入了,但后面的却读不进去了,cyl让我直接把快读删掉,过了样例,小小检查了下开大数组交上去了,WA了。只剩不到10min了,我快速通览代码,并给队友讲解,通览一遍没发现写错的地方,于是又开大数组交了几发,在遗憾中结束了本次比赛。

小结

我很遗憾,不理解K为什么会WA,我觉得我写代码的时候思路已经很清晰了,前后花了1h10min多点的样子,3种类型的update和1个query,维护10个信息,3个tag标记,动态开点,写了150行,我也没办法,我觉得我线段树的结构经过长期迭代还是不错了,一般使用重载结构体+运算简化运算合并,但这题动态开点,合并时需要的信息有点多,我还为此时写了一个返回值Node类型的合并函数。17:18我检查代码发现了我下传rec清空标记漏写了传递左右子树的语句,我清晰记得当时我还提醒自己这个下传清空标记要在清空左右子树信息后再传,不如标记会被clear()函数清空,不知道怎么就忘记写了,欸,最后通览检查最后的机会也没有发现。看榜发现就算过了5题也还是铜,银不了,稍微好受了点,在此还得庆幸昨天做了带修主席树并打印了代码,带修主席树用到的动态开点技巧对今天写代码很有帮助,遗憾的时连续3天遇到静态主席树、带修主席树、动态开点线段树,都没有过,今天是离AC最接近的一次,还是差那么一点点,要是考场还能多个10多分钟说不定就过了。

今天真实复刻了前天ICPC2020昆明的经历,签到秒过,27分钟又过了一题,然后剩下的时间基本都被两道题折磨完了,最后铜。连续3天都是铜牌水平。其实从过往成绩来看的话,我们队基本就发挥不错就银,发挥不太好就铜,甚至铁,金我是不奢望的,大概银:铜:铁 = 0.35 : 0.4 : 0.25,要是发挥好能有银今年我就相当满足了,最后是铜尾,反转了,铜尾还得小庆幸一下,算是不幸中的万幸了吧,不然打铁就要被T出队了。

最后,感谢队友的辛勤训练,甚至在我不在的时候vp比赛,没有他们我连铜都拿不到,真的感谢队友在绝望失利的时候能吸取经验,大胆换方法,保住了铜牌。今年的赛季对于我来说就结束力,短暂而无奈,我只能尽力珍惜每次机会吧。比赛结束后,我也有很多ddl要赶了

关于本次比赛,值得肯定的几点:
1. 赛前准备还算充分吧,为了比赛,赛前一段时间大家都放弃了很多,尽可能抽出时间来训练,热身赛后我还补了带修主席树,没想到第二天还真用上了,赛前一天晚上还补了最小费用上下界可行流,以及斜率优化DP,资料和板子也都齐全打印了,感谢syz和cyl帮我打印了板子
2. 队友在绝望的时候大胆抛弃原来的思路,保住了铜牌,保住了校队身份

下次需要注意的地方:
1. 任务栏的快捷图标没有清空,导致中途打开CLion,还好没有打开浏览器
2. 打印的代码没来得及装订,试题也没有装订,找文件有些麻烦
3. 大数据结构题还是谨慎开吧,虽说写之前有把握,但实际花的时间还是会比较多,甚至调不出来,另外,PTA的过题数是计算重数的(会被恶意刷通过数),如果状态好的话还是可以看榜,但不看排名吧

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇