【简单题】如何利用提交的限制智慧地水分

WeLikeStudying · 2022-06-18 08:57:04 · 题解

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

题目

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

分析

• 首先，你发现对于一个固定的局面：还有 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) 的方法，代码。
• 或许我们有更好的，不用二分的方法，那就是对函数进行分析，我们之前的做法本质上就是找到每个 f(K) 的取值在 K 上形成的区间，那么反正我们有强大的库函数，直接找不就行了？
• 如果函数嵌套之后没有增加，就直接跳，否则直接求出它的作用区间就好了，复杂度 O(n)，代码。