自动搬运

查看原文

来自洛谷，原作者为

	WeLikeStudying 

搬运于2025-08-24 22:36:46，当前版本为作者最后更新于2022-06-18 08:57:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 好题啊！以后就按照这样的策略水分！等等似乎如果奶牛不那么蠢的话早就水满分了。
• 就是最后发现数据点多的时候得分根本上不去十分的尬。
• 为啥要用矩阵乘法啊，普及组蒟蒻表示不解。
• 普及组蒟蒻只会用 $\text{C++}$ 特性，但复杂度好像是 $O(n)$ 的呢。
• 普及组蒟蒻不知道库函数复杂度很合理吧，作者猜测由于浮点数的特性，计算方法可能与数值大小关系不大。

题目

• 你有 $T$ 道判断题，你只会做第一道，所以你打算其它的你瞎蒙。
• 你最多可以交 $K$ 次，每次你都可以得到成绩，但是你的自主权只有：是否把这次作为最终成绩，或者放弃这次结果重新提交一份？你由于智商，每次都会交随机数。
• 如果你充分利用你的自主权，使用最优策略，你期望可以拿到多少分？
• $2\le T\le 10^3,1\le K\le 10^9$。

分析

• 首先，你发现对于一个固定的局面：还有 $K$ 个测试点，你得到了分数 $S$，你交还是不交是固定的，那么显然有一个 $f(K)$，大于等于它你就不需要再交，否则你还是再交一次，利用组合数，我们可以 $O(n^2)$ 得到它的概率分布，枚举最优转移点，我们就得到了 $O(nk)$ 的暴力，代码。
• 然后你发现你实际上是在求一个凸壳的最值，由于转移点单调，我们可以用类似旋转卡壳的方法做到 $O(k)$，代码，或者你发现 $K-1$ 的期望就是 $f(K)$ 也可以，代码。
• 然后你发现转移点相同的迭代过程的嵌套，展开出来是这样的：比如把 $ax+b\to x$ 赋值 $n$ 次，展开是一个等比数列求和，为 $a^nx+\frac{a^n-1}{a-1}\cdot b$ 这可以用库函数直接算（需要特判 $a=1,b=0$）。
• 显然答案满足单调性，所以我们二分就得到了 $O(n^2+n\log k)$ 的方法，代码。
• $O(n^2)$ 显然可以优化，为了考虑精度，这里对阶乘取 $\ln$，可以防止掉精度，复杂度 $O(n\log k)$，代码，其实这份代码精度最高。
• 或许我们有更好的，不用二分的方法，那就是对函数进行分析，我们之前的做法本质上就是找到每个 $f(K)$ 的取值在 $K$ 上形成的区间，那么反正我们有强大的库函数，直接找不就行了？
• 如果函数嵌套之后没有增加，就直接跳，否则直接求出它的作用区间就好了，复杂度 $O(n)$，代码。