CUP 4367: Tyvj1952 Easy BZOJ
本文最后更新于 2308 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

题解

由于给定序列,$o$的概率一定是1,$x$的概率一定是0.
$?$的期望实际上是0.5
我们要求的是$E_{x^2}$,令$dp_i$代表到第i位时$E_{x^2i}$,$l_i$为到达$i$位置时的期望长度。根据上述条件,$o$时$l_i = l_{i-1} + 1$,$x$时$l_i = 0$,而$x$的时候$l_i = 0.5 \times (l_{i-1} + 1)$

根据$l$,观察$E_i – E_{i-1}$,可以发现$x^2 – (x – 1)^2 = 2x + 1$
因此$dp_i = dp_{i – 1} + 2 \times l_{i – 1} + 1$
$dp_n$为答案

AC代码

#include <iostream>
#include <iomanip>
using namespace std;
const int maxn = 3e5+6;
long double dp[maxn],l[maxn];
int main()
{
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    for(int i = 1;i<=n;++i)
    {
        if(s[i] == 'o') {
            dp[i] = dp[i - 1] + l[i - 1] * 2 + 1;
            l[i] = l[i - 1] + 1;
        }
        else if(s[i] == 'x') {
            dp[i] = dp[i - 1];
            l[i] = 0;
        }
        else {
            dp[i] = dp[i - 1] + l[i - 1] + 0.5;
            l[i] = l[i - 1] / 2 + 0.5;
        }
    }
    cout << setiosflags(ios::fixed) << setprecision(4);
    cout << dp[n] << '\n';
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