发布于

lp1654 OSU!

真是棒到不行!OSU!

首先，我们可以知道，对于长度为\(x\)的线段，在其后加上一个新的长度为1的线段，新线段的价值是\((x+1)^3\)
那么，价值的差便是：
$$3*x^2+3*x+1$$
而这样的贡献必须要当前点被选中才可行的。似乎可以得到：
$$f_{i}=f_{i-1}*(1-p_{i})+(f_{i-1}^3+3*f_{i-1}^2+3*f_{i-1}+1)*p_{i}$$
但仔细观察就可以发现这样显然是错误的。
这是因为，平方的期望不等于期望的平方。
因此，对于平方的期望，以及一次方的期望，我们应当另外维护两个函数\(g,u\)，分别表示平方的期望和一次方的期望。
那么：
$$g_{i}=(g_{i-1}+2*u_{i-1}+1)*p_{i}$$
$$u_{i}=(u_{i-1}+1)*p_{i}$$
于是：
$$f_{i}=f_{i-1}+(3*g_{i-1}+3*u_{i-1}+1)*p_{i}$$
问题得解。
这一题还是很有思维难度的。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
double p[100005],u[100005],g[100005],f[100005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf",&p[i]);
    }
    u[0]=g[0]=f[0]=0;
    double ans=0;
    for(int i=1;i<=n;++i){
        u[i]=(u[i-1]+1)*p[i];
        g[i]=(g[i-1]+2*u[i-1]+1)*p[i];
        f[i]=f[i-1]+(3*g[i-1]+3*u[i-1]+1)*p[i];
        ans+=f[i];
    }
    printf("%.1lf",f[n]);
    
}
int main(){
    init();
    return 0;
}
发布于

CF148D Bag of mice

看到\(w,b \le 1000\)，我们可以大胆猜想复杂度是\(w*b\)的（大雾）
那么我们设\(f[i][j]\)表示，包里还剩下\(i\)只白老鼠，\(j\)只黑老鼠的时候，轮到公主抽，赢的期望。
仔细看了看题意（之前题意看错了，瞎想半天，淦。），我们可以发现，公主输会发生在两种情况下：
一：包里没有白老鼠了；二：公主抽到了黑老鼠而龙抽到了白老鼠。
同时，对于一个局面，公主胜利的概率有两部分；
一：公主抽到了白球。二：公主的状态转移到的状态抽到了白球。
我们分类讨论。
首先，依据公主抽到白球的概率是\(\frac{i}{i+j}\)，我们可以知道：
$$f_{i,j}+=\frac{i}{i+j}$$
然后，用填表法，我们发现，公主抽到了黑老鼠且龙抽到黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}$$
在这种情况下，跑出一只白老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}$$
跑出一只黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
所以得到转移方程：
$$f_{i,j}=\frac{j}{i+j}*\frac{j-1}{i+j-1}+f_{i-1,j-2}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}+$$
$$f_{i,j-3}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
于是填表法可得解。

#include<iostream>
#include<cstdio>
using namespace std;
int w,b;
double f[1005][1005];
void init(){
    scanf("%d%d",&w,&b);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]=0;
        }
    }
    for(int i=1;i<=w;++i){
        f[i][0]=1;
    }
    for(int i=1;i<=b;++i){
        f[0][i]=0;
    }
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]+=(double)i/(i+j);
            if(j>=2){
                f[i][j]+=f[i-1][j-2]*(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);
            }
            if(j>=3){
                f[i][j]+=f[i][j-3]*(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
            }
        }
    }
    printf("%.9lf",f[w][b]);
}
int main(){
    init();
    return 0;
}

 

发布于

sp1026 Favorite Dice

开始学习期望DP。
这是一道期望DP入门题。
首先我们设\(f[i]\)表示，已经取了\(i\)种数，距离取完的期望回合数。
根据概率的基本定理，我们可以知道，已经取了\(k\)种以后，下一种取到的是未取到过的概率是\(\frac{n-k}{n} \)；而取到的是取过的概率是\(\frac{k}{n}\)
我们很容易可以知道，已经取了\(i\)种数，下一次取可能有两种情况：
一：取到的是一种新的数。
二：取到的是已经取到过的数。
但无论如何都要再取一次才有造成状态改变的空间。
故而我们得到方程：
$$ f_{i}=\frac{n-i}{n}*f_{i+1}+\frac{i}{n}*f_{i}+1 $$
即：
$$ n*f_{i}=(n-i)*f_{i+1}+i*f_{i}+n $$
从而得到：
$$ f_{i}=\frac{(n-i)*f_{i+1}+n}{n-i} $$
等价于：
$$ f_{i}=f_{i+1}+\frac{n}{n-i} $$
于是我们得到了逆向的递推方程。
然后是边界条件。很显然，\(f_{n}=0\)，这是因为，已经取到\(n\)种以后，就意味着已经取完了。

#include<iostream>
#include<cstdio>
using namespace std;
double f[1005];
int n;
void init(){
    scanf("%d",&n);
    f[n]=0;
    for(int i=n-1;i>=0;--i){
        f[i]=f[i+1]+(double)n/(n-i);
    }
    printf("%.2lf\n",f[0]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

停课第二天。

停课第二天，距离NOIP2018还有11天。

停课的喜悦感弱了很多。

对可能取得的成绩充满担忧。

今天做了什么事呢？
打了两场校内模拟赛。赛中做出的有3题。事实上还有一题也写了正解，但是没写特判被叉成10分。难受。（凉心出题人）

然后是学了一下基础的概率与期望。
收获有，但没有想象中那么大。