ICPC第一场网络预选赛游寄

CCPC被禁赛,只能打ICPC了

Posted by ethan-zhou on September 18, 2022

按照之前的开题顺序,我开中间四题。然后就发现 F 题是之前 HDU 的原题,然而是个重量级的数论,上次我们就没过。

读着题的时候,破壁人就说 L 很签,上机写了一会,又突然说假了。

于是我就上去签 H,在 17 分钟过了。这个 H 的题面就非常灵性,让我更深刻的理解了 CCPC “比赛中不能打开头文件”的规则。

H 题面:

啪的一下,很快呀 wky 就说 C 也是签到,遂在 22 min 通过。此时,由于我们手速飞快,排名在第五,这也是整场比赛排名最高的时候。

于是我开了 G,wky 开始构造 D。过了一会,wky 想出一个构造,于是开写,然而样例挂了。于是我就胡了一个 $O(\log n^2)$ 的做法,找到小于 $R$ 的最大好数,写完之后也挂了。但是在和 wky 讲了做法之后,wky也觉得没啥问题,于是把代码虚拟打印出来静态查错,wky 发现是有一个地方把 $+1$ 写成了 $-1$。改完遂在 71 分钟通过。

赛后才知道直接暴力搜也可以过。

我们调试的时候,破壁人一直在机器上写 L,也在78分钟通过。

此时,G 我还只会一个 $O(n^5)$ 做法,然而 $n$ 是 $100$。这熟悉的数据范围和复杂度不禁让我浮想联翩,想起了之前某场 cf 中一道臭名昭著的卡常题,其复杂度为 $\frac{n^5}{100},n=100$,其中 $\frac1{100}$ 是常数,我只能说,BDFZ 的同学应该懂得都懂。

然后我发现,有效的状态数只有 $\frac{n^5}{4!}$ 甚至 $\frac{n^5}{5!}$,于是滚动了一下数组,遂在 138 分钟通过。

G 这题也让我受益匪浅,对 CCPC 中的 “5 秒原则” 有了更加深刻的体会。

G 题面:

过完了 G,破壁人又在 147 分钟过了 J。随后,wky A 题猜了一个结论,写了暴力,能过样例。于是写了一个线段树过了,并锐评道:“这题为啥不出带修?其实不出待修也可以猫树分治”。

剩下的时间我和破壁人想 K,wky 开始推 F 的式子。

一开始 K 只会 $O(n^3)$ 做法,过了一会,破壁人告诉我最优解里头 $w$ 不会超过 $O(\sqrt n)$ 量级,于是复杂度变成 $O(n^{2.5})$。我又想了半天数据结构优化,未果。于是觉得可能还有什么结论没被我们发现。

手玩了一会数据,突然发现一个构造,可以证明 $n-ans\le O(\sqrt n)$。当时脑子卡壳,于是又问破壁人这个性质是否有用,破壁人告诉我可以直接把之前记答案那维改成记答案与当前 $i$ 之差即可。于是口胡出来一个 $O(n^2)$ 做法。上机写了一发,评测等了一分钟,在 245 分钟过了。

于是 wky 和破壁人开始讨论 F,突然发现 wky 某个式子写错了,并且和之前假期打 HDU 错的一模一样。于是在一片快活的气氛中,wky 含泪注释掉自己刚写的代码,又写了一阵,终于过了样例,手动测了极限数据也跑的不慢,结果一交 T 了。

结果发现是因为 wky 的预处理放在读入的前面,所以没有算在极限数据的时间里头。算上预处理,极限数据跑的就慢了。

于是 wky 就开始疯狂卡常数,最后卡到本机极限数据 0.7 秒,然而一直还是过不了。

wky 卡常的时候,我口胡出了一个 I 的做法,然而先要在值域上分治,还要写个 fft,剩下的时间也不够写了,于是作罢。

最后排名 46,小寄。

有一支科大学长的队伍在封榜之后过了两题,最后以 10 题吊打我们,十分震撼。当然,EI 队的 11 题就不用说了。


作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接


阅读量:


icon