#期望dp#洛谷 1365 bzoj 3450 Easy

news/2024/3/4 10:55:20

题目

n n n次点击要做,成功了就是 o o o,失败了就是 x x x,分数是按 c o m b o combo combo计算的,连续 a a a c o m b o combo combo就有 a × a a\times a a×a分, c o m b o combo combo就是极大的连续 o o o。有些地方 o o o或者 x x x各有 1 2 \frac{1}{2} 21的可能性,用 ? ? ?号来表示。期望得分是多少


分析

那么首先设 f [ n ] f[n] f[n]表示到 n n n的总期望 c o m b o combo combo, g [ n ] g[n] g[n]表示到 n n n的连续一段 o o o的总长度,
那么就可以得到

  • s [ n ] = x , f [ n ] = f [ n − 1 ] , g [ n ] = 0 s[n]=x,f[n]=f[n-1],g[n]=0 s[n]=x,f[n]=f[n1],g[n]=0
  • s [ n ] = o , f [ n ] = f [ n − 1 ] + 2 × g [ n − 1 ] + 1 , g [ n ] = g [ n − 1 ] + 1 ( 也 就 是 说 , 用 之 前 的 c o m b o , 按 完 全 平 方 公 式 拆 开 , 加 上 的 就 是 2 倍 长 度 + 1 , 同 时 期 望 长 度 也 要 增 加 一 ) s[n]=o,f[n]=f[n-1]+2\times g[n-1]+1,g[n]=g[n-1]+1(也就是说,用之前的combo,按完全平方公式拆开,加上的就是2倍长度+1,同时期望长度也要增加一) s[n]=o,f[n]=f[n1]+2×g[n1]+1,g[n]=g[n1]+1(combo2+1)
  • s [ n ] = ? , 其 实 和 o 很 类 似 , 但 是 f [ n ] = f [ n − 1 ] + g [ n − 1 ] + 0.5 ( 后 面 两 项 有 一 半 的 概 率 ) , g [ n ] = ( g [ n − 1 ] + 1 ) ÷ 2 s[n]=?,其实和o很类似,但是f[n]=f[n-1]+g[n-1]+0.5(后面两项有一半的概率),g[n]=(g[n-1]+1)\div 2 s[n]=?,of[n]=f[n1]+g[n1]+0.5()g[n]=(g[n1]+1)÷2

代码

#include <cstdio>
#define rr register
using namespace std;
int n,p; double f[2],g[2];
signed main(){for (scanf("%d",&n);n;--n){rr char c=getchar(); p^=1;while (c!='o'&&c!='x'&&c!='?') c=getchar();if (c=='x') f[p]=f[p^1],g[p]=0;else if (c=='o') f[p]=f[p^1]+2*g[p^1]+1,g[p]=g[p^1]+1;else f[p]=f[p^1]+g[p^1]+0.5,g[p]=(g[p^1]+1)*0.5;}return !printf("%.4lf",f[p]);
}

http://www.ppmy.cn/news/201299.html

相关文章

ExpressBox 3450

Magma的ExpressBox 3450提供最佳的GPU和其他HPC的外围扩展现有的主机系统。为了支持全创3 x16 PCIe连接的所有设备&#xff0c;这是一个完美的伴侣eb3450工作站和服务器。高达四的双宽&#xff08;如GPU&#xff09;和一个宽的PCIe设备都支持通过扩展。 郭小姐 18874824200 0…

bzoj3450 (概率dp)

题意:有一个长度为 n 的字符串&#xff0c;由 o,x,? 三种字符组成。? 代表 o,x 各有 50% 概率。求连续 o长度的平方和的期望。 思路:由平方公式可得,那么就可以设i之前连续的o的长度期望为f[i]. 如果s[i]o那么答案贡献为f[i-1]*21,f[i]f[i-1]1. 如果s[i]xf[i]0,贡献也为0 …

POJ - 3450

题目链接&#xff1a;http://poj.org/problem?id3450 Corporate Identity Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 8549 Accepted: 2856 Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which …

BZOJ 3450 Easy

Description 某一天WJMZBMR在打osu~~~但是他太弱逼了&#xff0c;有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做&#xff0c;成功了就是o&#xff0c;失败了就是x&#xff0c;分数是按comb计算的&#xff0c;连续a个comb就有a*a分&#xff0c;comb就是极大…

hdu3450

开始看觉得是dp&#xff0c;复杂度O(n^2)会超时就没做&#xff0c;应该是用线段树或者树状数组&#xff0c;加上离散化和二分法优化。 你需要一个dp[i]数组&#xff0c;存储的是以i为结尾的个数&#xff0c;结果就是dp[]之和. 离散化的部分是用一个离散化结构体&#xff0c;最…

3450

/* KMP来做532ms */// include file #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <ctime>#include <iostream> #include <sstream> #include <fstream> #in…

BZOJ3450 Easy

原题链接&#xff1a;http://www.lydsy.com/JudgeOnline/problem.php?id3450 Easy Description 某一天WJMZBMR在打osu~~~但是他太弱逼了&#xff0c;有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做&#xff0c;成功了就是o&#xff0c;失败了就是x&…

