http://acm.hdu.edu.cn/showproblem.php?pid=5795
可以进行一堆分三堆操作的nim多堆问题
nim问题说到底也是sg函数的问题，sg函数求的是当前状态所无法到达的最小状态，这个状态本质是由自己编号的，一般情况下根据石子数目编号，但是不可以采用不同的两套标准。对于分三堆，比如3->(1,2)似乎无法进行sg函数编号，实际上两堆的sg等于两堆独立sg的异或，但是又值得注意的是sg函数所能到达的状态的含义是当前局面的子和子子...局面。
所以sg打表我是模仿这个的,注释的地方很关键
int sg[maxn]; int g(int x){int mex[1010];memset(mex,0,sizeof(mex));if(sg[x]!=-1)return sg[x];for(int i=x-1;i>=0;i--)mex[g(i)]=1; //g(i)，因为必须要考虑到后继能够分堆for(int i=1;i<=x/2;i++){int ans=0;ans^=g(i);//g(i)，因为必须要考虑到后继能够分堆ans^=g(x-i);//g(i)，因为必须要考虑到后继能够分堆mex[ans]=1;}for(int i=0;;i++)if(!mex[i])return sg[x]=i; }int main() {int n;while(scanf("%d",&n)==1){NEG(sg);printf("%d\n",g(n));}return 0; }
最终发现sg函数8个一组有规律 #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<string> #include<cctype> #include<stack> #include<queue> #include<set> #include<sstream> #include<map> using namespace std; #define For(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,k,n) for(int i=n;i>=k;i--) #define Lson (u<<1) #define Rson ((u<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define NEG(a) memset(a,-1,sizeof(a)); #define FILL(a) memset(a,0x3f,sizeof(a)); #define INF 0x3f3f3f3f #define LLINF 0x3f3f3f3f3f3f3f3f #define ll long long #define printbin(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<b<<"="<<s<<endl;} #define printarr(i,a,f,b) {For(i,f,b) printf("%d ",a[i]); printf("\n");} #define flgprint(flg,a,b) {if(flg) printf("%s\n",a);else printf("%s\n",b);} #define fp freopen("in.txt","r",stdin) #define maxn 2000int N,M; void solve(int a,int b) {int f=true;while(true){if(a>b) swap(a,b);if(b%a==0) break;if(b-a>a) break;b-=a;f=!f;}flgprint(f,"Stan wins","Ollie wins"); } int main() {while(scanf("%d %d",&N,&M)==2&&!(N==0&&M==0)){solve(N,M);}return 0; }