灵魂画师(noip模拟题)

Posted by yjjr's blog on February 6, 2018

标签:数学期望,DP

题目描述

       虽然不知道为什么,但是你一直想用一种神奇的方式完成一幅画作。

       你把n张画纸铺成一排,并将它们从1到n编号。你一共有c种颜色可用,这些颜色可以用0到c-1来编号。初始时,所有画纸的颜色都为1。你一共想进行k次作画,第i次作画时,你会等概率随机地选闭区间[Li,Ri]内的画纸的一个子集(可以为空),再随机挑一种颜色bi,并把挑出来的画纸都涂上该颜色。原有颜色a的画纸在涂上颜色b后,颜色会变成(a*b) mod c,这是这个世界的规律。

       因为你将颜色用数字来命名了,因此你可以求出在k次作画结束后,每张画纸上的颜色对应的数字相加之和的期望。现在请你编程求一下这个值。

 

       以防万一你不知道什么是期望:如果一个量X,它有p1的概率值为v1,有p2的概率值为v2……pn的概率值为vn,则X的期望值等于。

 

输入格式

       第一行包含3个正整数n, c, k,意义如题所述。

       接下来k行,每行包含两个数Li, Ri,表示你每次操作会从哪个区间内随机地选画纸。

 

输出格式

       一行,一个小数,表示答案,四舍五入精确到小数点后3位。

 

样例输入1

2 3 1

1 2

 

样例输出1

2.000

 

样例解释

       一共有4种选择子集的可能,每种的概率都是。

       选空集:画纸不会发生改变,颜色和是1+1=2;

       选{1}:画纸2不会发生改变。选颜色有3种可能,使得画纸1最终分别变成颜色0、1、2,概率都是,颜色和的期望是;

       选{2}:与选1对称,颜色和的期望也是2;

       选{1,2}:选颜色有3种可能,使得两张画纸最终都变成颜色0、1、2,概率都是,颜色和的期望是;

       综上,4种选择子集的方案的颜色和的期望为。

 

样例输入2

3 3 3

1 2

2 3

1 3

 

样例输出2

2.639

 

数据范围

测试点编号

n

k

c

其它

1

≤10

=1

≤10

 

2

 

3

≤100

≤100

 

4

 

5

=1

≤100

Li=Ri

6

≤100

7

 

8

 

9

 

10

 

对所有数据,1≤Li≤Ri ≤n。

 

分析:

第一眼看到题,样例2手玩不出来gg

貌似只会打20分的暴力,毕竟没怎么做过期望题

其实是很简单的一个有关期望的性质

和的期望=期望的和   就是期望的可加性啦

正解做法和50分部份分做法类似

DP

F[i][j]表示涂i次后显示颜色j的概率

转移:f[i+1][j*t%c]+=f[i][j]/c

G[i][j]表示i次被包含在区间里,j次被选中的概率(就是C(i,j)/2i

G[i][j]=(g[i-1][j]+g[i-1][j-1])/2

Ans=

对于满分的做法,我们用Cnt数组记录下每个画纸被覆盖的次数

用和之前一样的做法去计算

 

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define  ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define eps 1e-7
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=106;
int k,n,cnt[maxn],mx,c;
double ans,g[maxn][maxn],f[maxn][maxn];
int main()
{
	freopen("paint.in","r",stdin);
	freopen("paint.out","w",stdout);
	g[0][0]=1;
	rep(i,0,100)
	    rep(j,0,i){g[i+1][j]+=g[i][j]/2.0;g[i+1][j+1]+=g[i][j]/2.0;}
	n=read(),c=read(),k=read();
	mem(cnt,0);mx=0;
	rep(i,1,k){
		int x=read(),y=read();
		rep(j,x,y){
			cnt[j]++;
			mx=max(mx,cnt[j]);
		}
	}
	mem(f,0);
	f[0][1]=1;
	rep(i,0,mx-1)
	    rep(j,0,c-1)
	        if(f[i][j]>eps)
				rep(r,0,c-1)f[i+1][j*r%c]+=f[i][j]/c;
	ans=0;
	rep(i,1,n)
		rep(j,0,cnt[i])
			rep(r,0,c-1)ans+=g[cnt[i]][j]*f[j][r]*r;
	printf("%.3lf\n",ans);
	return 0;
}




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr