上一篇文章我們講了兩種經典的博弈模型：《【ACM博弈論】SG函式入門（1）：從巴什博奕到尼姆游戲》，這一節我們開始講解SG函式，
?? 作者：Eriktse
?? 簡介：19歲，211計算機在讀，現役ACM銀牌選手??力爭以通俗易懂的方式講解演算法！??歡迎關注我，一起交流C++/Python演算法，（優質好文持續更新中……）??
?? 閱讀原文獲得更好閱讀體驗：https://www.eriktse.com/algorithm/1111.html
在了解SG函式之前，我們需要知道博弈圖，
博弈圖
就比如Bash博弈，當n=7,m=3時，我們可以畫出如下的博弈圖，
我們可以發現，每一個點都有至多2個后繼狀態（即出點），這個是可以通過Bash推出來的，
其他博弈題大多也可以類似的推出一個這樣的圖，
SG函式
SG函式可以理解為一個用于表示博弈圖中節點狀態的一個函式，同時sg(x) = n還表示節點x的出點構成一個集合{y | 0 <= sg(y) <= n - 1}，也就是說x可以到達所有sg小于它自己的sg的點，
就比如上圖，我們規定必敗態的sg = 0，必勝態的sg != 0，于是我們可以知道sg(0) = 0，然后往回推，
sg函式轉移方程
\[sg(x) = mex({y | y \in out[x]}) \]說人話就是x的sg是其所有出點的sg構成的集合做mex運算，mex表示集合中最小的沒出現過的自然數，
代碼一般為：
int mex(set<int>& st)
{
for(int i = 0;; ++ i)
if(st.find(i) == st.end())//如果找不到i
return i;
}
于是我們可以推出上面這個博弈圖的所有點的sg函式，
注意是根據所有出點推出當前點，只有所有出點都確定了，當前點的sg才能確定，有點像建反圖然后topo，但是一般我們會直接寫一個記憶化搜索然后打表找規律，在處理帶環的圖時需要具體情況具體分析，
上面這張圖我們很容易找出規律，就是0 1 2 0 1 2....
子游戲的合并
Nim定理：全域結果等于子游戲SG的異或和，
我們昨天學過Nim博弈，他是有n堆石子，每次可以選一堆拿走若干個，那么我們可以將子游戲看做是一堆石子，每堆石子的個數是 (sg) 個，然后取走若干個石子類比為將sg轉移到更小的sg，
現在我們就可以解決一些抽象的博弈問題了，
做題一般思路
一般是三步：找出SG轉移方程，打表找規律，子游戲合并，
為什么需要打表找規律呢，因為一般題目給的資料會很大，且一般會有較強的規律性，打表找到規律就行無需證明，證明對于競賽來說太奢侈了，而且沒太大意義，
例題：AtCoder Beginner Contest 297 - Constrained Nim 2
先寫一個_sg()函式用于打表：
int _sg(int x)
{
if(x == 0)return 0;
set<int> st;
for(int i = max(0ll, x - r);i <= x - l; ++ i)st.insert(_sg(i));
for(int i = 0; ; ++ i )if(st.find(i) == st.end())return i;
}
我們隨機輸入一些資料，打個表，得到如下結果：
我們發現這個在l，r給定的情況下，sg(x)的值非常有規律，可以用下面這個運算式直接表達：
int sg(int x)
{
return x % (l + r) / l;
}
最后把所有子游戲的sg異或起來就是最終答案，
AC代碼：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 9;
int a[N], l, r;
int sgk(int x)
{
if(x == 0)return 0;
set<int> st;
for(int i = max(0ll, x - r);i <= x - l; ++ i)st.insert(sgk(i));
for(int i = 0; ; ++ i )if(st.find(i) == st.end())return i;
}
int sg(int x)
{
return x % (l + r) / l;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;cin >> n >> l >> r;
for(int i = 1;i <= n; ++ i)cin >> a[i];
// for(int i = 0;i <= 20; ++ i)
// cout << "sg(" << i << ") = " << sgk(i) << " = " << sg(i) << '\n';
int ans = 0;
for(int i = 1;i <= n; ++ i)ans ^= sg(a[i]);
if(ans)cout << "First" << '\n';
else cout << "Second" << '\n';
return 0;
}
?? 本文由eriktse原創，創作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549773.html
標籤：其他
上一篇：事實勝于雄辯,蘋果MacOs能不能玩兒機器/深度(ml/dl)學習(Python3.10/Tensorflow2)