进阶 - 拓扑博弈问题

Lag_longlong

2026-07-08 10:19:33

发布于：广东

16阅读

0回复

0点赞

~~又是啥诗山~~
体面：

环形博弈胜负判定

1. 问题描述

给定一个包含 $n$ 个位置的环，位置编号为 $0,1,\dots,n-1$ ，其中位置 $0$ 为终止位置。初始位置为 $1$ 到 $n-1$ 中的某个位置。

有两个行动方（编号为 $1$ 和 $2$ ）：

行动方 $1$ 有步长集合 $s_1$ 。
行动方 $2$ 有步长集合 $s_2$ 。

若当前轮到行动方 $p$ ，则必须从 $s_p$ 中选择一个步长 $x$ ，并将当前位置 $i$ 更新为 $(i+x) \bmod n$ 。若更新后位置为 $0$ ，则执行本次行动的一方获胜。

对于每个先手行动方及每个初始位置 $1,2,\dots,n-1$ ，判断先手方在双方最优策略下的结果：

必胜（Win）：存在一种策略保证获胜。
必败（Lose）：无论怎么走，对方都能获胜。
无限进行（Loop）：无法保证获胜但可以避免失败，使过程无限循环。

2. 输入格式

第一行包含整数 $T$ （测试数据组数）。

对于每组测试数据：

第一行：整数 $n$ 。
第二行：整数 $k_1$ ，随后 $k_1$ 个互不相同的整数 $s_{1,1},s_{1,2},\dots,s_{1,k_1}$ （行动方 $1$ 的步长集合）。
第三行：整数 $k_2$ ，随后 $k_2$ 个互不相同的整数 $s_{2,1},s_{2,2},\dots,s_{2,k_2}$ （行动方 $2$ 的步长集合）。

3. 输出格式

对每组测试数据输出两行：

第一行： $n-1$ 个单词，第 $i$ 个单词表示行动方 $1$ 先手且初始位置为 $i$ 时的结果。
第二行： $n-1$ 个单词，第 $i$ 个单词表示行动方 $2$ 先手且初始位置为 $i$ 时的结果。

结果只能是以下三种：

Win（必胜）
Lose（必败）
Loop（进行）

4. 数据范围

$1 \le T \le 100$
$2 \le n \le 7000$
$1 \le k_1,k_2 \le n-1$
$1 \le s_{p,j} \le n-1$ ，且集合 $s_p$ 内元素互不相同
所有测试数据满足 $\sum n \le 7000$

5. 样例

输入

输出

Loop Win Win Win
Win Win Win Win Win Win Win
Lose Win Lose Lose Win Lose Lose

样例解释

第一组数据（ $n=5$ ）：

第一行：行动方 $1$ 先手时，初始位置 $1,2,3,4$ 的结果分别为 Lose、Win、Win、Loop。
第二行：行动方 $2$ 先手时，初始位置 $1,2,3,4$ 的结果分别为 Loop、Win、Win、Win。

第二组数据（ $n=8$ ）：

第一行：行动方 $1$ 先手时，位置 $1$ 到 $7$ 的结果均为 Win。
第二行：行动方 $2$ 先手时，位置 $1$ 到 $7$ 的结果为 Lose、Win、Lose、Lose、Win、Lose、Lose。

数据范围

$1 \le T \le 100$
$2 \le n \le 7000$
$1 \le k_1, k_2 \le n-1$
$1 \le s_{p,j} \le n-1$
对于每个 $p \in \{1,2\}$ ，集合 $s_p$ 内的数互不相同
所有测试数据满足 $\sum n \le 7000$

蒟蒻的思路

1. 分析

这是一道分党派带环有向图博弈问题：

两名玩家拥有各自独立的步长集合，属于非公平博弈，无法使用公平博弈中的 SG 函数求解。
游戏在环形位置上进行，走到位置 0 的玩家直接获胜，最终存在必胜、必败、无限循环三种结果。
核心解法为反向拓扑排序（BFS 胜负传播）：从确定的终止胜负态出发，反向推导所有状态的博弈结果。

2. 大炮状态

