SPOJ 4060 题解

题意

给定一定数量的石子，两个人抛硬币，抛到正面则拿走一颗石子，否则什么都不做。拿走最后一颗石子的人胜利。
已知石子数量，假设双方都采用最优方案，两个人分别抛到自己想要的那一面的概率分别为 \(0.5 \leqslant q,p < 1\) 这不唯物，求先手的获胜概率。

题解

要点：对概率的熟悉程度，对 DP 的熟练程度，奇怪的缩小数据范围的方法

首先考虑直接硬算，发现希望掷得的面会变化，没法直接算，考虑 DP。

设计状态

• 表示出当前到达第几颗石子
• 表示出当前谁拿石子

于是得到状态：\(f_{i,0/1}\) 表示 \(i\) 个石子，第 \(1\) 或第 \(2\) 个人获胜的概率

显然 \(f_{0,0}\) 和 \(f_{0,1}\) 是两种确定结果，则概率分别为 \(1,0\)。于是考虑倒推。

看概率的取值，说明只要我们希望抛到一个面，抛到这个面概率就会更大。
由于很容易判断出当前状态下应该希望取得/不取得石子（通过前一个状态的概率大小），所以不用单独表示出希望取得/不取得石子。

状态是否可行？根据 lzp 大佬的教诲，我们需要判断该状态：

• 是否能表示单独状态：显然可以，上面解释过了。
• 是否可递推：直觉是可以递推，但是需要列柿子看一下

转移方程

开始写柿子：
希望取得这颗石子（正面）：

\[ \begin{aligned} f_{i,0} &= f_{i-1,1}\cdot p + f_{i,1} \cdot (1-p) \newline f_{i,1} &= f_{i-1,0}\cdot q + f_{i,0} \cdot (1-q) \end {aligned} \]

发现这玩意没法递推，但是发现可以运用初中二元一次方程的思路，代入消元。

\[ \begin{aligned} f_{i,0} &= f_{i-1,1}\cdot p + f_{i,1} \cdot (1-p) \newline f_{i,0} &= f_{i-1,1} \cdot p + (f_{i-1,0}\cdot q + f_{i,0} \cdot (1-q))(1-p) \newline f_{i,0} &= f_{i-1,1} \cdot p + f_{i-1,0}\cdot (1-p)q + f_{i,0} \cdot (1-q)(1-p) \newline (1-(1-q)(1-p))f_{i,0} &= f_{i-1,1} \cdot p + f_{i-1,0}\cdot (1-p)q \newline f_{i,0} &= \frac {p\cdot f_{i-1,1} + (1-p)q\cdot f_{i-1,0}}{1-(1-q)(1-p)} \end{aligned} \]

发现这玩意就可以递推了，再依照同样的方式能够列出 \(f_{i,1}\) 的转移方程和不希望取得这颗石子的两个转移方程。不再赘述过程（基本上和上面完全一样），给出柿子 希望取得：

\[ \begin{aligned} f_{i,0} &= \frac {p\cdot f_{i-1,1} + (1-p)q\cdot f_{i-1,0}}{1-(1-q)(1-p)} \newline f_{i,1} &= \frac {q\cdot f_{i-1,0} + (1-q)p\cdot f_{i-1,1}}{1-(1-p)(1-q)} \end {aligned} \]

不希望取得：

\[ \begin{aligned} f_{i,0} = \frac{p(1-q)\cdot f_{i-1,0} + (1-p)\cdot f_{i-1,1}}{1-qp} \newline f_{i,1} = \frac{q(1-p)\cdot f_{i-1,1} + (1-q)\cdot f_{i-1,0}}{1-qp} \end{aligned} \]

对比一下容易发现：希望取得与不希望取得的转移方程中，区别仅仅是 \(p,(1-p)\) 和 \(q,(1-q)\)。于是，当取石子比不取石子优的时候，把 \(p,q\) 把 \(1\) 减一下就行了。

于是 DP 部分解决，复杂度 \(\operatorname{O}(n)\)

优化

但是题目中 \(n\) 的范围比较申必，\(n \leqslant 10^9-1\)，还有多测，显然过不了。怎么办？开始考虑减少递推次数

• “自身简化专业玄 —— lzp” 矩阵快速幂之类的优化...不好评价，转移方程貌似有点巨大；单调队列或者斜率？已经线性了，这种方法貌似没啥用。
• 概率还可以考虑是否会出现趋于稳定的情况。可以打表测一下（或者提交试一下），试一下发现确实可以
  \(n = \min(n,100)\) 即可。

易错提示

1. 要确定好自己选择的是正推还是逆推。（从这个状态推到下一个状态还是从上一个状态推到当前状态），换句话说，注意 \(i-1,i,i+1\) 的区别。
2. 要确定好自己递推使用的是哪一个柿子，不要写反（谁因为这个调了半天我不说

示例代码

不得不说 rust 某些方面比 C++ 严格，读入也比较麻烦，但是从另一方面来说非常人性化...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

use std::io;

fn solution() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut lis = input.trim().split(' ');

    let mut n: usize = lis.next().unwrap().parse().unwrap();
    let p: f64 = lis.next().unwrap().parse().unwrap();
    let q: f64 = lis.next().unwrap().parse().unwrap();

    let mut f: [Vec<f64>; 2] = [Vec::new(), Vec::new()];

    if n > 100 {
        // 推到第 100 个石子就够了
        n = 100;
    }

    f[0].push(0.0);
    f[1].push(1.0);

    for i in 1..=n {
        let mut pnow = p;
        let mut qnow = q;
        if f[1][i - 1] > f[0][i - 1] {
            // 如果上一颗石子不应当让自己取
            // 这里取不取等号无所谓
            pnow = 1.0 - p;
            qnow = 1.0 - q;
        }
        f[0].push(
            (pnow * (1.0 - qnow) * f[0][i - 1] + (1.0 - pnow) * f[1][i - 1]) / (1.0 - pnow * qnow),
        );
        f[1].push(
            (qnow * (1.0 - pnow) * f[1][i - 1] + (1.0 - qnow) * f[0][i - 1]) / (1.0 - pnow * qnow),
        );
    }

    println!("{}", f[0][n]);
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut s = input.trim().split(' ');
    let mut t: i32 = s.next().unwrap().parse().unwrap();
    while t != 0 {
        solution();
        t -= 1;
    }
}