UVa 11061 Playing War

题目描述

“$\text{War}$” 是一款经典的棋盘游戏，在巴西相当有名。游戏中，玩家们共同统治整个世界，每位玩家控制一个或多个领地。每位玩家可能有不同的目标，但通常领地越多越好，所有人都为此而战。

每个领地被其拥有者的若干 “军队” 占领。每回合，玩家可以用一个领地上的军队攻击相邻领地并试图征服它。攻击时，进攻方至少要在原领地留下 $1$ 个军队，因此若进攻方有 $a$ 个军队，最多只能用 $a-1$ 个去攻击，且单次战斗中双方最多只能使用 $3$ 个军队。也就是说，无论进攻方领地有多少军队（$\ge 4$），每次攻击最多使用 $3$ 个；防守方同样最多使用 $3$ 个。

战斗通过投掷普通 $6$ 面骰子进行。进攻方和防守方各自投掷与所用军队数相等的骰子（最多 $3$ 个）。然后按以下规则决定双方损失的军队数：

玩家可以在同一回合内对一个敌方领地发起连续多次攻击，每次使用剩余的军队并遵守每次最多 $3$ 个的限制。通常玩家会尽量多用军队，但也有一些 “神经质” 的玩家，一旦开始攻击某个敌方领地，就会一直攻击下去，直到征服该领地（防守方军队为 $0$） 或 无法继续攻击（进攻方只剩 $1$ 个军队） 为止。

$\text{Elbdson}$ 就是这样的神经质玩家，同时他也是个优秀的程序员。因此，当他邀请朋友玩 $\text{War}$ 时，第一件事就是写程序计算自己进攻时的优势。换句话说，$\text{Elbdson}$ 想知道：为了攻击一个拥有 $X$ 个军队的敌方领地，并且有超过 $50\%$ 的概率征服它，他至少需要在该领地拥有多少个军队。现在请你完成同样的计算。

输入格式

输入包含多个测试集，每个测试集为一行一个整数 $X$（$1\le X\le 1000$），表示敌方领地的军队数。输入以 $X=0$ 结束，该行不处理。

输出格式

对于每个测试集，输出一行一个整数，即 $\text{Elbdson}$ 需要的最少初始军队数，使得征服概率大于 $0.5$。

样例

输入

1
2
3
0

输出

3
4
6

题目分析

本题是一个概率计算问题，核心在于模拟随机战斗过程，并求出给定防守方军队数 $X$ 时，最小的进攻方初始军队数 $N$，使得从状态 $(N,X)$ 出发，最终征服（防守方军队降为 $0$）的概率大于 $0.5$。

战斗过程是马尔可夫链，状态由 $(a,d)$ 表示，其中 $a$ 为进攻方军队数，$d$ 为防守方军队数，且 $d>0$。每轮战斗：

• 进攻方可使用的骰子数 $A=\min (3,a-1)$（必须保留 $1$ 个在原领地）；
• 防守方可使用的骰子数 $D=\min (3,d)$；
• 实际比较次数 $m=\min (A,D)$。

投掷 $A$ 个进攻骰子和 $D$ 个防守骰子后，根据比较结果，统计进攻方获胜的次数 $k$（$0\le k\le m$）。则：

• 防守方损失 $k$ 个军队；
• 进攻方损失 $m-k$ 个军队（因为每一对比较必有一方损失）。

新的状态为 $(a-(m-k),d-k)$。若 $d-k=0$，则进攻方获胜；若 $a-(m-k)\le 1$ 且 $d-k>0$，则进攻方失败（无法继续攻击）。

由于骰子结果独立且等概率，我们可以预先计算出对于每对 $(A,D)$，进攻方获胜次数 $k$ 的概率分布 $\text{prob}[A][D][k]$。然后使用动态规划从状态 $(a,d)$ 转移到更小的状态（因为 $a$ 和 $d$ 都是非增的，且至少有一个严格减少），最终求出获胜概率。

