bzoj2698 染色

本文主要是介绍bzoj2698 染色，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj2698
题目大意：
有N个格子排成一排，初始时所有格子都是黑色的。现在进行M次染色操作，每次随机选取一段长度在[S,T]之间的连续段染成白色。随机选取就是所有合法的染色方案都是等概率的。求最后被染成白色的格子个数的期望值。

题解：
期望、概率
求最后被染成白色的格子个数的期望值，其实就是每个格子被染成白色的期望的和。
因为一个格子只要有一次被染成白色了就是白的了，所以一个格子被染成白色的概率就是1-没被染过的概率。
设一次染色中总的染色方案为sum，第i个格子没被染到的方案数为num
所以有$ans=\sum_{i=1}^n1-\left(\frac{num_i}{sum}\right)^m$

要想什么正难则反，一开始在弄有多少种方案染到第i个格子，好麻烦。
但是如果是求有多少种方案没有染到第i个格子就简单很多，那么就可以在左边随便染，右边随便了，只是要求不跨过第i格而已。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;double qpow(double x,int t)
{double ret=1.0;while (t){if (t&1) ret*=x;x*=x;t>>=1;}return ret;
}
double getsum(int len,double s,double t)
//用长度为[s,t]的连续段染长度为len的区间的方案数
{double ls=(double)len;if (len<s) return 0;if (len<t) return (ls-s+2)*(ls-s+1)/2.0;return (ls*2-s-t+2)*(t-s+1)/2.0;
}
int main()
{int m,i,n;double s,t,ans=0,num;scanf("%d%d%lf%lf",&n,&m,&s,&t);num=(n*2-s-t+2)*(t-s+1)/2.0;for (i=1;i*2<=n+1;i++){double kk=(getsum(i-1,s,t)+getsum(n-i,s,t))/num;if (i*2<n+1) ans+=2-2*qpow(kk,m);else ans+=1-qpow(kk,m);}printf("%.3lf\n",ans);return 0;
}

这篇关于bzoj2698 染色的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---