ABC397 做题记录

· · 个人记录

一场极其抽象的 ABC

A

没什么好说的，直接过了

B

直接过了

C

正着来一遍，倒着来一遍，完事

D

全场最大败笔。

在场上，我首先想到枚举其中一个数，然后算另一个。

发现在两个数差 1 的情况下，小的那个数不会超过 4\times 10^8 。

然后喜提 TLE

然后想到 a^3-b^3=(a-b)(a^2+ab+b^2)=n

这样可以枚举 (a-b)，是 sqrt(n) 的。

又喜提 TLE

扔到自定义测试上，发现 1\times 10^{18} 跑了不到 3s

尝试卡常，未果

此时已经将近 21:10，果断弃掉。

赛后炜哥讲了他的枚举两个数的差，再二分的做法，突然意识到我这个枚举的也是差，而差不可能大于 1\times 10^6

糖丸了

E

但是没写完。 赛后写完，发现挂了，先睡觉。 早上调到只 WA 最后两个 然后发现 $k=1$ 时没特判... ## F 扫了一眼 E，F 发现 F 好像好写，于是先写 F 发现只要知道断点，直接做完了 发现可以 $O(n^2)$ dp 遂想到扔到线段树上，枚举第二个断点 $i$。线段树的每一个点表示以每个点为第一段结尾、第二段结尾在 $i$ 权值。 每个数只会在 $la$ 到 $i-1$ 有贡献。 最后一段的贡献可以预处理。 做完了。 ## 总结 看了榜1的 D，发现我的最开始的枚举也可以，只是加一个双指针就行，直接做还是太劣了。 炜哥的 E 写的跟我不太一样，但是大差不差，是按树高向上做，挺对的，还短好多，没有我那么多特判。 F 扫了一眼基本上全是一样的写法。 还是要多注意一些小细节，避免悲剧的再次发生。