首页 > 代码库 > SG函数
SG函数
SG函数模板:
1 void getSG(int *s,int t){ 2 int i,j; 3 memset(sg,0,sizeof(sg)); 4 for(i=1; i<maxn; i++){ 5 memset(Hash,0,sizeof(Hash)); 6 for(j=0; j<t; j++) 7 if(i - s[j] >= 0) 8 Hash[sg[i-s[j]]] = 1; 9 for(j=0; j<maxn; j++) 10 if(!Hash[j]) 11 break; 12 sg[i] = j; 13 } 14 }
例子:HDU1536
这题有个小坑,一直时间超限,只要是Hash()类型定义为int了,改问bool速度就快多了。。。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1536
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 const int maxn = 10005; 6 int a[105],sg[maxn]; 7 bool Hash[maxn]; 8 using namespace std; 9 10 void getSG(int *s,int t){ 11 int i,j; 12 memset(sg,0,sizeof(sg)); 13 for(i=1; i<maxn; i++){ 14 memset(Hash,0,sizeof(Hash)); 15 for(j=0; j<t; j++) 16 if(i - s[j] >= 0) 17 Hash[sg[i-s[j]]] = 1; 18 for(j=0; j<maxn; j++) 19 if(!Hash[j]) 20 break; 21 sg[i] = j; 22 } 23 } 24 int main(){ 25 int n; 26 while(scanf("%d",&n)!=EOF,n){ 27 for(int i = 0; i < n; i++){ 28 scanf("%d",&a[i]); 29 } 30 sort(a, a+n); 31 getSG(a,n); 32 int m; 33 scanf("%d",&m); 34 while(m--){ 35 int sum = 0, h; 36 scanf("%d",&h); 37 for(int i = 1; i <= h; i++){ 38 int v; 39 scanf("%d",&v); 40 sum ^= sg[v]; 41 } 42 if(sum) printf("W"); 43 else printf("L"); 44 } 45 printf("\n"); 46 } 47 return 0; 48 }
SG函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。