2020-2021:teams:legal_string:lgwza:博弈论
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:博弈论 [2020/09/25 17:41] lgwza |
2020-2021:teams:legal_string:lgwza:博弈论 [2021/07/18 22:26] (当前版本) lgwza [博弈论和 SG 函数] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 博弈论和 SG 函数 ====== | + | ====== 博弈论 ====== |
| ===== 必胜点和必败点 ===== | ===== 必胜点和必败点 ===== | ||
| 行 105: | 行 105: | ||
| 这样想的话，就可以利用 **Bouton’s Theorem** 的证明来理解 $SG$ 定理了。 | 这样想的话，就可以利用 **Bouton’s Theorem** 的证明来理解 $SG$ 定理了。 | ||
| - | ## 例题 | + | ===== 例题 ===== |
| [[http://acm.hdu.edu.cn/showproblem.php?pid=1848|HDU 1848 Fibonacci again and again]] | [[http://acm.hdu.edu.cn/showproblem.php?pid=1848|HDU 1848 Fibonacci again and again]] | ||
| 行 111: | 行 111: | ||
| **题意**： | **题意**： | ||
| - | + 这是一个二人游戏，两人轮流走； | + | * 这是一个二人游戏，两人轮流走； |
| - | + 一共有 3 堆石子，数量分别是 $m,n,p$ 个； | + | * 一共有 3 堆石子，数量分别是 $m,n,p$ 个； |
| - | + 每走一步可以选择任意一堆石子，然后取走 $f$ 个； | + | * 每走一步可以选择任意一堆石子，然后取走 $f$ 个； |
| - | + $f$ 只能是斐波那契数列中的元素； | + | * $f$ 只能是斐波那契数列中的元素； |
| - | + 最先取光所有石子的人为胜者； | + | * 最先取光所有石子的人为胜者； |
| - | + 假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢； | + | * 假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢； |
| - | + $0\le n,m,p\le 1000$ | + | * $0\le n,m,p\le 1000$ |
| **题解**： | **题解**： | ||
| 行 127: | 行 127: | ||
| **代码**： | **代码**： | ||
| - | ```c++ | + | <hidden> |
| + | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| using namespace std; | using namespace std; | ||
| 行 134: | 行 135: | ||
| int sg[1005]; | int sg[1005]; | ||
| void SG(){ | void SG(){ | ||
| - | for(int i=1;i<=1000;i++){ | + | for(int i=1;i<=1000;i++){ |
| - | memset(s,0,sizeof(s)); | + | memset(s,0,sizeof(s)); |
| - | for(int j=1;j<=p;j++){ | + | for(int j=1;j<=p;j++){ |
| - | if(f[j]>i) break; | + | if(f[j]>i) break; |
| - | s[sg[i-f[j]]]=1; | + | s[sg[i-f[j]]]=1; |
| - | } | + | } |
| - | for(int j=0;j<=1000;j++){ | + | for(int j=0;j<=1000;j++){ |
| - | if(!s[j]){ | + | if(!s[j]){ |
| - | sg[i]=j; | + | sg[i]=j; |
| - | break; | + | break; |
| - | } | + | } |
| - | } | + | } |
| - | } | + | } |
| } | } | ||
| int main(){ | int main(){ | ||
| - | f[1]=1,f[2]=2; | + | f[1]=1,f[2]=2; |
| - | for(int i=3;;i++){ | + | for(int i=3;;i++){ |
| - | f[i]=f[i-1]+f[i-2]; | + | f[i]=f[i-1]+f[i-2]; |
| - | if(f[i]>1000){ | + | if(f[i]>1000){ |
| - | p=i-1; | + | p=i-1; |
| - | break; | + | break; |
| - | } | + | } |
| - | } | + | } |
| - | SG(); | + | SG(); |
| - | int m,n,p; | + | int m,n,p; |
| - | while(scanf("%d %d %d",&m,&n,&p)){ | + | while(scanf("%d %d %d",&m,&n,&p)){ |
| - | if(!m&&!n&&!p) break; | + | if(!m&&!n&&!p) break; |
| - | int ret=0; | + | int ret=0; |
| - | ret=sg[m]^sg[n]^sg[p]; | + | ret=sg[m]^sg[n]^sg[p]; |
| - | if(ret) puts("Fibo"); | + | if(ret) puts("Fibo"); |
| - | else puts("Nacci"); | + | else puts("Nacci"); |
| - | } | + | } |
| - | return 0; | + | return 0; |
| } | } | ||
| - | ``` | + | </code> |
| + | </hidden> | ||
| [[https://www.hackerrank.com/challenges/bob-and-ben/problem|HackerRank Bob and Ben]] | [[https://www.hackerrank.com/challenges/bob-and-ben/problem|HackerRank Bob and Ben]] | ||
| 行 193: | 行 196: | ||
| **代码**： | **代码**： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 217: | 行 221: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| [[http://acm.hdu.edu.cn/showproblem.php?pid=6892|HDU 6892 Lunch]] | [[http://acm.hdu.edu.cn/showproblem.php?pid=6892|HDU 6892 Lunch]] | ||
| 行 230: | 行 235: | ||
| **打表代码**： | **打表代码**： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 276: | 行 282: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| **AC 代码**： | **AC 代码**： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 324: | 行 333: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== 威佐夫博弈 ===== | ||
| + | |||
| + | ==== 简介 ==== | ||
| + | |||
| + | 两个玩家轮流行动，在两堆石子中选一堆取走任意个，或同时在两堆石子中取走相等的石子数，最后取光所有石子的人获胜。这个游戏的一个等价描述是：一个棋子放在一个大棋盘上，两人轮流移动棋子，向下，向左或向左下移动任意步，胜者是将棋移动至原点的人。 | ||
| + | |||
| + | ==== 最优策略 ==== | ||
| + | |||
| + | 游戏中的任一状态可由一对整数描述 $(n,m)(n\le m)$，游戏中的状态点分为必败点和必胜点。在必胜点的最优策略是移动至任一可到达的必败点。必败点和必胜点的分类由以下三条规则递归给出： | ||
| + | |||
| + | - $(0,0)$ 是必败点； | ||
| + | - 可一步走到必败点的点是必胜点； | ||
| + | - 如果无论怎样走都只能到达必胜点，则该点是必败点。 | ||
| + | |||
| + | 前几个必败点是：$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13)$。 | ||
| + | |||
| + | === 变形：最后一步移动的人为败者 === | ||
| + | |||
| + | $(0,1),(2,2)$ 是必败点，$(n,m)(2<n\le m)$ 是必败点当且仅当 $(n-2,m-2)$ 在正常游戏中是必败点。 | ||
| + | |||
| + | ==== 必败点的判定准则 ==== | ||
| + | |||
| + | $\phi=\dfrac{\sqrt 5+1}{2}$，第 $k$ 个必败点 $(n_k,m_k)$： $$ | ||
| + | n_k=\lfloor k\phi\rfloor=\lfloor m_k\phi\rfloor-m_k\\ | ||
| + | m_k=\lfloor k\phi^2\rfloor=\lceil n_k\phi\rceil=n_k+k | ||
| + | $$ 若给定 $(n,m)$，判断其是否为必败点，则判断 $\lfloor(m-n)\dfrac{\sqrt 5+1}{2}\rfloor==n?$，必要时使用 $\lfloor\sqrt{5(m-n)^2}\rfloor==3n-m?$ 来判定（二分答案算根号）。 | ||
| + | |||
| + | ==== 多于两堆的情况 ==== | ||
| + | |||
| + | 玩家可任选一堆石子取走任意数量，当选择多于一堆石子时，则每堆取走的石子数需相同。 | ||
| + | |||
| + | 例如，$(1,1,3)$ 和 $(1,2,3)$ 是必胜点，因为它们能到达必败点 $(0,1,2)$。$(1,1,4),(1,3,3)$ 是必败点。 | ||
2020-2021/teams/legal_string/lgwza/博弈论.1601026870.txt.gz · 最后更改: 2020/09/25 17:41 由 lgwza
