BZOJ2554:Color – 题解

主要思路

好难理解啊这题,让我想想。

首先,我们要把这个问题搞成一个二元问题,可以枚举最后的颜色,然后来单独计算。考虑最后的颜色为白色,其他颜色是黑色。转换成这个问题后,可以考虑进行转移。

首先,一个状态可以直接被白色颜色数量 \(x\) 所刻画。在 \(x\) 的状态下,发现有 \(x(n – x)\) 种方案是会导致颜色数量出现变动,那么变动的概率就是 \(g_x = \frac{x(n – x)}{n(n – 1)}\),变动的期望次数也就是 \(\frac{1}{g_x}\)(因为 \(x\) 是不变的)。变动时,\(x += 1\) 和 \(x -= 1\) 的概率一致(因为反过来就可以一一对应)。

那么,如果我们只考虑这个二元问题,设 \(f_x\) 为全部变成白色的期望步数,可以得到:

\[ f_x = \frac{f_{x – 1} + f_{x + 1}}{2} + g_x \]

看上去有个环,但是我们发现一个特点:边界时,当 \(x = 0, x = n\) 时,\(f_x\) 为 \(0\)。那么,来到 \(f_1 = \frac{f_2}{2} + g_1\),得 \(f_2 = 2f_1 – 2g_1\)。发现这样递推下去,每个 \(f_x\) 都可以被表示为 \(f_x = af_1 + b\) 的形式(有点类似于树上高斯消元)。当递推到 \(f_n\) 时,就可以往回推了。

然而,得到这个之后仍然不是最终答案,他只是这个二元问题的答案。要计算最后的综合概率,我们还需要加上条件,也就是钦定最终一定是某种颜色。我们只需要乘上一个 \( \frac{cnt}{n} \) 即可。

代码

// BZ2554.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4 + 200;

int n, cnt[26];
char str[MAX_N];
double ai[MAX_N], bi[MAX_N], f[MAX_N], g[MAX_N], ans;

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    for (int i = 1; i <= n; i++)
        cnt[str[i] - 'A']++;
    for (int i = 1; i <= n; i++)
        g[i] = 1.0 * i / n;
    ai[1] = 1, bi[1] = 0;
    for (int i = 1; i < n; i++)
    {
        ai[i + 1] = (ai[i] - ai[i - 1] * (i - 1) / (2 * i)) * (2 * i) / (i + 1);
        bi[i + 1] = (bi[i] - bi[i - 1] * (i - 1) / (2 * i) - double(n * (n - 1)) / double(2 * i * (n - i))) * (2 * i) / (i + 1);
    }
    f[1] = -bi[n] / ai[n];
    for (int i = 0; i < 26; i++)
        ans += g[cnt[i]] * (ai[cnt[i]] * f[1] + bi[cnt[i]]);
    printf("%.1lf\n", ans);
    return 0;
}

 

发布者

kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注