【题目链接】:http://codeforces.com/contest/768/problem/D

【题意】



你有一个水晶;

它每天都会产生一个球??(球有k种)

然后每种球产生的可能性是相同的->1/k

然后给你q个询问;

每个询问pi;

问你最少需要多少天;

每种球至少有一个的概率大于等于pi/2000;

这里pi<=1000

【题解】



动态规划;

考虑按天划分状态;

设f[i][j]表示第i天一共有j种球的概率;

则第i天考虑两种情况

1.拿到了一个新的球，从原来的j-1种球变成了j种球->概率是(k-j+1)/k

2.拿到了原先就有的球,原来的j种球,球类总数不变,天数增加了1->概率是j/k

则有动态转移方程

f[i][j] = f[i-1][j-1]*(k-j+1)/k+f[i-1][j]*j/k;

直到f[i][k]>1/2就好了;

因为pi最大为1000,而分母为2000;

数组第一维开多大??

1000*10

为什么??

猜

是因为循环次数吧.

或者你再开大一点也没关系：->中间break掉就好

只要不超时就好;

可以预处理出1..1000的答案;

扫一遍就可以了



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 1e3+100;

int k, q,ans[N];

double f[N * 10][N];

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(k), rei(q);

    f[0][0] = 1;

    rep1(i, 1, 10000)

    {

        rep1(j, 1, k)

            f[i][j] = f[i - 1][j - 1] * ((k - j + 1)*1.0 / (1.0*k)) + f[i - 1][j] * (j*1.0 / (1.0*k));

        if (f[i][k] > 0.5) break;

    }

    int now = 1;

    rep1(i, 1, 1000)

    {

        while (f[now][k] * 2000 < i)

            now++;

        ans[i] = now;

    }

    while (q--)

    {

        int x;

        rei(x);

        cout << ans[x] << endl;

    }

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}