ICPC2023 网络赛 0917第一场游记

Update On 2023.10.21

CF gym上也有链接了,可以看榜vp了。


看题链接 每天签到可得5金币,取消勾选“同时购买时光机”,花1金币购买题目集就能看题交题了。

有个队友去实习了,2人场,高罚时7题。

机房电脑比较卡,用的队友的笔记本。

跟榜,看L题过了人,就看了一眼,发现是大水题。既然用的是队友的笔记本,就扔给队友写。

队友写L我看A,队友写A我看D,队友写D我看J,总之前半场我根本没碰到键盘。队友:我就是个打工人。

J题一开始我猜答案是 $C_2$ 与两个圆心的交点到 $C_1$ 圆心的距离,队友用python手玩了下样例,发现答案不对。后来队友推了个公式,A了。

然后我看I,想了个trival的DP, 写到一半发现当出现连续问号时时间复杂度会变成 $\Theta(62^2\times 8\times n)$ , 极限数据下有 $3\times 10^8$ ,考虑到时限1s没敢交,就先放着。

队友说G过了很多人,但他数据结构不好,就让我看。我一眼秒掉,这不就是个Kruskal重构树+dfs序+树状数组二维数点吗!时间复杂度 $\Theta(n\log n)$ ,1e6,1s,问题不大,开写!同时让队友接着想I。

作为老年人写了很长时间终于写完了,交了一发,发现MLE,以为是哪里有bug导致爆栈了。队友I题想了一个奇怪的分类讨论做法,我打印G代码,队友写I。

我找不到G的bug,同时队友说自己写不动I的分类讨论。此时我想出了I的正解,去掉了一个62,变成了 $\Theta(62 \times 8 \times n)$ 。于是写I,交I,过。用时接近0.5s,看来评测机速度一般。

看K题,感觉K题结论显然,但我不会危寄坟。队友去积K题的分,过了K。

现在只剩G了,我用python造了一组G的极限数据,队友打开Win11的任务管理器,发现程序能正常结束,但真的会MLE。队友使用__attribute((packed))禁止结构体对齐,成功以内存230M/256M,时间951ms/1000ms的优秀效率AC,下班。

Licensed under CC BY-NC-SA 4.0
使用 Hugo 构建
主题 StackJimmy 设计