直接对每个测试用例独立 $\text{DP}$，最大 $X$ 为 $1000$，而答案 $N$ 可能达到数千，重复计算会超时。因此我们采用一次性预处理所有 $X$ 的策略，按进攻方军队数 $a$ 递增的顺序，滚动数组计算所有 $d$ 的获胜概率，并在过程中记录每个 $X$ 首次满足概率 $>0.5$ 时的 $a$ 值。

解题思路

1. 预计算转移概率

对于所有可能的 $A,D\in \{1,2,3\}$，枚举所有骰子结果组合。进攻方有 $6^A$ 种结果，防守方有 $6^D$ 种结果，总共最多 $6^3\times 6^3=46656$ 种组合。对每种组合，分别排序后比较前 $m=\min (A,D)$ 对，统计进攻方胜利的次数 $k$。最后将频数除以总数，得到概率 $\text{prob}[A][D][k]$。

这一步只需做一次，可以在程序开始时完成。

2. 动态规划状态定义

令 $\text{dp}[a][d]$ 表示当进攻方有 $a$ 个军队、防守方有 $d$ 个军队时，进攻方最终征服的概率。边界条件：

• 若 $d=0$，则已征服，概率为 $1$（但我们的状态始终保证 $d>0$，转移时处理）；
• 若 $a\le 1$ 且 $d>0$，则无法攻击，概率为 $0$。

对于 $a\ge 2,d\ge 1$，转移公式为：

