题意:有n张标有“C”或“F”的卡片。

1、随机取前k张(1<=k<=n)

2、若这k张的第一张为“C”,则不翻转,否则,全部翻转这k张。

3、然后处理剩下的n-k张

4、重复步骤1~3直至处理完所有卡片。

求处理后卡片W的个数期望。

分析:期望dp从后往前推。

1、对于最后一张卡片,无论为C还是W,最后的结果都是W个数为0,因此dp[len] = 0.

2、对于卡片i,k有(len - i + 1)种选择

若卡片i为C,则前k张卡片是不反转的,预处理前缀和。

k = 1, 1 / (len - i + 1) * (0 + dp[i + 1])

k = 2, 1 / (len - i + 1) * (前两张卡片中W的个数 + dp[i + 2])

.......

k = len - i + 1, 1 / (len - i + 1) * (前len - i + 1张卡片中W的个数)

若卡片i为W,同理也处理处前缀和。

提取公因数1 / (len - i + 1)后,后面的式子合并dp[i + 1] + dp[i + 2] +...+ dp[len]可以边算边处理出后缀和sumsuf[i]。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1000000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
char s[MAXN];
LL a1[MAXN], a2[MAXN];
LL sum1[MAXN], sum2[MAXN];
double sumsuf[MAXN], dp[MAXN];
int main(){
freopen("foreign.in", "r", stdin);
freopen("foreign.out", "w", stdout);
scanf("%s", s + 1);
int len = strlen(s + 1);
for(int i = 1; i <= len; ++i){
if(s[i] == 'W') a1[i] = a1[i - 1] + 1;
else a1[i] = a1[i - 1];
}
for(int i = 1; i <= len; ++i){
if(s[i] == 'C') a2[i] = a2[i - 1] + 1;
else a2[i] = a2[i - 1];
}
for(int i = 1; i <= len; ++i){
sum1[i] = sum1[i - 1] + a1[i];
sum2[i] = sum2[i - 1] + a2[i];
}
dp[len] = 0;
sumsuf[len] = 0;
for(int i = len - 1; i >= 1; --i){
LL tmp;
if(s[i] == 'C'){
tmp = sum1[len] - sum1[i - 1] - a1[i] * (len - i + 1);
}
else{
tmp = sum2[len] - sum2[i - 1] - a2[i] * (len - i + 1);
}
dp[i] = (1 / (double)(len - i + 1)) * (sumsuf[i + 1] + tmp);
sumsuf[i] = sumsuf[i + 1] + dp[i];
}
printf("%.12lf\n", dp[1]);
return 0;
}

  

最新文章

  1. js图片延迟加载
  2. 课堂作业二 PAT1025 反转链表
  3. Win+R命令大全
  4. tslib1.4与Qt4.8.6的交叉编译与移植
  5. Java--&gt;Json解析网页数据
  6. java 动态创建数据库和动态连接数据库
  7. 【BZOJ】3038: 上帝造题的七分钟2(线段树+暴力)
  8. php 命名空间(要求php5.3以上)
  9. codeforces Codeforces 650A Watchmen
  10. Array.prototype.map()
  11. 【转】C/C++ 内存对齐
  12. [jQuery编程挑战]003 克隆一个页面元素及其相关事件
  13. c#按键Up和Down对Textbox的内容加1减1
  14. hdu 5036 Explosion(概率期望+bitset)
  15. linux-telnet服务配置
  16. Linux上bash的部分基础特性:
  17. 关于HTTP协议头域详解
  18. JSP自定义方法库
  19. [Python学习笔记] turtle库的基本使用
  20. Elastic 开发篇 javaAPI(4)

热门文章

  1. centos6.9下 svn 1.7.10版本 编译安装
  2. 【PAT甲级】1019 General Palindromic Number (20 分)
  3. 【转】ERP系统测试方法
  4. redhat 7.6 常用命令
  5. 浏览器输入URL后HTTP请求返回的完整过程
  6. vue中 el [$el] 的理解
  7. 本周总结(19年暑假)—— Part3
  8. postgresql shell脚本传递参数并执行sql脚本并
  9. kafka在zookeeper默认使用/为根目录,将/更换为/kafka
  10. 一、什么是Velocity及简单示例