马尔可夫【MDP】

Alice 和 Bob 正在玩一个 k 轮的石头剪刀布游戏。游戏开始时，两位玩家各有恰好 3 张牌，每张牌是石 头（R）、剪刀（S）或布（P）。每一轮游戏按照如下方式进行： 1. 双方均可看见彼此手中的全部 6 张手牌。 2. Alice 先从她的手牌中选择一张牌打出。 3. Bob 在看到 Alice 打出的牌后，选择自己的一张牌打出。 4. 根据标准规则判定胜负：石头胜剪刀，剪刀胜布，布胜石头。相同则为平局。若 Alice 获胜，她得 3 分；若平局，她得 1 分；若 Bob 获胜，她得 0 分。 5. 双方都将打出的牌丢弃，并各自独立地以等概率获得一张新的石头、剪刀或布。 Alice 希望最大化自己的期望总得分，Bob 希望最小化 Alice 的期望总得分。 给定游戏轮数 k、Alice 的初始手牌和 Bob 的初始手牌，你需要求出双方都采取最优策略时，Alice 的最 大期望总得分。 Input 输入的第一行包含一个整数 T (1 ≤ T ≤ 10 5 )，表示测试数据组数。对于每组测试数据： 第一行包含一个整数 k (1 ≤ k ≤ 10 9 )，表示游戏轮数。 第二行包含一个长度为 3 的字符串，由字符 R, S, P 组成，表示 Alice 的初始手牌。 第三行包含一个长度为 3 的字符串，由字符 R, S, P 组成，表示 Bob 的初始手牌。 Output 对于每组测试数据，输出一行包含一个实数，表示 Alice 的最大期望总得分。 如果你的答案的绝对误差或相对误差不超过 10 −6，则将被视为正确。形式化地，设你的输出为 a，标准 答案为 b，当且仅当 |a−b| max(1,|b|) ≤ 10 −6 时，你的输出会被接受。

一、核心思路

1. 状态表示（去重）

石头剪刀布中，手牌的顺序不影响结果。例如RSP、PSR、SPR是一样的。

为了去重，我们将手牌排序。

• Alice 的手牌排序后是一个非降序三元组，例如{0, 0, 2}(R, R, P)。

• 这样的组合只有 10 种（数学上叫可重复组合：(3C3+3−1​)=10）。

• 我们将这 10 种组合编号为 0~9。

• 全局状态：Alice的状态 + 10 * Bob的状态。范围 0~99。

2. 动态规划定义

dp[i][zt]表示：还剩下i轮游戏，当前状态为zt时，Alice 能获得的期望总得分。

3. 博弈过程模拟（DP转移）

对于状态zt，还剩i轮：

1. Alice 出牌：她手上有 3 张牌，她尝试出第a张（位置 0, 1, 2）。

2. Bob 出牌：他知道 Alice 出了什么。他遍历自己手上的 3 张牌，选择一张让 Alice得分最少的牌。

3. 弃牌与补牌：双方各弃一张，然后各自独立随机摸一张（R/S/P）。这里有 3×3=9种可能性。

4. 状态转移：摸牌后手牌变化，重新排序，进入新状态zt'，剩余i-1轮。

5. 得分计算：本轮得分 + 下一轮期望得分。

由于 Bob 是后手且想最小化 Alice 得分，内层取min；Alice 想最大化得分，外层取max。

4. 处理巨大的 k（线性外推）

k最大到 10e9，不可能算这么多轮。

观察发现，当 i很大时，每多一轮游戏，期望得分的增加量趋于稳定（就像物理中的匀速运动）。

• 我们计算前 1000 轮。

• 计算平均每轮增加的分值 d（通过计算第 1000 轮与第 999 轮的差值平均得到）。

• 对于 k>1000，使用公式：dp[1000][zt]+(k−1000)×d。

二、带详细注释的代码

