Chlience

【题解】BZOJ 2554 Color
Problem有 $n$ 个球排成一列,每个球都有一个颜色,用 $A-Z$ 的大写字母来表示,我们每次随机选出两个...
扫描右侧二维码阅读全文
30
2019/01

【题解】BZOJ 2554 Color

Problem

有 $n$ 个球排成一列,每个球都有一个颜色,用 $A-Z$ 的大写字母来表示,我们每次随机选出两个球,使得后者染上前者的颜色

求期望操作多少次,才能使得所有球的颜色都一样?

Thought

期望操作次数 = $\sum$ 某条件下的概率 × 某条件下的(期望)步数

首先,最多会有 $26$ 种颜色,分开考虑每一种颜色作为最后颜色的期望

既然只考虑一种颜色,那么可以说所有颜色 非黑即白
我们定义选择最后的颜色为白,其他颜色为黑

那么题目转化为给出两种颜色的球,求全转化为白色的期望步数

先解决概率

一开始有 $i$ 个白色球,共 $n$ 个球
将其看作是在数轴上的随机游走

向左走的概率为 $\frac{i*(n-i)}{n(n-1)}$ ,向右走的概率为 $\frac{i*(n-i)}{n(n-1)}$ ,原地不动的概率为 $\frac{i(i-1)+(n-i)(n-i-1)}{n(n-1)}$

只考虑到达 $0$ 或者 $n$ 的概率,那么原地不动对答案没有影响,即左右走概率可均认为是 $50\%$
设 $h[x]$ 为点 $x$ 到达 $n$ 的概率,显然有 $h[0]=0,h[n]=1,h[i]=\frac{1}{2}(h[i-1]+h[i+1])$

可以看出 $h$ 就是一个等差数列,那么 $h[x]=\frac{x}{n}$

再来解决期望

设 $f[x]$ 为点 $x$ 到达 $n$ 的期望步数

怎么考虑转移呢?

走一步的期望步数为 $\frac{n(n-1)}{2i(n-i)}$ ,可以得到

$i$ 走向 $i-1$ 最后到达 $n$ 节点的期望步数为 $\frac{n(n-1)}{2i(n-i)}+ f[i-1]$
$i$ 走向 $i + 1$ 最后到达 $n$ 节点的期望步数为 $\frac{n(n-1)}{2i(n-i)}+ f[i+1]$

并且

若 $i$ 能到达 $n$ ,必然经过 $i-1$ 或者 $i+1$
所以转移时两者概率和应该为 $1$
并且两者转移概率比为能从两个点到达 $n$ 的概率比

$i$ 通过 $i-1$ 最终走向 $n$ 的可能为 $\frac{i-1}{2i}$
$i$ 通过 $i+1$ 最终走向 $n$ 的可能为 $\frac{i+1}{2i}$

那么表达式为 $f[i]=\frac{i-1}{2i}f[i-1]+\frac{i+1}{2i}f[i+1]+\frac{n(n-1)}{2i(n-i)}$

设每个点表达式为 $f[i]=c[i]+k[i]*f[i+1]$
那么有

$$ f[i]=\frac{i-1}{2i}(c[i-1]+k[i-1]f[i])+\frac{i+1}{2i}f[i+1]+\frac{n(n-1)}{2i(n-i)}\\ (2i-(i-1)k[i-1])f[i]=(i-1)c[i-1]+(i+1)f[i+1]+\frac{n(n-1)}{n-i}\\ f[i]=\frac{(i-1)c[i-1]+\frac{n(n-1)}{n-i}}{2i-(i-1)k[i-1]}+\frac{i+1}{2i-(i-1)k[i-1]}f[i+1] $$

自然的有

$$ k[i]=\frac{i+1}{2i-(i-1)k[i-1]}\\ c[i]=\frac{(i-1)c[i-1]+\frac{n(n-1)}{n-i}}{2i-(i-1)k[i-1]} $$

线性从 $1-n$ 推得 $k,c$ 最后回代算出 $f$ 即可

最终答案即选择每个颜色的期望 × 概率之和

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
char s[N];
int n, num[N];
double c[N], k[N], f[N];
int main() {
    scanf("%s", s);
    n = strlen(s);
    for(int i = 0; i < n; ++ i) ++ num[s[i] - 'A'];
    double di, dn = n, cs;
    k[1] = 1; c[1] = dn / 2;
    for(int i = 2; i <= n - 1; ++ i) {
        di = i; cs = (2 * di - (di - 1) * k[i - 1]);
        k[i] = (di + 1) / cs;
        c[i] = ((di - 1) * c[i - 1] + (dn * (dn - 1)) / (dn - di)) / cs;
    }
    for(int i = n - 1; i >= 1; -- i)
        f[i] = k[i] * f[i + 1] + c[i];
    double ans = 0;
    for(int i = 0; i < 26; ++ i)
        ans += (1.0 * num[i]) / dn * f[num[i]];
    printf("%.1lf\n", ans);
    return 0;
}
Last modification:January 30th, 2019 at 10:29 am

Leave a Comment