tjut 3450

/*分析:每次寻找以a[i]结尾的子序列能有多少个,只需要寻找a[i]-d和a[i]d之之间数结尾的子序列 的全部个数,然后把a[i]直接放在那些数后面即可 找寻和更新都是用树状数组 */ #include <iostream> #include <cstdio> #include <cstdlib> #include …

POJ 3450题解

题目连接 POJ 3450 Corporate Identity 思路 先用后缀数组处理出height数组&#xff0c;然后我们二分最长公共子串的长度&#xff0c;然后再height中找大于这个长度并且不在一个字符串的个数&#xff0c;如果等于n则返回true否则返回false即可。 前期一直TLE不知道为何&…

hdu 3450

吐吐槽吧&#xff1a;本来思路完全对了&#xff0c;但是那个二分查找搞错了&#xff0c;我还以为一个就可以了&#xff0c;结果查找上界和下界分别要一个查找函数&#xff08;WA时就看了一下别人的代码&#xff0c;发现别人都是用两个查找函数的&#xff0c;模仿别人写的查找函…

poj3450

Corporate Identity http://poj.org/problem?id3450 Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Bu…

HDU 3450(树状数组)

题目链接:HDU 3450 题目大意: 求长度大于等于且相邻差值不超过d的子序列的个数. 分析: 没什么好说的水题,就是没给a的范围真的天坑. 以下是代码: #include <set> #include <map> #include <stack> #include <queue> #include <vector> #inclu…

HDU 3450 Counting Sequences(树状数组+离散化+二分+dp思想 详细解答)

题目链接&#xff1a;HDU 3450 题意&#xff1a;给出一段序列&#xff0c;让你找出一段子序列&#xff08;长度>2&#xff09;满足序列中每相邻的两个数之间的差 <d&#xff0c;求出这样的序列的个数。 思路&#xff1a;本题利用dp思想&#xff0c;dp[i] 表示 以 i 为结…

小米路由器R1C或R1CM小米R1C 原厂Bootloader和epproom

想把刷机后的小米路由器R1C刷回小米原厂,而又没备份的小伙伴可以使用下面的BootLoader和epprom&#xff08;也就是原厂分区里面的Factory分区&#xff09;都是我自己手动备份的。 分享给大家 链接&#xff1a;https://pan.baidu.com/s/1v6iUB5idgxUPqclk2KJLkA 提取码&#x…

android 7.1 小米,你的小米手机,能升Android 7.1吗?

对于诸多资深Android手机用户来说&#xff0c;官方何时放出最新Android系统更新包&#xff0c;是他们所关心的&#xff0c;小米手机用户也是如此。今天MIUI官方汇总了支持Android N的小米机型。你的手机能升Android 7.1吗&#xff1f; 根据MIUI官方的汇总数据(注&#xff1a;7月…

小米全系列机型代码查询与 制作rom分区架构图示

安卓机型的不断更新与芯片型号的不同和各自厂家研发的方向差异导致目前各品牌机型固件架构也不同。这种现象对于普通大众来说没有丝毫影响。一般只有玩家类和第三方rom制作有所关注 来几张图看下当前小米系列机型的代码和分区架构图示 做第三方rom时注意各机型的分区架构和线刷…

小米刷机教程

刷机教程 一、解锁小米手机教程 1、手机进入“设置 -> 开发者选项 -> 设备解锁状态”中绑定账号和设备 2、电脑打开申请解锁小米手机&#xff08;下载解锁工具&#xff09; 3、手机进入Bootloader模式&#xff08;重启&#xff0c;按住音量下键&#xff09; 4、通过…

小米pro15拆机_实战小米笔记本PRO 15.6寸拆解 加装M.2海力士固态硬盘

你是AMD Yes党?还是intel和NVIDIA的忠实簇拥呢?最新一届#装机大师赛#开始啦!本次装机阵营赛分为3A红组、intel NVIDIA蓝绿组、混搭组还有ITX组,实体or虚拟装机都能参与,可使用值得买定制化DIY装机工具在文中展现配置单!每个小组均有精美礼品,优秀文章还可角逐装机大师终…

qq空间把android改成iphone,qq空间改iPhone6 Plus方法 qq空间改手机型号教程

苹果今年发布了两部iPhone&#xff0c;分别是iPhone6和iPhone6 Plus&#xff0c;对于土豪们来说&#xff0c;iPhone6 Plus当然是换机的优先选择&#xff0c;相信随着身边使用iPhone6 Plus的朋友越来越多&#xff0c;势必将在QQ空间掀起一股“您的手机来自 iPhone6 Plus”标识热…

小米10系列详细参数对比,小米10 青春版\10\10Pro\10至尊纪念版

小米10系列对比 一、参数对比 配置/型号小米10 青春版小米10小米10 Pro小米10 至尊纪念版售价6642099元\\\61282299元\\\81282499元3999元\5299元82562799元4299元4999元5599元12256\4699元5499元5999元12512\\5999元\16512\\\6999元内存规格 LPDDR4X LPDDR5存储规格UFS 2.1U…
最新文章