发布于 ,更新于 

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;
}
}