CF 987

时间:2020-12-26 18:25:38

毒瘤啊啊啊啊啊

虽然排名还不错,331,但是B我没做出来......

这是战绩:

CF 987

可以看到我大发神威势如破竹的A了CDE,但是B把我卡了三次...不然我就能进前300了(还是很水)。

逐一分析题目:

A不多说了,随便开个map完事。

B...比较  x ^ y 和 y ^ x 的大小。

数据范围 [1, 10 ^ 9]

思考之后发现可以取对数。

然后连WA三次,精度分别是1e-10,1e-12,1e-7

赛后发现精度1e-6就A了,WA的那个点是两个10000000000,我......

拉到自己电脑上跑,A了......CF有毒。

不科学...........

最后我发现了一种新♂方法。

y * log(x) @ x * log(y)

log(x) / x @ log(y) / y

考虑这个函数的单调性:最大值在 1 ~ 2 间。(我又忘了对数指数的求导了)

然后我们可以分类讨论(打表)来解决。

表如下:

CF 987

然后就可以随便水啦...

其实我一开始也打表了,但是用的是快速幂,后面爆long long了,打的表不准。

然后想到对数就抛弃打表了。

所以说,怪CF评测不准!!!

C:

大意:求使得i < j < k && a[i] < a[j] < a[k]时的cost[i] + cost[j] + cost[k] min

一开始以为是数据结构,然后想到按照cost排序慢慢加,最后想到DP。

发现DP能过。

因为这题可以容忍n²的复杂度,所以我令f[j]表示所有a[i] < a[j] && i < j中的最小cost

然后对于f[i]扫两遍,第一遍以i为第三个数更新ans,第二遍更新f[i]

然后A了。

D:

图论题。

以每种type做BFS,然后每个点排序。

复杂度(n  +  m) * k + n * k * log(k)

感觉会超时,然后发现时限2s,A了。

发现排名还是1000多,有点伤心。

来到E题:哇!做过!

直接秒A,排名300多。

来到F:不会,再见。

此时还剩下49min,我弃疗了。