首页 > 代码库 > hdu1847(sg函数&yy)

hdu1847(sg函数&yy)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1847

 

题意:中文题诶~

 

思路:直接sg函数打表即可,观察打表的结果发现是有规律的,sg函数的值只为0, 1, 2,所以我们只需n%3即可得出答案;

回过头来我们可以这样想,对于3的倍数的数,无论如何操作,最后必定会到达3这点,因为每次只能减2的幂,那么显然这种情况下先手会败;

 

代码:

技术分享
 1 #include <iostream>
 2 #include <string.h>
 3 #define MAXN 1010
 4 using namespace std;
 5 
 6 int n, pos=1;
 7 int f[MAXN], vis[MAXN], sg[MAXN];
 8 
 9 void get_sg(){//**sg函数打表
10     memset(sg, 0, sizeof(sg));
11     for(int i=1; i<=MAXN; i++){
12         memset(vis, 0, sizeof(vis));
13         for(int j=1; f[j]<=i; j++){
14             vis[sg[i-f[j]]]=1;//标记当前点可以到达的点
15         }
16         for(int j=0; j<=MAXN; j++){
17             if(vis[j]==0){
18                 sg[i]=j;//第一个不属于mex函数的数
19                 break;
20             }
21         }
22     }
23 }
24 
25 int main(void){
26     for(int i=1; i<2000; i*=2){
27         f[pos++]=i;
28     }
29     get_sg();
30     while(cin >> n){
31         if(sg[n]==0){
32             cout << "Cici" << endl;
33         }else{
34             cout << "Kiki" << endl;
35         }
36     }
37     return 0;
38 }
View Code

 

hdu1847(sg函数&yy)