First, define the status Position P first hand must lose N x first win.
Operation method: reverse transfer
A pair with the same status and different location is equivalent to none.
For ICG games, we can represent every possible situation in the game as a point. And if there is a situation I and a situation J, and j is the successor of the situation I (that is, situation I can be transformed into a situation j), we use a directed edge, starting from I to J, to connect the points representing the situation I and the situation J.Then the whole game can be represented as a directed acyclic graph.
According to the definition of the ICG game, we know that any situation that can not continue is the end of the situation, that is, the P situation. In the above figure, we can mark all points with a degree of 0 as P. Then, according to the two properties of ICG game, we can reverse all the P points.N situation:
For a game that may happen x, we define its SG value as follows:
(1)If x is the end of the current situation, the SG value is 0.
(2)If the current x situation is not final, its SG value is:sg(x) = mex{sg(y) | yIt is the successor situation of X}.
mex{a[i]}Represents the smallest non negative integer that does not appear in a. For example,
mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2
We will use the SG function to express the above figure.
It can be found that if a situation x is P, then there is SG (x) =0; otherwise SG (x) > 0. The same SG value also satisfies the conversion relationship between N and P:
If a situation x, its SG (x) > 0, then there must be a follow-up situation y, SG (y) =0.
If a situation x, its SG (x) =0, then all subsequent situations of x y, SG (y) > 0.
From the above corollary, we can know that games described by N, P-Position can be described by SG as well. And there is a very useful theorem in the SG function, called SG theorem:
For multiple single games, X = x [1. n], each time we can only change the situation of one single game. The SG value of its overall situation is equal to the XOR sum of the SG values of these single games.
First define the mex (minimal excludant) operation, which is applied to a set to represent the smallest non-negative integer that does not belong to the set. For example, mex{0,1,2,4}=3, mex{2,3,5}=0, mex{}=0.
For a given directed acyclic graph, we define every vertex of a graph.Sprague-GrundyThe function g is as follows: G (x) =mex{g (y)} y is the successor} of X, where g (x) is sg[x].
For example, the problem of taking stones, there is a pile of n stones, each can only take {1, 3, 4} stones, the first stone to win, then the number of SG value?
sg[0]=0，f[]={1,3,4},
x=11-f{1} stones can be removed and the remaining {0}, mex{sg[0]}={0}, sg[1]=1;
x=22-f{1} stones can be removed and the remaining {1}, mex{sg[1]}={1}, sg[2]=0;
x=3When 3-f{1,3} stones can be removed, the remaining {2,0}, mex{sg[2], sg[0]}={0,0}, so sg[3]=1;
x=44-f {1,3,4} stones can be removed, the remaining {3,1,0}, mex {sg [3], SG [1], SG [0]} = {1,1,0}, so SG [4] = 2;
x=55-F {1,3,4} stones can be removed, the remaining {4,2,1}, mex {sg [4], SG [2], SG [1]} = {2,0,1}, so SG [5] = 3;
And so on…..
x 0 1 2 3 4 5 6 7 8….
sg[x] 0 1 0 1 2 3 2 0 1….
Calculate the SG value from the 1-n range.
f(Store the number of steps that can be taken. F[0] means how many ways to go.
f[]Needs to be sorted from small to large
1.You can choose consecutive integers with 1~m steps, directly take modules, SG (x) = x% (m+1);
2.Optional steps are arbitrary steps, SG (x) = x;
3.The number of optional steps is a series of discontinuous numbers, calculated by GetSG ().
//f[]：The number of stones that can be taken away//sg[]:0~nSG function value//hash[]:mex{} int f[N],sg[N],hash[N]; void getSG(int n) { int i,j; memset(sg,0,sizeof(sg)); for(i=1;i<=n;i++) { memset(hash,0,sizeof(hash)); for(j=1;f[j]<=i;j++) hash[sg[i-f[j]]]=1; for(j=0;j<=n;j++) //Finding the smallest non negative integer that does not appear in mes{} { if(hash[j]==0) { sg[i]=j; break; } } } }
SGcharge by the meter
//Note that S arrays are sorted from small to large SG functions are initialized to - 1 only once per set//nThe size S[i] of the set s is an array of the special rule set defined. int s[110],sg[10010],n; int SG_dfs(int x) { int i; if(sg[x]!=-1) return sg[x]; bool vis[110]; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { if(x>=s[i]) { SG_dfs(x-s[i]); vis[sg[x-s[i]]]=1; } } int e; for(i=0;;i++) if(!vis[i]) { e=i; break; } return sg[x]=e; }
dfs
Note that in the initialization of the SG table, it doesn’t have to be initialized every time; otherwise it will be T, because it can be recycled, which is a powerful place
HDU1536 actual combat
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int s[110],sg[10010],n; char op[200]; int SG_dfs(int x) { int i; if(sg[x]!=-1) return sg[x]; bool vis[110]; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { if(x>=s[i]) { SG_dfs(x-s[i]); vis[sg[x-s[i]]]=1; } } int e; for(i=0;;i++) if(!vis[i]) { e=i; break; } return sg[x]=e; } int main() { int k; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(int i=0 ; i<n ; i++) scanf("%d",&s[i]); sort(s,s+n); int m,cnt=0; scanf("%d",&m); memset(sg,-1,sizeof(sg)); for(int i=0 ; i<m ; i++) { scanf("%d",&k); int x=0; while(k--) { int w; scanf("%d",&w); x^=SG_dfs(w); } if(x!=0) printf("W"); else printf("L"); } puts(""); } return 0; }
View Code