题解 CF248E 【Piglet's Birthday】

xtx1092515503 · 2020-04-01 18:16:16 · 题解

写这篇题解是因为有一个小点我对当前两篇题解里的一个内容有异议。

首先先写做法。

我们可以设f[i][j]表示：

橱子i，剩了j个罐子没吃过的概率。

再设num_i表示橱子i初始罐数，now_i表示橱子i当前罐数。

则在f[i][j]中，必有j\leq\min(num_i,now_i)，因为如果从其它地方搬来了罐子，则这些罐子一定是已经被吃过的。

当我们有一次从u到v搬了w个罐子的操作时：

位置v的f值不会有任何影响——搬来的罐子吃过了。

位置u的罐子可以通过排列组合算出来：

其中，C_{k}^{k-j}表示从k个没吃过的罐子中选出k-j个罐子吃的方案数；C_{now_u-k}^{w-(k-j)}表示从now_u-k个吃过的罐子中选出w-(k-j)个罐子吃的方案数。

然后就是我有异议的地方了：

似乎题面里也没有规定这个now_u最大能到多少吧？

如果我们考虑极端情况，每次都从一个地方搬5个罐子过来，则now_u最大可以到500100！

而两篇题解里面预处理的C数组，都是1000\times1000的。

一个极端数据很容易就能卡掉。

我认为这个C数组应该预处理成500100\times5的，因为k-j,w-(k-j),w，这三者都是\leq5的。

虽然可能数据并没有卡错误的C范围，但是做题还是严谨一点好。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500100;
int n,num[100100],q,now[100100];
double f[100100][110],C[500500][10],res;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]),now[i]=num[i],f[i][num[i]]=1,res+=f[i][0];
    for(int i=0;i<=MAXN;i++)C[i][0]=1;
    for(int i=1;i<=MAXN;i++)for(int j=1;j<=min(i,5);j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
    scanf("%d",&q);
    for(int i=1,u,v,w;i<=q;i++){
        scanf("%d%d%d",&u,&v,&w);
        res-=f[u][0];
        for(int j=0;j<=num[u];j++){
            double ans=0;
            for(int k=j;k<=min(j+w,now[u]);k++)ans+=f[u][k]*C[k][k-j]*C[now[u]-k][w-(k-j)];
            f[u][j]=ans/C[now[u]][w];
        }
        res+=f[u][0],now[u]-=w,now[v]+=w;
        printf("%.9lf\n",res);
    }
    return 0;
}