做北美市场用哪个网站,帮别人做视频剪辑的网站,优化加速,公众号开发哪家专业sg函数#xff1a;sg函数是博弈中的确定一个position性质的一个函数#xff0c;全称是sprague-grundy。性质1#xff1a;对于所有的p-position#xff0c;都有sg 0#xff1b;对于所有的n-position都有sg #xff01; 0#xff1b; 性质2#xff1a;某点a的sg函数的值…sg函数sg函数是博弈中的确定一个position性质的一个函数全称是sprague-grundy。性质1对于所有的p-position都有sg 0对于所有的n-position都有sg 0 性质2某点a的sg函数的值由它的后继的sg函数的值来决定设后继为b, c, d, e……则sg(a) mex(sg(a), sg(b), sg(c), sg(d), sg(e),…… mex是不属于这个集合的最小非负整数。 应用范围在此无环图中谁无法再次移动便是输。如果谁无法移动便是赢暂时不知如何解决。 应用通过判断该点sg 0是p点sg 0是N点。 构造sg函数的方法 方法一打表 例题hdu-1536-S-nim 点击打开链接 [cpp] view plaincopyprint? /* 收获 */ #includeiostream #includecstdlib #includevector #includemap #includecstring #includeset #includestring #includealgorithm #includesstream #includectype.h #includefstream #includestring.h #includestdio.h #includemath.h #includestack #includequeue #includectime //#includeconio.h using namespace std; const int INF_MAX0x7FFFFFFF; const int INF_MIN-(131); const double eps1e-10; const double piacos(-1.0); #define pb push_back //a.pb( ) #define chmin(a,b) ((a)(b)?(a):(b)) #define chmax(a,b) ((a)(b)?(a):(b)) templateclass T inline T gcd(T a,T b)//NOTES:gcd( {if(a0)return gcd(-a,b);if(b0)return gcd(a,-b);return (b0)?a:gcd(b,a%b);} templateclass T inline T lcm(T a,T b)//NOTES:lcm( {if(a0)return lcm(-a,b);if(b0)return lcm(a,-b);return a*(b/gcd(a,b));} typedef pairint, int PII; typedef vectorPII VPII; typedef vectorint VI; typedef vectorVI VVI; typedef long long LL; int dir_4[4][2]{{0,1},{-1,0},{0,-1},{1,0}}; int dir_8[8][2]{{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}}; //下左下左左上上右上右右下。 //******* WATER **************************************************************** const int MAXN 10500; bool judge[150]; int sg[MAXN]; int M[150]; const int Init 1e7; int Num; void input_m() { for(int i 0; i Num; i) { cinM[i]; } return ; } void debug() { coutsg functionendl; for(int i 0; i 100; i) { couti sg[i]endl; } return ; } void getsg() { for(int i 0; i MAXN; i) { memset(judge, false, sizeof(judge)); //int tsg Init; for(int j 0; j Num; j) { int ps i - M[j]; if(ps 0) judge[sg[ps]] true; } //if(tsg Init) tsg 0; for(int j 0; j Num 1; j) { if(judge[j] false) { sg[i] j; break; } } } //debug(); return ; } int main() { //freopen(input.txt,r,stdin); //freopen(output.txt,w,stdout); while(cinNum, Num) { input_m(); getsg(); int num; cinnum; while(num--) { int nn, tp; cinnn; int ret 0; for(int i 0; i nn; i) { cintp; ret ^ sg[tp]; } if(ret 0) coutL; else coutW; } coutendl; } return 0; //printf(%.6f\n,(double)clock()/CLOCKS_PER_SEC); } /*
收获
*/
#includeiostream
#includecstdlib
#includevector
#includemap
#includecstring
#includeset
#includestring
#includealgorithm
#includesstream
#includectype.h
#includefstream
#includestring.h
#includestdio.h
#includemath.h
#includestack
#includequeue
#includectime
//#includeconio.h
using namespace std;
const int INF_MAX0x7FFFFFFF;
const int INF_MIN-(131);
const double eps1e-10;
const double piacos(-1.0);
#define pb push_back //a.pb( )
#define chmin(a,b) ((a)(b)?(a):(b))
#define chmax(a,b) ((a)(b)?(a):(b))
templateclass T inline T gcd(T a,T b)//NOTES:gcd(
{if(a0)return gcd(-a,b);if(b0)return gcd(a,-b);return (b0)?a:gcd(b,a%b);}
templateclass T inline T lcm(T a,T b)//NOTES:lcm(
{if(a0)return lcm(-a,b);if(b0)return lcm(a,-b);return a*(b/gcd(a,b));}
typedef pairint, int PII;
typedef vectorPII VPII;
typedef vectorint VI;
typedef vectorVI VVI;
typedef long long LL;
int dir_4[4][2]{{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]{{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下左下左左上上右上右右下。
//******* WATER ****************************************************************
const int MAXN 10500;
bool judge[150];
int sg[MAXN];
int M[150];
const int Init 1e7;
int Num;
void input_m()
{
for(int i 0; i Num; i)
{
cinM[i];
}
return ;
}
void debug()
{
coutsg functionendl;
for(int i 0; i 100; i)
{
couti sg[i]endl;
}
return ;
}
void getsg()
{
for(int i 0; i MAXN; i)
{
memset(judge, false, sizeof(judge));
//int tsg Init;
for(int j 0; j Num; j)
{
int ps i - M[j];
if(ps 0) judge[sg[ps]] true;
}
//if(tsg Init) tsg 0;
for(int j 0; j Num 1; j)
{
if(judge[j] false)
{
sg[i] j;
break;
}
}
}
//debug();
return ;
}
int main()
{
//freopen(input.txt,r,stdin);
//freopen(output.txt,w,stdout);
while(cinNum, Num)
{
input_m();
getsg();
int num;
cinnum;
while(num--)
{
int nn, tp;
cinnn;
int ret 0;
for(int i 0; i nn; i)
{
cintp;
ret ^ sg[tp];
}
if(ret 0) coutL;
else coutW;
}
coutendl;
}
return 0;
//printf(%.6f\n,(double)clock()/CLOCKS_PER_SEC);
}
方法二递归迭代 以下 [cpp] view plaincopyprint? #includeiostream #includealgorithm #includestring.h using namespace std; int s[101],sg[10001],k; int getsg(int m) { int hash[101]{0}; int i; for(i0;ik;i){ if(m-s[i]0) break; if(sg[m-s[i]]-1) sg[m-s[i]]getsg(m-s[i]); hash[sg[m-s[i]]]1; } for(i0;;i) if(hash[i]0) return i; } int main() { //int k; // freopen(game.in,r,stdin); //freopen(game.out,w,stdout); while(cink,k) { int i; for(i0;ik;i) cins[i]; sort(s,sk); memset(sg,-1,sizeof(sg)); sg[0]0; int t; cint; while(t--) { int n,m; cinn; int ans0; while(n--) { cinm; if(sg[m]-1) sg[m]getsg(m); ans^sg[m]; } if(ans) coutW; else coutL; } coutendl; } return 0; } #includeiostream
#includealgorithm
#includestring.h
using namespace std;
int s[101],sg[10001],k;
int getsg(int m)
{
int hash[101]{0};
int i;
for(i0;ik;i){
if(m-s[i]0)
break;
if(sg[m-s[i]]-1)
sg[m-s[i]]getsg(m-s[i]);
hash[sg[m-s[i]]]1;
}
for(i0;;i)
if(hash[i]0)
return i;
}
int main()
{
//int k;
// freopen(game.in,r,stdin);
//freopen(game.out,w,stdout);
while(cink,k)
{
int i;
for(i0;ik;i)
cins[i];
sort(s,sk);
memset(sg,-1,sizeof(sg));
sg[0]0;
int t;
cint;
while(t--)
{
int n,m;
cinn;
int ans0;
while(n--)
{
cinm;
if(sg[m]-1)
sg[m]getsg(m);
ans^sg[m];
}
if(ans)
coutW;
else coutL;
}
coutendl;
}
return 0;
} 是别人的代码
相关文章：
