int sg[maxn];//sg[n] n表示每堆数量 int s[k];//每次能取的值，下标从0开始，0 ~ k-1,必须有序，可以sort(s,s+k); bool vis[maxn]; const int k;//k是集合s的大小 void get_sg() { int i,j; for(i=0;i<maxn;i++) { memset(vis,0,sizeof(vis)); j=0; while(j<k&&s[j]<=i) { vis[sg[i-s[j]]]=1; j++; } for(j=0;j<maxn;j++) if(!vis[j]) { sg[i]=j; break; } } } int main() { ... //将s数组初始化,如果s数组不是从小到大递增的话需要进行sort memset(sg,-1,sizeof(sg)); get_sg(); if(sg[n]==0) //先手必败 else //先手必胜 //如果有多堆，则 // num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx]; // if(num==0) 则先手必败 // else 先手必胜 ... }
//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍 //n是集合s的大小 S[i]是定义的特殊取法规则的数组 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; }
HDU - 1847
题意：n 张牌( 1 <= n <= 1000)，两个人轮流取牌，只能取2的幂次张牌 （即：1，2，4，8，16...），最后抓完牌的人获胜
题解：一堆，s数组取值为 2 ^ i (0 <= i <= 11)
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-4 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 1e3 + 5; const int mod = 998244353; #define k 12 int sg[maxn];//sg[n] n表示每堆数量 int s[k];//每次能取的值，下标从0开始，0 ~ k-1,必须有序，可以sort(s,s+k); bool vis[maxn]; void get_sg() { int i, j; for (i = 0; i < maxn; i++) { memset(vis, 0, sizeof(vis)); j = 0; while (j < k && s[j] <= i) { vis[sg[i - s[j]]] = 1; j++; } for (j = 0; j < maxn; j++) if (!vis[j]) { sg[i] = j; break; } } } int main() { int n; for(int i = 0; i < k; i++) s[i] = int(pow(2,i)); while(cin >> n) { memset(sg, -1, sizeof(sg)); get_sg(); if (sg[n] == 0) //先手必败 puts("Cici"); else puts("Kiki");//先手必胜 } //如果有多堆，则 // num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx]; // if(num==0) 则先手必败 // else 先手必胜 }
HDU - 1730
题意：如图所示，游戏在一个n行m列（1 ≤ n ≤ 1000且2 ≤ m ≤ 100）的棋盘上进行，每行有一个黑子（黑方）和一个白子（白方）。执黑的一方先行，每次玩家可以移动己方的任何一枚棋子到同一行的任何一个空格上，当然这过程中不许越过该行的敌方棋子。双方轮流移动，直到某一方无法行动为止，移动最后一步的玩家获胜。
题解：每一行中加的距离可以看作是石子的堆数，因为每一个当一个人往两侧走的时候，另一个人可以往那个方向走直至距离一样，这个基础上它还可以再走，所以中间的距离只会减少不会增加，就可以看作是一个多堆石子的NIM游戏
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-4 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 1e3 + 5; const int mod = 998244353; #define k 12 int sg[maxn];//sg[n] n表示每堆数量 int s[k];//每次能取的值，下标从0开始，0 ~ k-1,必须有序，可以sort(s,s+k); bool vis[maxn]; void get_sg() { int i, j; for (i = 0; i < maxn; i++) { memset(vis, 0, sizeof(vis)); j = 0; while (j < k && s[j] <= i) { vis[sg[i - s[j]]] = 1; j++; } for (j = 0; j < maxn; j++) if (!vis[j]) { sg[i] = j; break; } } } int main() { int n,m; while(cin >> n >> m) { int a,b; int flag = 0; while(n--){ cin >> a >> b; flag ^= (abs(a - b) - 1); } if(flag == 0) puts("BAD LUCK!"); else puts("I WIN!"); } //如果有多堆，则 // num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx]; // if(num==0) 则先手必败 // else 先手必胜 }
HDU - 1848
题意：3堆石子，每次只能取斐波那契数列中的个数，去完最后一个的人赢
题解：打表fibonacci后打SG表
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-4 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 1e3 + 5; const int mod = 998244353; int sg[maxn];//sg[n] n表示每堆数量 int s[50];//每次能取的值，下标从0开始，0 ~ k-1,必须有序，可以sort(s,s+k); bool vis[maxn]; int k;//k是集合s的大小 void get_sg() { int i,j; for(i=0;i<maxn;i++) { memset(vis,0,sizeof(vis)); j=0; while(j<k&&s[j]<=i) { vis[sg[i-s[j]]]=1; j++; } for(j=0;j<maxn;j++) if(!vis[j]) { sg[i]=j; break; } } } int main() { s[0] = 1; s[1] = 2; for(int i = 2;i ; i++){ s[i] = s[i - 1] + s[i - 2]; if(s[i] > 1000) { k = i; break; } } // debug(k); int m,n,p; while(cin >> m >> n >> p) { if(m == 0 && n == 0 && p == 0) break; memset(sg, -1, sizeof(sg)); get_sg(); int flag = sg[n] ^ sg[m] ^ sg[p]; if(flag == 0) puts("Nacci"); else puts("Fibo"); } //如果有多堆，则 // num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx]; // if(num==0) 则先手必败 // else 先手必胜 }
HDU - 1536
题意：给出k个可取数的集合，m个查询。查询每次是否是先后获胜。
题解：给定s数组，记得排序
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-4 #define bug printf("*********\n") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int MAXN = 1e4 + 5; const int mod = 998244353; int sg[MAXN]; int s[MAXN]; bool vis[MAXN]; int k; void SG() { int i,j; for(i = 0 ; i < MAXN; i ++) { memset(vis,0,sizeof vis); j = 0; while(j < k && s[j] <= i) { vis[sg[i - s[j]]] = 1; j++; } for(j = 0; j < MAXN; j++) if(!vis[j]) { sg[i] = j; break; } } } int main() { int n; while(scanf("%d",&n) && n) { memset(sg,-1,sizeof sg); for(int i = 0; i < n; i++) scanf("%d",&s[i]); k = n; sort(s,s + k); SG(); int m; scanf("%d",&m); while(m--) { int l; scanf("%d",&l); int flag = 0; while(l--) { int tmp; scanf("%d",&tmp); flag ^= sg[tmp]; } if(flag == 0) putchar(‘L‘); else putchar(‘W‘); } printf("\n"); } }
原文：https://www.cnblogs.com/smallhester/p/11371983.html
