博弈-sg函数的原理和优化（hdu-1536）
生活随笔
收集整理的這篇文章主要介紹了
博弈-sg函数的原理和优化（hdu-1536）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
sg函數：sg函數是博弈中的確定一個position性質的一個函數，全稱是sprague-grundy。
/*? 收獲：? */?? #include<iostream> ?? #include<cstdlib> ?? #include<vector> ?? #include<map> ?? #include<cstring> ?? #include<set> ?? #include<string> ?? #include<algorithm> ?? #include<sstream> ?? #include<ctype.h> ?? #include<fstream> ?? #include<string.h> ?? #include<stdio.h> ?? #include<math.h> ?? #include<stack> ?? #include<queue> ?? #include<ctime> ?? //#include<conio.h> ?? using?namespace?std;?? ?? const?int?INF_MAX=0x7FFFFFFF;?? const?int?INF_MIN=-(1<<31);?? ?? const?double?eps=1e-10;?? const?double?pi=acos(-1.0);?? ?? #define?pb?push_back???//a.pb(?) ?? #define?chmin(a,b)?((a)<(b)?(a):(b)) ?? #define?chmax(a,b)?((a)>(b)?(a):(b)) ?? ?? ?? template<class?T>?inline?T?gcd(T?a,T?b)//NOTES:gcd( ?? ??{if(a<0)return?gcd(-a,b);if(b<0)return?gcd(a,-b);return?(b==0)?a:gcd(b,a%b);}?? template<class?T>?inline?T?lcm(T?a,T?b)//NOTES:lcm( ?? ??{if(a<0)return?lcm(-a,b);if(b<0)return?lcm(a,-b);return?a*(b/gcd(a,b));}?? ?? ?? typedef?pair<int,?int>?PII;?? typedef?vector<PII>?VPII;?? typedef?vector<int>?VI;?? typedef?vector<VI>?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++)?? ????{?? ????????cin>>M[i];?? ????}?? ????return?;?? }?? ?? void?debug()?? {?? ????cout<<"sg?function"<<endl;?? ????for(int?i?=?0;?i?<?100;?i++)?? ????{?? ????????cout<<i<<"?"<<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(cin>>Num,?Num)?? ????{?? ????????input_m();?? ????????getsg();?? ????????int?num;?? ????????cin>>num;?? ????????while(num--)?? ????????{?? ????????????int?nn,?tp;?? ????????????cin>>nn;?? ????????????int?ret?=?0;?? ????????????for(int?i?=?0;?i?<?nn;?i++)?? ????????????{?? ????????????????cin>>tp;?? ????????????????ret?^=?sg[tp];?? ????????????}?? ????????????if(ret?==?0)?cout<<"L";?? ????????????else?cout<<"W";?? ????????}?? ????????cout<<endl;?? ????}?? ????return?0;?? ????//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC); ?? }?? /*
收獲：
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<31);const double eps=1e-10;
const double pi=acos(-1.0);#define pb push_back //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))template<class T> inline T gcd(T a,T b)//NOTES:gcd({if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm({if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> 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++){cin>>M[i];}return ;
}void debug()
{cout<<"sg function"<<endl;for(int i = 0; i < 100; i++){cout<<i<<" "<<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(cin>>Num, Num){input_m();getsg();int num;cin>>num;while(num--){int nn, tp;cin>>nn;int ret = 0;for(int i = 0; i < nn; i++){cin>>tp;ret ^= sg[tp];}if(ret == 0) cout<<"L";else cout<<"W";}cout<<endl;}return 0;//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC);
}
#include"iostream" ?? #include"algorithm" ?? #include"string.h" ?? using?namespace?std;?? int?s[101],sg[10001],k;?? int?getsg(int?m)?? {?? ????int?hash[101]={0};?? ????int?i;?? ????for(i=0;i<k;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(i=0;;i++)?? ????????if(hash[i]==0)?? ????????????return?i;?? ??? ??? }?? int?main()?? {?? ????//int?k; ?? ???//?freopen("game.in","r",stdin); ?? ????//freopen("game.out","w",stdout); ?? ????while(cin>>k,k)?? ????{?? ????????int?i;?? ????????for(i=0;i<k;i++)?? ????????????cin>>s[i];?? ????????sort(s,s+k);?? ????????memset(sg,-1,sizeof(sg));?? ????????sg[0]=0;?? ????????int?t;?? ????????cin>>t;?????? ????????while(t--)?? ????????{?? ??????????????? ????????????int?n,m;?? ????????????cin>>n;?? ????????????int?ans=0;?? ????????????while(n--)?? ????????????{?? ????????????????cin>>m;?? ????????????????if(sg[m]==-1)?? ????????????????????sg[m]=getsg(m);?? ????????????????ans^=sg[m];?? ????????????}?? ????????????if(ans)?? ????????????????cout<<'W';?? ????????????else?cout<<'L';?? ????????}?? ????????cout<<endl;?? ????}?? ????return?0;?? }?? #include"iostream"
#include"algorithm"
#include"string.h"
using namespace std;
int s[101],sg[10001],k;
int getsg(int m)
{int hash[101]={0};int i;for(i=0;i<k;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(i=0;;i++)if(hash[i]==0)return i;}
int main()
{//int k;// freopen("game.in","r",stdin);//freopen("game.out","w",stdout);while(cin>>k,k){int i;for(i=0;i<k;i++)cin>>s[i];sort(s,s+k);memset(sg,-1,sizeof(sg));sg[0]=0;int t;cin>>t; while(t--){int n,m;cin>>n;int ans=0;while(n--){cin>>m;if(sg[m]==-1)sg[m]=getsg(m);ans^=sg[m];}if(ans)cout<<'W';else cout<<'L';}cout<<endl;}return 0;
}
是別人的代碼：
性質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?是別人的代碼：
總結
以上是生活随笔為你收集整理的博弈-sg函数的原理和优化（hdu-1536）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 博弈问题及SG函数（真的很经典）
- 下一篇： 程序员的八个级别