lp5104 红包发红包

在\(\lbrack 0,1 \rbrack \)中任取一个数,期望是\(\frac{1}{2}\)
同理,在\(\lbrack 0,w \rbrack \)中任取一个数,期望是\(\frac{w}{2}\)
故而,取\(k\)个数的期望是\(\frac{w}{2^k}\)
费马小定理加快速幂即可。

#include<iostream>
#include<cstdio>
const long long MOD = 1000000007;

inline long long pw(int A,long long X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}

inline long long inv(int X){
	return pw(X,MOD-2);
}

long long w,n,k;

void init(){
	scanf("%lld%lld%lld",&w,&n,&k);
	printf("%lld\n",(w*(inv(pw(2,k))))%MOD);
}

int main(){
	init();
	return 0;
}

lp1850 NOIP2016 换教室

一道优\(d\acute{u}\)秀\(li\acute{u}\)的期望DP。
简述题意:
原有一个包括\(n\)个节点的路径,你可以用\(m\)次操作,每一次操作可以把第\(i\)个节点从\(c_{i}\)换到\(b_{i}\)。
对于每一次操作,有\(p_{i}\)的概率成功。求最优决策下路径长度的期望。

首先考虑到是稠密图,故考虑用邻接矩阵来处理。不过需要注意读入时应当取较小值,以及每个点到其本身的距离为\(0\)
首先用\(Floyd\)预处理出所有点之间的距离。然后我们定义\(f_{i,j,k}\)表示,当前在决定第\(i\)个节点,已经使用了\(j\)次机会,当前选择为\(k\)时的期望路径长度。
那么我们考虑转移。
对于每一个状态,我们有两种选择:使用机会或者不使用机会。故而我们尝试推理状态转移方程:
首先,如果不使用机会的话,有两种情况可以转移过来,分别是,上一次使用了机会,或者上一次没有使用机会,故:
$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
如果在这个点使用机会且成功的话,则有:
$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
然后,只需要走到终点即可,因此:
$$ Ans=Min(f_{N,i,j})\ (i\in [0,M],j\in [0,1])$$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int mp[305][305],N,M,V,E;
int c[2005],d[2005];
double p[2005],f[2005][2005][2];
void init(){
    memset(mp,0x3f,sizeof(mp));
    scanf("%d%d%d%d",&N,&M,&V,&E);
    for(int i=1;i<=N;++i){
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%lf",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=E;++i){
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);
    }
    for(int i=1;i<=V;++i){
        mp[i][i]=0;
    }
    for(int k=1;k<=V;++k){
        for(int i=1;i<=V;++i){
            for(int j=1;j<=V;++j){
                mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); 
            }
        }
    }
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<=1;++k){
                f[i][j][k]=1000007;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=N;++i){
        for(int j=0;j<=M;++j){
            f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));
            if(!j){
                continue;
            }
            f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));
        }
    }
    double ans=1000007;
    for(int i=0;i<=M;++i){
        for(int j=0;j<2;++j){
            ans=Min(ans,f[N][i][j]);
        }
    }
    /*
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<2;++k){
                printf("%.2lf ",f[i][j][k]);
            }
            printf("|");
        }
        puts("");
    }
    */
    printf("%.2lf",ans);
}
int main(){
    init();
    return 0;
}

 

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;
}