手机怎么使用代理ip上网_太原网站建设方案托管_拼多多关键词排名在哪里看_西安seo工作室

sg函数(全称Sparague—Grundy)

它是博弈论和组合游戏理论中的一个重要概念，用于分析组合游戏的输赢情况，特别是那些具有明确终止条件和有限状态空间的游戏。

定义

对于一个给定的组合游戏，其sg函数G(n)是一个非负整数，用于表示游戏位置n的"输赢状态"；两个游戏位置的sg函数值相同，意味着从这两个位置开始，对于任何一个玩家来说，都存在相同的赢或输的策略。

性质

终止位置：

终止位置的sg函数值通常定义为0(表示当前玩家无法移动，即输掉游戏，但这也取决于具体的游戏规则和胜负判断)

非终止位置：

对于非终止位置n，其sg函数数值G(n)是后续所有可能位置m的sg函数值集合中不包含的最小非负整数(即mex函数)

周期性：

在某些游戏中，sg函数值可能呈现出周期性，这意味着当游戏状态达到某个特定大小时，其输赢情况会开始重复

计算方法

确定终止位置

首先确定所有可能的终止位置，并给它们赋予适当的sg值(通常为0)

逆向递归

从终止位置开始，逆向归纳计算每一个非终止位置的sg值。涉及递归地考虑所有可能的移动和后续位置

应用mex函数

对于每个非终止位置，使用mex函数来找到其sg值。mex函数返回的是不包含在给定集合中的最小非负整数。

示例

给一个简单的Nim游戏的变体：其中有一堆n个石子，两个玩家轮流取，每次可以取1～k个石子，取走最后一个石子的人获胜。这个游戏的sg函数计算：
1、对于n=0，这是一个失败的问题，因为没有石子可以取了，所以G(0)=0（但注意，有些定义中可能不给终止位置赋SG值，或者视为特殊值）。
2、对于n&gt=0，玩家会尝试取走一定数量的石子，使得剩下的石子数量m的sg函数值G(m)!=0。
3、通过计算可以发现，这个游戏的SG函数值呈现一种周期性模式，即当n足够大时，G(n)的值会开始重复。具体来说，周期的长度通常与k+1有关（但这也取决于具体的游戏规则）。

巴什博弈

题目描述

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》(英文名称:zatiura)，一直到现在，我依然对于电影中的部分电脑特技印象深刻。
今天，大家选择上机考试，就是一种勇敢(brave)的选择;这个短学期，我们讲的是博弈(game)专题;所以，大家现在玩的也是"勇敢者的游戏”，这也是我命名这个题目的原因。当然，除了“勇敢"，我还希望看到"诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~
各位勇敢者要玩的第一个游戏是什么呢?很简单，它是这样定义的:
1、本游戏是一个二人游戏:
2、有一堆石子一共有n个;
3、两人轮流进行:
4、每走一步可以取走1…m个石子;
5、最先取光石子的一方为胜;
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

输入