$$\text{dp}[a][d]=\sum _{k=0}^m\text{prob}[A][D][k]\times \{\begin{array}{ll}1,& d-k=0,\\ 0,& a-(m-k)\le 1\text{ 且 }d-k>0,\\ \text{dp}[a-(m-k)][d-k],& \text{otherwise}.\end{array}$$

其中 $A=\min (3,a-1)$，$D=\min (3,d)$，$m=\min (A,D)$。

3. 计算顺序与滚动数组

注意到转移后的状态 $(a^{\prime },d^{\prime })$ 满足 $a^{\prime }\le a$，$d^{\prime }\le d$，且至少一个严格减小（因为 $k$ 和 $m-k$ 不能同时为 $0$）。因此，我们可以按 $a$ 从小到大递增，对于每个 $a$，再按 $d$ 从小到大递增计算，这样所有依赖的状态 $a^{\prime }<a$ 或 $a^{\prime }=a$ 且 $d^{\prime }<d$ 都已经计算完毕。

因为 $a$ 可能达到数千，但转移只依赖最近 $4$ 个 $a$ 值（因为 $a-(m-k)$ 与 $a$ 的差最大为 $m\le 3$），所以可以用滚动数组 $\text{dp}[4][d]$，其中第一维为 $a\mathrm{mod}4$。

4. 一次性预处理所有答案

读入所有查询的 $X$，记录最大值 $\text{maxX}$。然后从 $a=2$ 开始递增，对每个 $a$ 计算所有 $d\in [1,\text{maxX}]$ 的 $\text{dp}[a\mathrm{mod}4][d]$。每计算完一个 $a$，检查所有尚未找到答案的查询 $X$，若 $\text{dp}[a\mathrm{mod}4][X]>0.5$，则记录答案 $a$，并标记该查询已解决。当所有查询都找到答案时，停止循环。

5. 正确性说明

• 预计算的概率分布准确反映了单轮战斗的随机性。
• 动态规划转移方程完整描述了所有可能的战斗结果及其后续概率。
• 因为状态空间随着 $a$ 和 $d$ 单调减小，循环顺序正确，滚动数组保留了必要的历史信息。
• 当 $a$ 增大时，获胜概率单调不减（因为更多军队总是更有利），因此第一个满足条件的 $a$ 就是最小值。

6. 复杂度分析

• 预计算：枚举 $3\times 3$ 对 $(A,D)$，每对枚举 $6^A\times 6^D\le 46656$ 种组合，排序和比较开销很小，总时间常数。
• 动态规划：假设最大所需 $a$ 为 $M$（实测不超过 $10000$），则状态数为 $M\times \text{maxX}$，每个状态转移最多 $4$ 种 $k$（因为 $m\le 3$），总时间复杂度 $O(M\cdot \text{maxX}\cdot 4)$，其中 $M$ 约为 $20000$ 以内，$\text{maxX}\le 1000$，完全可行。
• 空间复杂度：滚动数组 $O(4\cdot \text{maxX})$。

代码实现

// Playing War
// UVa ID: 11061
// Verdict: Accepted
// Submission Date: 2026-06-21
// UVa Run Time: 0.640s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

double prob[4][4][4]; // prob[A][D][k]：A个攻击骰子、D个防御骰子时，攻击方胜k次的概率

// 生成所有长度为num的骰子点数（1~6）组合
void genRolls(int num, vector<int>& cur, vector<vector<int>>& all) {
if ((int)cur.size() == num) {
all.push_back(cur);
return;
}
for (int i = 1; i <= 6; ++i) {
cur.push_back(i);
genRolls(num, cur, all);
cur.pop_back();
}
}

// 预计算所有(A,D)组合下的概率分布
void precompute() {
for (int A = 1; A <= 3; ++A) {
for (int D = 1; D <= 3; ++D) {
vector<vector<int>> att, def;
vector<int> cur;
genRolls(A, cur, att);
genRolls(D, cur, def);
int total = (int)att.size() * (int)def.size();
int m = min(A, D);
vector<int> cnt(m + 1, 0);
for (auto& a : att) {
sort(a.begin(), a.end(), greater<int>());
for (auto& d : def) {
sort(d.begin(), d.end(), greater<int>());
int win = 0;
for (int i = 0; i < m; ++i)
if (a[i] > d[i]) ++win;
++cnt[win];
}
}
for (int k = 0; k <= m; ++k)
prob[A][D][k] = (double)cnt[k] / total;
}
}
}

int main() {
precompute();

vector<int> queries;
int x;
while (cin >> x && x != 0)
queries.push_back(x);
if (queries.empty()) return 0;

int maxX = *max_element(queries.begin(), queries.end());
vector<int> ans(maxX + 1, 0);
vector<bool> found(maxX + 1, false);

// dp[4][maxX+1] 滚动数组，dp[i][d] 表示进攻方军队数为 i（取模4）时的概率
vector<vector<double>> dp(4, vector<double>(maxX + 1, 0.0));

int foundCount = 0;
for (int a = 2; ; ++a) {
int A = min(3, a – 1);
int curIdx = a % 4;

for (int d = 1; d <= maxX; ++d) {
int D = min(3, d);
int m = min(A, D);
double sum = 0.0;
for (int k = 0; k <= m; ++k) {
int la = m – k; // 进攻方损失
int ld = k; // 防守方损失
double p = prob[A][D][k];
if (d – ld == 0) sum += p;
else if (a – la <= 1) sum += 0.0;
else sum += p * dp[(a – la) % 4][d – ld];
}
dp[curIdx][d] = sum;
}

// 检查是否有查询首次满足条件
for (int X : queries) {
if (!found[X] && dp[curIdx][X] > 0.5 + 1e-9) {
found[X] = true;
ans[X] = a;
++foundCount;
}
}
if (foundCount == (int)queries.size()) break;
// 安全上限（理论上足够，防止意外）
if (a > 100000) break;
}

for (int X : queries)
cout << ans[X] << '\\n';

return 0;
}

总结

本题的核心是概率动态规划，结合了预计算转移概率和滚动数组优化。关键点包括：

• 准确建模战斗规则，注意单次战斗最多使用 $3$ 个骰子的限制。
• 利用马尔可夫链的无后效性，按状态大小递增顺序递推。
• 一次性预处理所有查询，避免重复计算，是应对多组数据的高效策略。
• 浮点数比较时需设置微小精度误差容忍，避免边界判断失误。

此类问题常见于模拟类概率计算，掌握状态转移的构建和计算顺序优化是解题的关键。