#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double // 使用长双精度，防止精度丢失 #define endl "\n" // 计时器（用于调试性能） chrono::_V2::system_clock::time_point bg_clock,en_clock; const int N = 1e3 + 10; // DP数组第一维大小，预计算1000轮 ld dp[N][100]; // dp[i][zt]: 剩余i轮，状态为zt时的期望得分 // 存储所有10种手牌组合（排序后的） std::vector<array<ll, 3>> card; // 映射：手牌组合 -> 索引 (0~9) map<array<ll, 3>, ll> mp; ld d = 0; // 稳态下平均每轮的得分增量 /** * @brief 判断对局得分 * @param a Alice出的牌 (0:R, 1:S, 2:P) * @param b Bob出的牌 * @return Alice的得分 (0, 1, or 3) */ ll check(int a, int b) { if (a == b) { return 1; // 平局 } // (0+1)%3=1 (R beats S) // (1+1)%3=2 (S beats P) // (2+1)%3=0 (P beats R) if ((a + 1) % 3 == b) { return 3; // Alice赢 } return 0; // Alice输 } /** * @brief 初始化函数：生成状态空间并计算DP表 */ void init() { ll cnt = 0; // 1. 生成所有非降序三元组（共10种） // 例如 {0,0,0}, {0,0,1}, {0,1,1}...{2,2,2} for (int i = 0; i < 3; i++) { for (int j = i; j < 3; j++) { for (int k = j; k < 3; k++) { card.push_back({i, j, k}); mp[{i, j, k}] = cnt; cnt++; } } } // 2. 动态规划计算 // i 代表剩余的轮数 for (int i = 1; i < N; i++) { // 遍历所有100个状态 (Alice 10种 * Bob 10种) for (int zt = 0; zt < 100; zt++) { ld resa = -1e18; // Alice能获得的最大期望得分 // Alice尝试打出她手上的第a张牌 (0, 1, or 2) for (int a = 0; a < 3; a++) { ld resb = 1e18; // Bob操作后的结果（他要最小化这个值） // Bob尝试打出他手上的第b张牌 for (int b = 0; b < 3; b++) { ld sum = 0; // 枚举双方随机补充的牌 (na: new Alice, nb: new Bob) for (int na = 0; na < 3; na++) { for (int nb = 0; nb < 3; nb++) { // 解析当前状态 zt // zt % 10 是 Alice 的状态索引, zt / 10 是 Bob 的状态索引 ll za = zt % 10; ll zb = zt / 10; // 获取当前手牌（注意：这里是拷贝，因为要修改） auto cuna = card[za]; // Alice current hand auto cunb = card[zb]; // Bob current hand // Alice打出第a张牌，并用新牌na填充该位置 cuna[a] = na; // Bob打出第b张牌，并用新牌nb填充该位置 cunb[b] = nb; // 手牌重新排序（因为顺序不影响后续状态） sort(cuna.begin(), cuna.end()); sort(cunb.begin(), cunb.end()); // 累加：下一轮的期望得分 + 本轮即时得分 // dp[i-1][...]: 剩下 i-1 轮的期望 // check(...): 本轮得分 sum += dp[i - 1][mp[cuna] + 10 * mp[cunb]] + check(card[za][a], card[zb][b]); } } // Bob选择让他付出代价最小的出牌（即最小化sum） resb = min(resb, sum); } // Alice选择让她获益最大的出牌 // 注意：resb 是9种情况的总和，除以9才是期望值 resa = max(resa, resb / 9.0); } dp[i][zt] = resa; } } // 3. 计算稳态平均每轮收益 d // 假设当轮数很大时，dp[i] - dp[i-1] 趋近于常数 d for (int i = 0; i < 100; i++) { // 取第1000轮和第999轮的差值作为增量估计 d += (dp[1000][i] - dp[999][i]); } d /= 100; // 对所有100个状态取平均，得到稳定的d } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); bg_clock = chrono::high_resolution_clock::now(); cout << fixed << setprecision(15); // 设置高精度输出 int T = 1; cin >> T; init(); // 一次性预处理所有数据 while (T--) { ll k; cin >> k; array<ll, 3> ca, cb; // current Alice/Bob hand string sa, sb; cin >> sa >> sb; // 将输入的字符转换为数字 (0:R, 1:S, 2:P) for (int i = 0; i < 3; i++) { if (sa[i] == 'R') ca[i] = 0; if (sa[i] == 'S') ca[i] = 1; if (sa[i] == 'P') ca[i] = 2; if (sb[i] == 'R') cb[i] = 0; if (sb[i] == 'S') cb[i] = 1; if (sb[i] == 'P') cb[i] = 2; } // 排序，匹配状态定义 sort(ca.begin(), ca.end()); sort(cb.begin(), cb.end()); // 计算当前状态编码 ll zt = mp[ca] + 10 * mp[cb]; if (k < N) { // 如果k小于预计算的轮数，直接查表 cout << dp[k][zt] << endl; } else { // 否则，利用线性外推公式计算 // dp[1000][zt]: 前1000轮的得分 // (k-1000)*d: 剩余轮数按平均速度获得的得分 cout << dp[1000][zt] + (k - 1000) * d << endl; } } en_clock = chrono::high_resolution_clock::now(); auto duration_clock = chrono::duration_cast<chrono::microseconds>(en_clock - bg_clock); ld duration_count = duration_clock.count() * 0.001; // cerr << "Time:" << duration_count << "ms" << endl; // 输出运行时间（调试用） return 0; }

