SPOJ 4060 题解

题意

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

题解

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

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

设计状态

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

于是得到状态：𝑓𝑖,0/1 表示 𝑖 个石子，第 1 或第 2 个人获胜的概率

显然 𝑓0,0 和 𝑓0,1 是两种确定结果，则概率分别为 1,0。于是考虑倒推。

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

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

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

转移方程

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

𝑓𝑖,0=𝑓𝑖−1,1⋅𝑝+𝑓𝑖,1⋅(1−𝑝)𝑓𝑖,1=𝑓𝑖−1,0⋅𝑞+𝑓𝑖,0⋅(1−𝑞)

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

𝑓𝑖,0=𝑓𝑖−1,1⋅𝑝+𝑓𝑖,1⋅(1−𝑝)𝑓𝑖,0=𝑓𝑖−1,1⋅𝑝+(𝑓𝑖−1,0⋅𝑞+𝑓𝑖,0⋅(1−𝑞))⁢(1−𝑝)𝑓𝑖,0=𝑓𝑖−1,1⋅𝑝+𝑓𝑖−1,0⋅(1−𝑝)⁢𝑞+𝑓𝑖,0⋅(1−𝑞)⁢(1−𝑝)(1−(1−𝑞)⁢(1−𝑝))⁢𝑓𝑖,0=𝑓𝑖−1,1⋅𝑝+𝑓𝑖−1,0⋅(1−𝑝)⁢𝑞𝑓𝑖,0=𝑝⋅𝑓𝑖−1,1+(1−𝑝)⁢𝑞⋅𝑓𝑖−1,01−(1−𝑞)⁢(1−𝑝)

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

𝑓𝑖,0=𝑝⋅𝑓𝑖−1,1+(1−𝑝)⁢𝑞⋅𝑓𝑖−1,01−(1−𝑞)⁢(1−𝑝)𝑓𝑖,1=𝑞⋅𝑓𝑖−1,0+(1−𝑞)⁢𝑝⋅𝑓𝑖−1,11−(1−𝑝)⁢(1−𝑞)

不希望取得：

𝑓𝑖,0=𝑝⁢(1−𝑞)⋅𝑓𝑖−1,0+(1−𝑝)⋅𝑓𝑖−1,11−𝑞⁢𝑝𝑓𝑖,1=𝑞⁢(1−𝑝)⋅𝑓𝑖−1,1+(1−𝑞)⋅𝑓𝑖−1,01−𝑞⁢𝑝

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

于是 DP 部分解决，复杂度 O⁡(𝑛)

优化

但是题目中 𝑛 的范围比较申必，𝑛 ⩽109 −1，还有多测，显然过不了。怎么办？开始考虑减少递推次数

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

易错提示

1. 要确定好自己选择的是正推还是逆推。（从这个状态推到下一个状态还是从上一个状态推到当前状态），换句话说，注意 𝑖 −1,𝑖,𝑖 +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;
    }
}