基本概念
- 先手必胜状：先手可以从这个状态走到某一个必败态。
- 先手必败态：先手走不到任何一个必败态。
- 也就是说先手必胜态，那么先手一定能采取某些操作，让后手面对必败态。如果是先手必败态，无论先手怎么操作，都无法让后手面对必败态。
基本模型
巴什博弈
假设一堆石子有n个，每次最多取m个，甲乙两个玩家轮流取石子，最后把石子取完的人获胜，保证甲乙每一步的决策都是最优的，请问给定n和m，问甲胜还是乙胜。
假设， \(n = m + 1\)，那么后手必胜。
令 \(n = (m + 1) \times r + s\)， 如果 \(s = 0\)，先手每次取 \(x\) 个，后手只要每次 \((m + 1 - x)\) 个即可，后手必胜，
如果 \(s\) 不等于 \(0\), 先手第一次取 \(s\) 个，后手每次取 \(x\) 个，先手只要每次 \((m + 1 - x)\) 个即可，先手必胜，
所以只需要讨论 \(s\) 是否为 \(0\)。
nim游戏
玩家： 2人；
道具： \(n\) 堆石子，每堆石子的数量分别为 \(x_1, x_2, …… x_n\)；
规则：
- 游戏双方轮流取石子；
- 每人每次选一堆石子，并从中取走若干颗石子（至少取 \(1\) 颗）；
- 所有石子被取完，则游戏结束；
- 如果轮到某人取时已没有石子可取，那此人算负。
假如两个游戏玩家都非常聪明，问谁胜谁负？
结论：
若\(x_1 \oplus x_2 …… \oplus x_n = 0\) 则先手必败，反之必胜。
证明：
先考虑它的子问题。
当 \(n = 1\) 时，显然是先手必胜的，可以理解为 $S_1 $ ^ \(0 = S\)。
当 \(n = 2\)时，假设一堆与另一堆相等，无论先手取什么，后手跟着取就好了，是后手必胜，可以理解为
\(s_1\) ^ \(s_2 = 0\)。
假设一堆与另一堆不相等，先手就直接在多的一堆取两堆的差值，这样又变成了上一种情况，不过现在是先手必胜，可以理解为 \(s_1\) ^ \(s_2 = s\)。
接下来将堆数，扩展到 \(n\)。
最终获胜的式子为 $ 0\( ^ 0 ^ 0 ^ 0 = 0， 而最初的状态为\)s_1$ ^ $ s_2$ ^ \(s_3\) ^ \(s_4= s\)。
…………………………
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 1e4 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int T, n;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
T = read();
while(T--)
{
n = read();
int res = 0;
for(int i = 1; i <= n; i++)
{
int x = read();
res ^= x;
}
if(res == 0) puts("No");
else puts("Yes");
}
return 0;
}
威佐夫博弈
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
结论：
当两堆石子各有 \(n\) 和 \(m\) 个，设 \(n < m\)。
那么先手必败，当且仅当 \((m - n) \times \frac {\sqrt5 + 1}2 = n\)。
好的，我并不会证明。
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int a, b;
signed main()
{
a = read(), b = read();
if(a > b) swap(a, b);
int c = b - a;
int d = (sqrt(5) + 1) / 2 * c;
if(a == d) puts("0");
else puts("1");
return 0;
}
SG函数
mex 运算
定义\(mes(s)\) 为不属于集合 \(s\) 的最小非负整数解。
SG 函数
设对于每个节点 \(x\), 设从 \(x\) 出发有 \(k\) 条有向边分别到达节点\(y_1,y_2,…,y_k\) 。
定义 \(SG(x)\) 函数为后继节点 \(y_1,y_2,…,y_k\)的SG函数值构成的集合再执行 mex运算的结果。
特别的, 整个有向图的 \(SG\) 函数被定义为有向图起点 \(s\) 的 \(SG\) 函数值, 即\(SG(G)=SG(s)\)
有向图终点的 \(SG\) 函数为 \(0\)。
结论：
先手必败, 则该局面对应 \(SG\) 函数 \(=0\)，反之必胜。
//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
int i,j;
memset(SG,0,sizeof(SG));
//因为SG[0]始终等于0，所以i从1开始
for(i = 1; i <= n; i++){
//每一次都要将上一状态 的 后继集合 重置
memset(S,0,sizeof(S));
for(j = 0; f[j] <= i && j <= N; j++)
S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记
for(j = 0;; j++) if(!S[j]){ //查询当前后继状态SG值中最小的非零值
SG[i] = j;
break;
}
}
}
挖个坑吧！！！