首页 > 代码库 > hdu 1536 S-Nim|| poj 2960 S-Nim (sg函数)
hdu 1536 S-Nim|| poj 2960 S-Nim (sg函数)
#include <stdio.h> #include <string.h> int s[110]; int sg[10010],hash[110]; int n, m; int getsg(int x) //sg模板 { int i; if(sg[x] != -1) return sg[x]; memset(hash,0,sizeof(hash)); for(i = 0; i < n; i++) { if(x >= s[i]) { sg[x - s[i]] = getsg(x - s[i]); hash[sg[x - s[i]]] = 1; } } for(i = 0; i < 110; i++) { if(hash[i] == 0) break; } return i; } int main ( ) { int i,k; int a,j,l; char ans[110]; while(scanf("%d", &n) != EOF) { if(n == 0) break; k = 0; for(i = 0; i < n; i++) scanf("%d", &s[i]); memset(sg, -1, sizeof(sg)); sg[0] = 0; for(i = 1; i < 10010; i++) sg[i] = getsg(i); scanf("%d", &m); for(i = 0; i < m; i++) { int sum = 0; scanf("%d", &l); for(j = 0; j < l; j++) { scanf("%d", &a); sum ^= sg[a]; //尼姆的变形 } if(sum == 0) ans[k ++] = 'L'; else ans[k ++] = 'W'; } for(i = 0; i < k; i++) printf("%c", ans[i]); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。