输入数据首先包含一个正整数C(C<-100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m(1<-n.m<-1000)，n和m的含义见题目描述

输出

如果先走的人能赢，请输出“frst”，否则请输出“second”，每个实例的输出占一行。

输入数据

2
23 2
4 3

输出数据

first
second

题解思路

当m=4时，石头数为0时前者为必胜态，1时也为必胜态，2时也为必胜态，3也为必胜态，4也为必胜态，5也为必败态…，依次类推可以得出当n%(m+1)==0时为必败态。

code：

#include<iostream>
using namespace std;
void solve(){int n,m;cin>>n>>m;if(n%(m+1)) cout<<"first"<<'\n';else cout<<"second"<<'\n';
}
int main(){int n;cin>>n;while(n--){solve();}return 0;
}

尼姆博弈

【模板】Nim 游戏

题目描述

甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$ ），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ （ $T\le10$ ），表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$ ，表示有 $n$ 堆石子， $n\le10^4$ 。

第二行有 $n$ 个数，表示每一堆石子的数量.

输出格式

共 $T$ 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。

样例 #1

样例输入 #1

样例输出 #1

No
Yes

解题思路：

(x，0，0，0)||(0，x，0，0)——>必败态(0，0，0，0)。
异或等于零为必败态。
异或和等于零必然由异或和不等于零推出来的，异或和不等于零一定有某种方法可以推出异或和等于零。
例子：
1，4，2(A拿)异或和不等于零
——>1，3，2(B拿)异或和等于零
——>0，3，2(A拿)异或和不等于零
——>0，2，2(B拿)异或和等于零
——>0，1，2(A拿)异或和不等于零
——>0，1，1(B拿)异或和等于零
——>0，0，1(A拿)异或和不等于零
——>A胜
它总可以把一个异或和不为零的状态转化为异或和为零的状态，也总可以把一个异或和为零的状态转化为异或和不为零的状态。

code:

#include<iostream>
using namespace std;
void solve(){int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){int x;cin>>x;ans^=x;}cout<<(ans ? "Yes":"No")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

题目描述

栗酱特别喜欢玩石子游戏，就是两个人玩，有n堆石子，每堆有ai个，每次一个人可以轮流选择任意一堆，取走任意多的石子(但不能不取)，谁先不能取谁输。
栗酱觉得这个游戏很有趣，知道有一天，小太阳告诉她，其实如果两个人足够聪明，游戏的结局一开始就已经注定。
栗酱是一个冰雪聪明的女孩子，她不相信，希望你演示给她看。

输入描述

多组数据，数据第一行T表示数据组数
每组数据第一行一个n，k表示一共有n堆石子，接下来你试图从第k堆开始取，从第二行开始，每隔一个空格一个
第i堆石子的数量ai.
n<=10 ^ 5,ai<=10 ^ 9

输出描述

输出“Yes"或“No"代表从该堆开始取是否可以必胜(如果足够聪明)。

输入

输出

No
Yes

说明

小太阳哥哥说，如果想赢，就试图把每堆石子数量的异或和变为0，最终便可以获得胜利，不相信自己证下。

解题思路

要改变一个数使其异或和为零，可以将一个数改为其余两个数的异或运算的答案。
分析No的数据：

3 2
1 2 3

要将1，2，3改变一个数使其异或和为零并且只可以改变第二个数，应该将其改为(1，3，3)，但是本题只能拿走，不能增加，所以先手应该为必败态。
分析Yes的数据：

2 1
2 1

要将2，1改变一个数使其异或和为零并且只能改变第一个数，应将其改为(1,1)，可以在第一堆中拿走一个所以先手必胜。
本题主要思路为现将除了第k位的数剩下的位数都进行 ^ 运算，然后需要地、第k位的数为剩下的数进行 ^ 运算的数，因为只有这样才可以让它异或和为零，如果这个数比原来的数大的话，不符合题意，则先手必败，如果这个数比原来的数小的话，符合题意，则先手必胜。

code：

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
void solve(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){if(i!=k) ans^=a[i];}cout<<(ans<a[k] ? "Yes":"No")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

题目描述

有一些石子堆，第i堆有 ai个石子。你和算卦先生轮流从任一堆中任取若干颗石子(每次只能取自一堆，并且不能不取），取到最后一颗石子的人获胜。
算卦先生来问你，如果你先手，你是否有必胜策略?若是改动其中几个石子堆中石子的数量呢?

输入描述

第一行两个正整数 n,q，表示有 n 个石堆，q 次操作。
第二行 n 个整数，第i个数 ai表示第i个石堆初始有 ai个石子。
接下去 q 行，每行两个正整数 x,y，表示把第x堆石子的个数修改成 y。操作是累计的，也就是说，每次操作是在上一次操作结束后的状态上操作的。

输出描述

共q行，输出每次操作之后先手是否有必胜策略如果有，输出"Kan"，否则输出"Li"

输入样例

输出样例

Kan
Kan
Li
Li

code：

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,q;
int main(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;for(int i=1;i<=n;i++){ans^=a[i];}for(int i=1;i<=q;i++){int x,y;cin>>x>>y;ans^=a[x];//将上次的第x位去掉，当一个数被异或运算两次，这个数会变成原来的数//一个数异或0不会改变这个数a[x]=y;ans^=a[x];cout<<(ans ? "Kan":"Li")<<'\n';}return 0;
}

题目描述

现在有两堆石子，两个人轮流从中取石子，且每个人每一次只能取1、3或9个石子，取到最后一个石子的人win.
假设先手后手都会选择最好的方式来取石子，请您判断先后手的输赢情况。

输入描述:

多组输入
每组一行，一行包括两个正整数n1和n2(1<=n1<=100,1<=n2<=100)，代表了两堆石子的数目

输出描述:

如果先手能赢，输出"win";否则就输出"1ose"。

输入

1 1
1 2

输出

lose
win

code1:

#include<iostream>
#include<map>
using namespace std;
map<pair<int ,int>,bool>mp;
int f(int x,int y){if(mp.count({x,y})) return mp[{x,y}];bool res=false;if(x>=1)if(!f(x-1,y)) res=true;if(x>=3)if(!f(x-3,y)) res=true;if(x>=9)if(!f(x-9,y)) res=true;if(y>=1)if(!f(x,y-1)) res=true;if(y>=3)if(!f(x,y-3)) res=true;if(y>=9)if(!f(x,y-9)) res=true;return mp[{x,y}]=res;
}
int main(){int n,m;while(cin>>n>>m){cout<<(f(n,m) ? "win":"lose")<<'\n';}return 0;
}

解法思路2:

可以打表找规律

code2:

#include<iostream>
#include<map>
#include<iomanip>
using namespace std;
map<pair<int ,int>,bool>mp;
int f(int x,int y){if(mp.count({x,y})) return mp[{x,y}];bool res=false;if(x>=1)if(!f(x-1,y)) res=true;if(x>=3)if(!f(x-3,y)) res=true;if(x>=9)if(!f(x-9,y)) res=true;if(y>=1)if(!f(x,y-1)) res=true;if(y>=3)if(!f(x,y-3)) res=true;if(y>=9)if(!f(x,y-9)) res=true;return mp[{x,y}]=res;
}
void table(int n){cout<<' ';for(int i=1;i<=n;i++) cout<<setw(2)<<i<<' ';for(int i=1;i<=n;i++){cout<<setw(2)<<i<<' ';for(int j=1;j<=n;j++){cout<<setw(2)<<f(i,j)<<' ';}cout<<'\n';}
}
int main(){int n,m;table(20);return 0;
}

题目描述

大学英语四级考试就要来临了，你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是如此。当然，作为在考场浸润了十几载的当代人学生，Kikd和Cici更懂得考前的放松，所谓"张也有道"就是这个意思。这不，Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“叮五”?“还是“斗地丰”?
当然都不是!那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的:
1、总共n张牌；
2、双方轮流抓牌;
3、每人每次抓牌的个数只能是2的幕次(即:1，2，4，8，16…)
4、抓完牌，胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设，哪有不聪明的学生~)，并且每次都是Kiki先抓牌，请问谁能赢呢?当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。
Good luck inCET-4 everybody!

输入

输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n(1<=n<=1000)

输出

如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实例的输出占一行

输入数据

1
3

输出数据

Kiki
Cici

code1:

#include<iostream>
#include<cstring>
#include<set>
using namespace std;
const int N=1010;
int dp[N];
int mex(set<int>st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x){if(dp[x]!=-1) return dp[x];set<int>st;for(int i=1;i<=x;i<<=1) st.insert(sg(x-i));return dp[x]=mex(st);
}
int main(){memset(dp,-1,sizeof(dp));int n;while(cin>>n){cout<<(sg(n) ? "Kiki":"Cici")<<'\n';}return 0;
}

解题思路2:

打表找规律，可以通过打表看出周期性，然后对其取模

code2：

#include<iostream>
#include<cstring>
#include<set>
#include<iomanip>
using namespace std;
const int N=1010;
int dp[N];
int mex(set<int>st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x){if(dp[x]!=-1) return dp[x];set<int>st;for(int i=1;i<=x;i<<=1) st.insert(sg(x-i));return dp[x]=mex(st);
}
int main(){memset(dp,-1,sizeof(dp));int n;cin>>n;for(int i=0;i<=n;i++) cout<<setw(2)<<i<<' ';cout<<'\n';for(int i=0;i<=n;i++) cout<<setw(2)<<sg(i)<<' ';return 0;
}

[SDOI2009] E&D

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2 n$ 堆石子，编号为 $\sim 2n$ 。其中，为了方便起见，我们将第 $2 k - 1$ 堆与第 $2 k$ 堆（ $\le k \le n$ ）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$ 。显然，被分割的一堆的石子数至少要为 $2$ 。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$ ，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1, 2, 3, 1$ 。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$ 。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$ 。这样，轮到小 W 时，所有堆的数量均为 $1$ ，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 $T$ ，表示数据组数。

对于每组数据：

第一行一个整数 $N$ ，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2 n$ 。

第二行 $N$ 个整数 $S_{1 \dots N}$ 。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

样例 #1

样例输入 #1

2
4
1 2 3 1
6
1 1 1 1 1 1

样例输出 #1

YES
NO

提示

对于 $20\%$ 的数据， $N = 2$ 。

对于另外 $20\%$ 的数据， $\le 4$ ， $S_i \le 50$ 。

对于 $100\%$ 的数据， $\le T \le 20$ ， $\le N \le 2 \times 10^4$ 且 $N$ 为偶数， $\le S_i \le 2 \times 10^9$ 。

解题思路：

本题由于数据太大，所以需要打表，sg函数代码直接求解为code1，code2为打表代码，code3为正解。

code1：

#include<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;
map<pair<int,int >,int>mp;
int mex(set<int>&st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x,int y){//设x>yif(x<y) return sg(y,x);if(y==0) return 0;if(mp.count({x,y})) return mp[{x,y}];set<int>st;//把x全部拿走，y给x i个for(int i=1;i<y;i++) st.insert(sg(i,y-i));//把y全部拿走，x给y i个for(int i=1;i<x;i++) st.insert(sg(x-i,i));return mp[{x,y}]=mex(st);
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

code2：

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
map<pair<int,int >,int>mp;
int mex(set<int>&st){for(int i=0;;i++){if(st.find(i)==st.end())return i;}
}
int sg(int x,int y){//设x>yif(x<y) return sg(y,x);if(y==0) return 0;if(mp.count({x,y})) return mp[{x,y}];set<int>st;//把x全部拿走，y给x i个for(int i=1;i<y;i++) st.insert(sg(i,y-i));//把y全部拿走，x给y i个for(int i=1;i<x;i++) st.insert(sg(x-i,i));return mp[{x,y}]=mex(st);
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
void table(int n){cout<<"  ";for(int i=1;i<=n;i++) cout<<setw(2)<<i<<' ';cout<<'\n';for(int i=1;i<=n;i++){cout<<setw(2)<<i<<' ';for(int j=1;j<=n;j++){cout<<setw(2)<<sg(i,j)<<' ';}cout<<'\n';}
}
int main(){int n;cin>>n;table(n);return 0;
}

code3:

当x和y都是奇数时，就为零。
转移规律示意图：
请添加图片描述

规律：如果要找(20,5)则需要找到(10,ceil(5/2))

code3:

#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
int sg(int x,int y){if(x<y) return sg(y,x);if((x&1)&&(y&1)) return 0;//x和y都为奇数//一般向上取整都是加分母减一if(x&1) return sg((x+1)/2,y/2)+1;//(x+1)/2代表向上取整，奇数加1是偶数所以可以这样向上取整，整体加一表示状态加1if(y&1) return sg(x/2,(y+1)/2)+1;return sg(x/2,y/2)+1;
}
void solve(){int n;cin>>n;vector<int>s(n+1);for(int i=1;i<=n;i++){cin>>s[i];}int ans=0;for(int i=1;i<=n;i+=2){ans^=sg(s[i],s[i+1]);}cout<<(ans ? "YES" : "NO")<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

[SDOI2011] 黑白棋

题目描述

小 A 和小 B 又想到了一个新的游戏。

这个游戏是在一个 $\times n$ 的棋盘上进行的，棋盘上有 $k$ 个棋子，一半是黑色，一半是白色。

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 $1$ 到 $d$ 个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小 A 和小 B 轮流操作，现在小 A 先移动，有多少种初始棋子的布局会使他胜利呢？

输入格式

输入三个数 $n, k, d$ 。

输出格式

输出小 A 胜利的方案总数。答案对 $10^9+7$ 取模。

样例 #1

样例输入 #1

10 4 2

样例输出 #1

提示

对于 $30\%$ 的数据，有 $k = 2$ 。
对于 $100\%$ 的数据，有 $\leq d \leq k \leq n \leq 10^4$ ， $k$ 为偶数， $\leq 100$ 。

题解

请添加图片描述

code:

#include<iostream>
#define int long long
using namespace std;
const int N=1e4+9,p=1e9+7;
int dp[25][N];//用于动态规划的数组
int fac[N];//存储阶乘的数组
int modpow(int a,int b){//快速幂计算(a^b%p)int res=1;while(b){if(b&1) res=res*a%p;a=a*a%p,b>>=1;}return res;
}
int inv(int x){//乘法逆元(x在模p下的逆元)return modpow(x,p-2);
}
int C(int n,int m){//计算组合数 C(n,m)if(n<m||n<0||m<0) return 0;return fac[n]*inv(fac[n-m]*fac[m]%p)%p;
}
int mo(int x){//确保结果为非负数return (x%p+p)%p;
}
signed main(){int n,k,d;cin>>n>>k>>d;fac[0]=1;for(int i=1;i<=n;i++){fac[i]=fac[i-1]*i%p;//存储0～n的阶乘}//先处理dp[0]for(int i=0;i<=k/2;i+=d+1) dp[0][i]=C(k/2,i);for(int i=1;i<=20;i++){for(int j=0;j<=n-k;j++){for(int l=0;l<=k/2;l+=d+1){//在第i位放置L个1if(j-(1ll<<i)*l>=0) dp[i][j]+=dp[i-1][j-(1ll<<i)*l]*C(k/2,l)%p;dp[i][j]%=p;}}}int ans=0;for(int i=0;i<=n-k;i++){//还剩下n-i-k个空位，放入(k/2)+1个间隙ans=(ans+dp[20][i]*C(n-i-k/2,k/2)%p)%p;}cout<<mo(C(n,k)-ans)<<'\n';return 0;
}

sg函数

sg()=0是必败态，sg()!=0时必胜态
sg(x)=n表示x点可以到达sg(y)=1，2，3…n-1的点(类似一个Nim游戏中的一堆石子)
Nim- K：
必败态：把石头个数进行二进制分解，对于每一位上的1的个数%(k+1)都为零
必胜态：其余情况

模型

Bash模型

当有n个数，每次减少[1,m]，当n%(m+1)!=0时，前者为必胜态，否则为必败态。

Nim-1模型

在n堆石子中，每次任取一堆，取走若干个。在每次都取最优的情况下，初始状态为异或和不等于零，总有将此状态转化为异或和等于零的状态，最后可以得出先手必胜。

Nim-k模型

在n堆石子中，每次任选至多k堆，取走若干个。把所有数字(每堆上的石头个数)转化成二进制后，求每一位上1的个数，如果每一位都满足1的个数%(k+1)==0，那么就是必败态。