当前位置: 首页> 科技> 能源 > 手机怎么使用代理ip上网_太原网站建设方案托管_拼多多关键词排名在哪里看_西安seo工作室

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

时间:2025/7/11 17:23:48来源:https://blog.csdn.net/2301_80662593/article/details/143109753 浏览次数:0次
手机怎么使用代理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 n n 堆石子(每堆石子数量小于 1 0 4 10^4 104),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手,且告诉你这 n n n 堆石子的数量,他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 T T T T ≤ 10 T\le10 T10),表示有 T T T 组数据

接下来每两行是一组数据,第一行一个整数 n n n,表示有 n n n 堆石子, n ≤ 1 0 4 n\le10^4 n104

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

输出格式

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

样例 #1

样例输入 #1
2
2
1 1
2
1 0
样例输出 #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"代表从该堆开始取是否可以必胜(如果足够聪明)。

输入

2
3 2
1 2 3
2 1
2 1

输出

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"

输入样例

5 4
6 7 3 4 5
1 6
2 1
2 4
5 5

输出样例

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 2n 2n 堆石子,编号为 1 ∼ 2 n 1 \sim 2n 12n。其中,为了方便起见,我们将第 2 k − 1 2k-1 2k1 堆与第 2 k 2k 2k 堆( 1 ≤ k ≤ n 1 \le k \le n 1kn)视为同一组。第 i i i 堆的石子个数用一个正整数 S i S_i Si 表示。

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

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

输入格式

本题有多组数据。

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

对于每组数据:

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

第二行 N N N 个整数 S 1 … N S_{1 \dots N} S1N

输出格式

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

样例 #1

样例输入 #1
2
4
1 2 3 1
6
1 1 1 1 1 1
样例输出 #1
YES
NO

提示

对于 20 % 20\% 20% 的数据, N = 2 N=2 N=2

对于另外 20 % 20\% 20% 的数据, N ≤ 4 N \le 4 N4 S i ≤ 50 S_i \le 50 Si50

对于 100 % 100\% 100% 的数据, 1 ≤ T ≤ 20 1 \le T \le 20 1T20 1 ≤ N ≤ 2 × 1 0 4 1 \le N \le 2 \times 10^4 1N2×104 N N N 为偶数, 1 ≤ S i ≤ 2 × 1 0 9 1 \le S_i \le 2 \times 10^9 1Si2×109

解题思路:

本题由于数据太大,所以需要打表,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 又想到了一个新的游戏。

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1
10 4 2
样例输出 #1
182

提示

  • 对于 30 % 30\% 30% 的数据,有 k = 2 k=2 k=2
  • 对于 100 % 100\% 100% 的数据,有 1 ≤ d ≤ k ≤ n ≤ 1 0 4 1 \leq d \leq k \leq n \leq 10^4 1dkn104 k k k 为偶数, k ≤ 100 k \leq 100 k100

题解

请添加图片描述

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,那么就是必败态。

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: