企业网站建设遵循的原则,手机网站用户体验,在家给别人做网站合法吗,免费下载教学设计的网站题目#xff1a;F - Fireworks#xff08;三分概率#xff09;
来自#xff1a;2020-2021 ICPC区域赛南京站F题
牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
题意#xff1a;
一个人造烟花#xff0c;制作一个烟花需要n的时间F - Fireworks三分概率
来自2020-2021 ICPC区域赛南京站F题
牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
题意
一个人造烟花制作一个烟花需要n的时间燃放烟花的时间是m燃放一个烟花是m燃放多个烟花也是m但是由于此人手艺不精烟花完美的概率是p。注意烟花只有放了才知道是不是完美的。如果所有燃放的烟花中至少有一个是完美的则结束。问实现该情况的最小期望
思路 期望 一种情况的权值 * 其概率 另一种情况的权值 * 其概率 … 假设一个Ex表示多次造k个烟花后燃放出现至少一个完美烟花的概率最大的最小期望简称最优 形象的讲不保证正确但是好理解每次都造k个后燃放出现完美烟花的概率是最大的所以每次我们都只造k个烟花后燃放 所以 E ( x ) ( k × n m ) × ( 1 − ( 1 − p ) k ) ( k × n m ) × ( 1 − p ) k E ( x ) × ( 1 − p ) k E(x)(k×nm)×(1−(1-p)^k)(k×nm)×(1-p)^kE(x)×(1-p)^k E(x)(k×nm)×(1−(1−p)k)(k×nm)×(1−p)kE(x)×(1−p)k 分三块去理解 1. ( k × n m ) × ( 1 − ( 1 − p ) k ) 表示当前次制作 k 个烟花后燃放至少出现一次完美烟花的概率 ∗ 消耗的时间 2. ( k × n m ) × ( 1 − p ) k 表示当前次制作 k 个烟花后燃放一次完美烟花都没有的概率 ∗ 单次消耗的时间 3. E ( x ) × ( 1 − p ) k 表示之前所有次都失败的概率 ∗ 之前用的所有时间 \begin{aligned} 1. (k×nm)×(1−(1-p)^k) 表示当前次制作k个烟花后燃放至少出现一次完美烟花的概率*消耗的时间 \\ 2. (k×nm)×(1-p)^k 表示当前次制作k个烟花后燃放一次完美烟花都没有的概率*单次消耗的时间 \\ 3. E(x)×(1-p)^k 表示之前所有次都失败的概率*之前用的所有时间 \end{aligned} 1.(k×nm)×(1−(1−p)k)表示当前次制作k个烟花后燃放至少出现一次完美烟花的概率∗消耗的时间2.(k×nm)×(1−p)k表示当前次制作k个烟花后燃放一次完美烟花都没有的概率∗单次消耗的时间3.E(x)×(1−p)k表示之前所有次都失败的概率∗之前用的所有时间 化简公式后发现 E ( x ) k × n m 1 − ( 1 − p ) k E(x) \frac{k×nm} {1-(1-p)^k} E(x)1−(1−p)kk×nm
打表或求导可以看出该函数是个具有波谷的函数用三分找到k次就可求出E(x)
代码
#includebits/stdc.h
#includeunordered_set
#define HighPrecisionPrint(n) printf(%.11f\n, (n)) // 答案误差在10^-11次方内的打印
#define UNIQUE(arr) (arr).erase(unique((arr).begin(),(arr).end()),(arr).end()) //将重复的区域删除
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define all(arr) (arr).begin(), (arr).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf 0x3f3f3f3f;
const double eps 1e-7;
int t;
double m,n,p;/** 题意一个人造烟花制作一个烟花需要n的时间* 燃放烟花的时间是m燃放一个烟花是m燃放多个烟花也是m但是由于此人手艺不精烟花完美的概率是p。* 注意烟花只有放了才知道是不是完美的。* 如果所有燃放的烟花中至少有一个是完美的则结束。* 问实现该情况的最小期望
*/
double Ex(int k)
{double ex (n*km) / (1-pow(1-p,k));return ex;
}
void solve()
{cinnmp;p p/1e4;double l 1, r 1000000000;while(r-l eps){double mid1 l (r-l) / 3;double mid2 r - (r-l) / 3;if(Ex(mid1) Ex(mid2)) l mid1;else r mid2;}// 保障计算如果最后l和r是左右两个点并没有在波谷汇合所以要手动枚举while的情况不需要// for(int i l1; i r; i)// ans min(ans,Ex(i));HighPrecisionPrint(Ex(r));
}
int main()
{cin t;while (t--){solve();}return 0;
}
特别鸣谢队友Gary解释思路以及xjsc01提供的题解思路