三、这段代码为什么能过？

1. 精度控制：使用了long double和setprecision(15)，远超题目要求的1e-6。

2. 状态压缩：100个状态使得DP可行。

3. 外推合理性：由于每轮结束后的随机补牌，状态转移是无记忆的（马尔可夫性）。当轮数趋于无穷，平均收益确实会收敛到一个固定值。用第1000轮的数据外推，误差极小。

4. 博弈逻辑正确：严格遵循了“Alice最大化，Bob最小化”的零和博弈规则。

原理讲解

一、马尔可夫性：一句话定义

给定一个过程，如果下一时刻的状态只取决于当前状态，跟更早的历史无关，这个过程就满足马尔可夫性。

形式化写：

P(St+1​∣St​,St−1​,…,S0​)=P(St+1​∣St​)

回到这题：

• 当前状态 = (Alice手牌, Bob手牌)

• 下一轮手牌只由"当前手牌 + 这轮谁出啥 + 随机补牌"决定

• 前 5 轮是怎么打到这个状态的，完全不影响下一轮

所以这是个马尔可夫过程。状态只有 100 个，就叫有限状态马尔可夫链。

二、马尔可夫链的几个"性格"

一条链长什么样，主要看三个属性：

不可约（Irreducible）

从任意一个状态出发，迟早能走到任意另一个状态。

这题：双方每轮都要弃牌+随机补牌，哪怕现在 Alice 全是 R、Bob 全是 P，几轮之内总能变到任何其他组合（因为补牌是独立的，总有概率摸到想要的）。

则这条链是不可约的。

非周期（Aperiodic）

不存在一个强制的"每隔几轮才回来"的规律。

这题：有可能下一轮就回到同一个手牌组合（运气好补回来一样的），也可能隔几轮才回来。周期可以是 1。

这条链是非周期的。

遍历（Ergodic）= 不可约 + 非周期 + 有限状态

三条都占 →你这条链是遍历的。

"遍历"——保证下面所有"稳定"的结论都成立。

三、平稳分布 π（最关键的结论）

遍历链有一个超级重要的定理：

存在唯一的分布 π=(π0​,π1​,…,π99​)，满足

πP=π

并且不管从哪个状态出发，玩很多轮之后，状态分布都会收敛到 π，跟起点无关。

π叫平稳分布，"平稳"的意思是：如果一开始按 π发手牌，那之后每一轮的手牌分布都永远是 π。

四、平均报酬定理（代码外推）

题每轮有个即时奖励​ ri​：在状态 i下 Alice 这轮的期望得分（Bob 已经最优应对了）。

遍历链 + 常驻奖励，有个定理叫平均报酬定理：

k→∞lim​kVk​(目i)​=ρ:=j=0∑99​πj​rj​

ρ就是长期平均每轮得分，是个常数，跟起点 i无关。

更精细一点，值函数可以拆成：

Vk​(i)=kρ+hi​+o(1)

其中 hi​叫偏差（bias），只跟起点有关，是常数。o(1)那项是残余，随 k指数衰减。

五、把代码里的变量对号入座

d += (dp[1000][i] - dp[999][i]); // 对所有i平均 d /= 100;

数学上：

dp[1000][i]−dp[999][i]=ρ+(hi​−hi​)+残留≈ρ

再对所有 i平均一把，残留更小 →用数值差分估 ρ。

然后外推：

dp[1000][zt] + (k-1000)*d // = 1000*ρ + h_zt + 残 + (k-1000)*ρ // = k*ρ + h_zt + 残

正好是 Vk​(zt)的近似。

六、这套知识在竞赛里还用在哪

马尔可夫链 + 平稳分布这套，在算法竞赛里是一类题的通解：

通用套路：

1. 建模状态，证明/确认是马尔可夫链

2. 判遍历性​ → 有平稳分布 π

3. 小 k 直接 DP，大 k：

   • 要么像本题这样数值外推（好写，够用）

   • 要么解 πP=π 得到精确 ρ，再配偏差 h（更稳，适合 k 到 1e18 的题）

七、这题如果用"正统 MDP 解法"

现在的代码 =数值迭代 + 线性外推，是"工程师解法"。

正统 MDP / 马尔可夫报酬链解法会多两步：

1. 策略迭代（或值迭代）得到最优策略下固定的转移 P∗和奖励 r∗

2. 解：

   • πP∗=π→ 平稳分布

   • ρ=πr∗

   • (I−P∗+1π)h=r∗−ρ1→ 偏差

3. 答案 = kρ+hi​−(P∗kh)i​，大 k 时最后一项丢掉

好处：ρ 和 h 都是解析精确值，不用赌"1000 轮够不够稳"。