我们通过两个二维数组维护博弈状态：

dp[player][pos]：记录当前轮到 player 行动、处于位置 pos 时的博弈结果
- 0：结果未确定，最终对应无限循环（Loop）
- 1：当前玩家必胜（Win）
- 2：当前玩家必败（Lose）
topo[player][pos]：拓扑排序的度数数组，记录当前状态未确定结果的后继状态数量
- 初始值为对应玩家的步长总数
- 当度数减为 0 时，说明所有后继都是必胜态，当前状态为必败态

3. 博弈规则

双方均采取最优策略，状态转移遵循以下公理：

必胜态：若当前状态存在至少一个后继是必败态，则当前状态为必胜态——选择该步即可让对手陷入必败局面。
必败态：若当前状态的所有后继都是必胜态，则当前状态为必败态——无论怎么走，对手都处于必胜局面。
循环态：BFS 结束后仍未被标记的状态，既无法保证一步制胜，也不会必然落入必败，双方可以通过策略让游戏无限循环。

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin >> n;
	vector<int> s[2];
	int k1,k2;
	cin >> k1;
	for(int i = 0;i < k1;i ++){
		int x;
		cin >> x;
		s[0].push_back(x);
	}
	cin >> k2;
	for(int i = 0;i < k2;i ++){
		int x;
		cin >> x;
		s[1].push_back(x);
	}
	vector<vector<int>> dp(2, vector<int>(n, 0));
	vector<vector<int>> topo(2, vector<int>(n, 0));
	for(int qpl = 0;qpl < 2;qpl ++){
		for(int pos = 1;pos < n;pos ++){
			topo[qpl][pos] = (int)s[qpl].size();
		}
	}
	queue<pair<int, int>> q;
	for(int qpl = 0;qpl < 2;qpl ++){
		for(int x : s[qpl]){
			int pos = (n - x) % n;
			if(pos == 0) continue;
			if(dp[qpl][pos] == 0){
				dp[qpl][pos] = 1;
				q.push({qpl, pos});
			}
		}
	}
	while (!q.empty()) {
		auto [qpl, pos] = q.front();
		q.pop();
		int p = 1 - qpl; 
		for (int x : s[p]) {
			int pre = (pos - x % n + n) % n;
			if(pre == 0) continue;
			if (dp[p][pre] != 0) continue;
			if (dp[qpl][pos] == 2) {
				dp[p][pre] = 1;
				q.push({p,pre});
			} else if (dp[qpl][pos] == 1) {
				if (--topo[p][pre] == 0) {
					dp[p][pre] = 2;
					q.push({p,pre});
				}
			}
		}
	}
	for(int i = 1;i < n;i ++){
		if(i > 1){
			cout << " ";
		}
		if(dp[0][i] == 1){
			cout << "Win";
		}else if(dp[0][i] == 2){
			cout<< "Lose";
		}else{
			cout << "Loop";
		}
	}
	cout << "\n";
	for(int i = 1;i < n;i ++){
		if(i > 1){
			cout << " ";
		}
		if(dp[1][i] == 1){
			cout << "Win";
		}else if(dp[1][i] == 2){
			cout<< "Lose";
		}else{
			cout << "Loop";
		}
	}
	cout << "\n";
}
int main(){
	int t;
	cin >> t;
	while(t --) solve();
	return 0;
}

本题与公平博弈问题区别
1.分党派博弈定义：不同玩家拥有独立、不相同的合法操作集合，双方行动权限不对称。
·特征：不能使用 SG 函数、Sprague-Grundy 定理失效，只能暴力拓扑 / 记忆化推导状态；
2.公平博弈定义：任意局面下，双方玩家拥有完全相同的合法移动集合，没有专属操作。
·特征：理论支撑：Sprague-Grundy 定理，所有公平博弈都能等价为尼姆堆，用 SG 函数快速计算胜负；

注意事项：
无环有向图博弈和带环有向图博弈
前者只有Win, Lose两种结果。后者则多出一个Loop（平局）
前者用正拓扑排序，后者用必须使用反向拓扑排序

有帮助，赞一个