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

hdu1847(sg函数&yy)

2024-09-11 11:46:38   220人阅读

题目链接：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)


联系
我们