ICPC2023 EC-final 总结
赛前
刚刚考完期末,于是全力以赴投入了比赛准备,把前几年的 ec-final 都刷了一遍,一周打了 4~5 场的样子。
热身赛
好在是在上海本地打所以省去了很多行程上的时间。热身赛给我的感觉就是好冷啊,这场地怎么跟开了冷空调似的!!C 是做过的,B 队友口胡了一下,D 队友抄了个板子,然后就是正常地把该测的都测了一下。
正式赛
过题数:6
排名:66
复盘:
- lym 推荐我们先看粉色气球的 C 和 M,我看了一眼 M 觉得好像不是很签,lym 看完 C 觉得离谱儿,看榜发现 B 被开出来于是两个队友看 B 我继续想 M。想了一会还是没头绪,榜上有人过 E 于是我先去看 E 了。两个队友很快签完 B,23min 1A;
- lym 去开 K,lhc 和我一起搞 E。我们先猜了一下贪心构造极大团是最优的,然后发现对
d=1 要特判让整个图是一个团。交上去 WA 了。手玩一下发现d=2 的时候不是极大团更优,这时lhc 去听 lym 的 K 做法,我又想了几个假做法之后发现这种情况只要颜色不相同的都连边就行了并且d\ge 3 的情况也给了贪心的感性证明(对于一个极大团不可能插上去任何一个点),交上去 62min 2A; - lym 上机写 K,我和 lhc 跟榜开 F。一上来我样例 2 玩了很久没玩出来,lhc 给了个相邻两个数可能不会差太大的结论然后被叉了;
- 82min 的时候 lym 写完了 K,WA 了;lhc 去帮 lym 一起调 K,我想 F 想了一会发现从全局来看的确相邻两个数就不能差太大,进一步发现了答案序列只能是
1,2,\dots,n 交换相邻的一些数对的结果,但有了这个性质我还不知道怎么计算答案。 - K WA 了好几发后 lhc 上去写对拍,lym 下来和我一起搞 F,我把性质喂给他之后他立刻想到了怎么算答案,我修了一个小细节之后上去写,期间 K 的对拍也拍出了错误样例,队友在看+改K的时候我交替写 F,F 148min 1A。
- K 修完拍出来的错之后,连拍几万组都没错,交了一发又 WA,过了十几分钟发现这一发的
freopen没删,改了就过了,151min 5A。 - 我和 lym 开构造题 L,lhc 去开别的。我们讨论了一会很快搞出一个先删再加的做法,非常轻松愉快地写完,186min 1A。
- lhc 把榜上过得最多的交互题 J 的题意喂给我们,我们决定 All in J。我先从树开始考虑很快给出一种在树情况下能够 4n 步以内完成的做法,然后考虑 dfs 树上非树边的影响,讨论了一会发现树边要走至多 4 次,非树边至多走 2 次,刚好满足限制。得到这个 idea 的时候大约还剩 70 min。
- 两个队友看着我一起写 J,266 min 写完把样例跑通就交了但 WA 了(神奇的是我写了如果交互器在判答案时不返回 correct 就自动
assert(0)),我写了个本地交互器玩了一下 4 阶完全图发现居然会出现不合法询问的情况。 - 三个人对着调试信息看了一会我突然发现非树边的某个分支里没有更新当前所在的节点,加上一句
u=v之后就能跑过 4 阶完全图了,此时 289min,提交,绝杀!
总结
绝杀的那一刻非常激动,这个赛季是真的圆满了,虽然绩点掉了