论剑F题。。咋一看各种数据需要处理和判断,好像很麻烦。。但是仔细思考之后。其实可以将问题分解为若干个子问题概率来处理;
对于该概率问题,可以先用一个代表颜色的数组分别遍历一遍男主的衣服和裤子,然后得到各种颜色对应的件数,然后就是重点开始了:
遍历出男主的各种穿衣穿裤情况,对应每种情况下算出当前的概率p,并调用一个函数来计算出全部女生中恰好有x个人穿相同衣服裤子的概率和。然后返回与p相乘,继续累加,最终即可得到结果;
点播:
1.对于求出每种颜色的衣服裤子各有多少件,用一个代表颜色的数组去遍历是比较方便后面的利用的;
2.在函数里求概率的时候,应再分解问题,变成先求出每个女生与男主相同的概率,然后用排列组合思想来选出x个的概率。
3.对于第二点中求出x个的概率,
①可以用“位枚举法”,因为每个女生的概率都可以表示为“取”或“不取”,取记为1,概率为p,不取记为0,概率为(1-p);复杂度O2^n(不过要不断优化不然就TLE,但是不确定是否能优化至AC,据说有种DFS+预处理的方法可以强行达到4700MS去AC)
②可以用dp数组,理由与原理与①点相同,注意对dp数组的初始化 和 边界情况的特殊处理,但是却可以大大的减少复杂度,On^2,最终以48ms的速度AC了这道题;
DP方程:dp[i][j]表示从前i个女生取j个与男主穿着相同的概率;
核心代码:
dp[0][0] = 1;
for (i = 1; i <= k; ++i)
{
for (j = 0; j <= i; ++j)
{
if (j - 1 < 0) dp[i][j] = dp[i - 1][j] * (1 - lolip[i]);
else dp[i][j] = dp[i - 1][j] * (1 - lolip[i]) + dp[i - 1][j - 1] * lolip[i];
}
}
return dp[k][x];
4.对于第三点中的①,位枚举法,虽然相当暴力,但也算是一种思想;
就是用二进制(对于每个小事件只有取或不取两种情况)来枚举每一种情况,比如有k个人,那么可以用[0,2^k)的数来表示各种情况!注意区间范围。。。
举例说明:比如,有2个人,那么情况可以有4中,分别是00,01,10,11,各自作为二进制表示的数应该明了了吧。
分享到:
相关推荐
书中全面具体地对该教材中各章的习题做了详细解答,对每一道题都进行了必要的分析和代码注释,力求通过实例让读者全面掌握面向对象与可视化程序设计的思路和开发技巧。同时,为让读者更好地掌握“Visual C++面向对象...
1、北邮考博2006年春季考题回忆+2007秋季通信网理论基础试题回忆 ...槪随机过程包括40分填空,10分概率一道(随机变量的独立性),随机5道大题(涉及复合普瓦松过程、高斯过程、信号通过随机系统等)
SGU 385,我写的程序,一道DP题,跟概率有关
(1)用户提交答题广场中占比12.05%的题号id为25958295,知识点是关于多边形的内角和外角,在2016年河南中考中没有单独题目是考本知识点的,河南只有一道3分的填空题。在中考的所占比重是极小的。 (2)3.1-6.15...
最后一道大题是两年重复的试题,虽然之后还考的概率较低,但毕竟是经典大题,建议着重复习相关知识。 最后如果不想下载,这里还有复习重点省流: T0——TCP握手和TCP消息阻塞的解决机制,各类TCP相关机制包括RTO快速...
2 最大似然估计与贝叶斯估计的不同(作业) 3 对于c类问题,假定各类条件概率密度函数均为多元正态分布。在最小错误率贝叶斯决策框架下,在什么情况下可以得到线性判别函数...(2) 最近邻的一道计算题,类似这道(作业)
这究竟是怎样神奇的一道面试题?他考察了候选人的哪些能力?对正在读本文的你有什么启示?且听我慢慢道来 不起眼的开始 招聘前端工程师,尤其是中高级前端工程师,扎实的 JS 基础绝对是必要条件,基础不扎实的工程师...
本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、...书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。
有 n 个题,每个题有 ai 个选项,给出一份正确答案,把每个题的正确答案填到后一道上,最后一个题填到第一个题上。问:做对的题目个数的期望值,保留三位小数 分析 很明显,每道题都可以作为一个独立事件,并且都为...
本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、...书中的每一道题都是面试的高频题目,反复出现在最近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。
《编程之法:面试和算法心得》涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路...书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。
《编程之法:面试和算法心得》涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路...书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。
书中的每一道题都是面试的高频题目,反复出现在最近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。, 全书逻辑清晰、通俗易懂,适合 热爱编程、算法、机器学习,以及准备IT笔试和面试,即将求职、找工作...
插图、书签齐全,修正小错误,epub格式 适合手机读 《编程之法:面试和算法心得》涉及面试、算法、机器...书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。
书中的每一道题都是面试的高频题目,反复出现在最近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。 全书逻辑清晰、通俗易懂,适合热爱编程、算法、机器学习,以及准备IT笔试和面试,即将求职、找工作的...
书中的每一道题都是面试的高频题目,反复出现在最近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。 全书逻辑清晰、通俗易懂,适合热爱编程、算法、机器学习,以及准备IT笔试和面试,即将求职、找工作的...
前端面试手写题整理前端面试常见的手写题,面试出现概率极高,建议每个都过自己过一遍。你也可以提交 PR,提供你面试遇到的题目。代码汇总请参照 。高频:★★★ 中频:★★ 低频:★JavaScript 原理 ★★ ★★ ★★...