http://acm.hdu.edu.cn/showproblem.php?pid=3980
求sg值。
一开始被第二个样例卡住了,读了好几遍题才发现它初始是个环。
这样就可以先把它变成链,然后在链上枚举取m个连续点,每次都可以将这条链分成两部分,相当于两个子游戏。对于一个链,一共有n-m-i个子游戏对,用vis数组标记好这些子游戏对的异或值,最后就可以找出sg[n]。
这算是我做的第三种类型求sg值的题吧。
code:
#include<cstdio>
#include<cstring>
int sg[1001], m ;
int mex(int n){
if(sg[n]!=-1) return sg[n] ;
if(n-m<0){
sg[n] = 0 ;
return 0 ;
}
bool vis[1001] ;
int i ;
memset(vis, false, sizeof(vis)) ;
for(i=0; i<=n-m-i; i++)
vis[mex(i)^mex(n-m-i)] = 1 ;
for(i=0; vis[i]; i++) ;
sg[n] = i ;
return sg[n] ;
}
int main(){
int T, t, i, j, n ;
scanf("%d", &T) ;
for(t=1; t<=T; t++){
memset(sg, -1, sizeof(sg)) ;
scanf("%d%d", &n, &m) ;
printf("Case #%d: ", t) ;
if(n<m){
printf("abcdxyzk\n") ;
continue ;
}
if(!mex(n-m)) printf("aekdycoin\n") ;
else printf("abcdxyzk\n") ;
}
return 0 ;}
#include<cstring>
int sg[1001], m ;
int mex(int n){
if(sg[n]!=-1) return sg[n] ;
if(n-m<0){
sg[n] = 0 ;
return 0 ;
}
bool vis[1001] ;
int i ;
memset(vis, false, sizeof(vis)) ;
for(i=0; i<=n-m-i; i++)
vis[mex(i)^mex(n-m-i)] = 1 ;
for(i=0; vis[i]; i++) ;
sg[n] = i ;
return sg[n] ;
}
int main(){
int T, t, i, j, n ;
scanf("%d", &T) ;
for(t=1; t<=T; t++){
memset(sg, -1, sizeof(sg)) ;
scanf("%d%d", &n, &m) ;
printf("Case #%d: ", t) ;
if(n<m){
printf("abcdxyzk\n") ;
continue ;
}
if(!mex(n-m)) printf("aekdycoin\n") ;
else printf("abcdxyzk\n") ;
}
return 0 ;}