毒瘤啊啊啊啊啊
虽然排名还不错,331,但是B我没做出来......
这是战绩:
可以看到我大发神威势如破竹的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 间。(我又忘了对数指数的求导了)
然后我们可以分类讨论(打表)来解决。
表如下:
然后就可以随便水啦...
其实我一开始也打表了,但是用的是快速幂,后面爆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,我弃疗了。