首页 > 代码库 > 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 }
hdu1847(sg函数&yy)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。