Codeforces_768_D_(概率dp)
2 seconds
256 megabytes
standard input
standard output
Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are k different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood tree north of the wall. The probability of this orb being of any kind is equal. As the north of wall is full of dangers, he wants to know the minimum number of days he should wait before sending a ranger to collect the orbs such that the probability of him getting at least one of each kind of orb is at least , where ε < 10 - 7.
To better prepare himself, he wants to know the answer for q different values of pi. Since he is busy designing the battle strategy with Sam, he asks you for your help.
First line consists of two space separated integers k, q (1 ≤ k, q ≤ 1000) — number of different kinds of orbs and number of queries respectively.
Each of the next q lines contain a single integer pi (1 ≤ pi ≤ 1000) — i-th query.
Output q lines. On i-th of them output single integer — answer for i-th query.
1 1
1
1
2 2
1
2
2
2
题意:有k种球,每天可得到一个球,其种类是任意一种,问每种球至少有一个的概率至少为 (p<1000)需要几天。
自己只想到用概率去算,但是也不知对不对,几乎没有思路,于是看了官方题解。
思路:dp[i][j]:第i天有j种的概率。那么可以有dp[i][j]=dp[i-1][j]*(j/k)+dp[i-1][j-1]*(k-j+1)/k;
看了题解觉得很容易,但是自己却想不到啊。。。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10005
double dp[N][]; int main()
{
int k,q;
scanf("%d%d",&k,&q);
dp[][]=;
for(int i=; i<N; i++)
for(int j=; j<=k; j++)
dp[i][j]=dp[i-][j]*((double)j/k)+dp[i-][j-]*((double)(k-j+)/k);
while(q--)
{
double p;
scanf("%lf",&p);
int i;
for(i=; i<N; i++)
if(dp[i][k]>=(p/))
break;
printf("%d\n",i);
}
return ;
}
最新文章
- 全球首发免费的MySql for Entity Framework Core
- Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors
- JS中iframe相关的window.self,window.parent,window.top
- 银行卡BIN码大全
- jgroups 入门
- java学习笔记_MIDI_GUI
- Angular2学习
- 解决 iOS webkit 使用CSS动画时闪烁的问题
- 使用python写appium用例
- RPC框架实现思路浅析
- DxPackNet 3.音频捕捉(录音)
- 学习笔记7-Android短信发送器
- Google 以 Flutter 作为原生突破口,移动端即将统一了
- 一个故事讲清楚BIO NIO 异步
- Spring 框架下 事务的配置(复杂)
- c# 二进制序列化
- Python+selenium点击网页上指定坐标
- poj3279(dfs+二进制枚举思路)
- Qt Creator设置多核编译(-j8参数)
- asp.net 4高级程序设计( 第4版)文摘