HDU.1847 Good Luck in CET-4 Everybody! ( 博弈论 SG分析)

时间:2023-03-08 16:30:22

HDU.1847 Good Luck in CET-4 Everybody! ( 博弈论 SG分析)

题意分析

简单的SG分析

题意分析

简单的nim 博弈

博弈论快速入门

代码总览

//#include <cstdio>
//using namespace std;
//
//int main()
//{
// int n;
// while(scanf("%d",&n) != EOF){
// if(n %3 == 0) printf("Cici\n");
// else printf("Kiki\n");
// }
// return 0;
//}
#include <cstdio>
#include <cstring>
#define nmax 1005
using namespace std;
int maybe[] = {1,2,4,8,16,32,64,128,256,512,1024};
int sg[nmax];
int f[nmax];
void getSG()
{
sg[0] = 0;
for(int i = 1;i<nmax;++i){
memset(f,0,sizeof f);
for(int j = 0;j<10;++j){
if(i-maybe[j] < 0)break;
f[sg[i-maybe[j]]] = 1;
}
for(int j = 0;;++j){
if(!f[j]){
sg[i] = j;
break;
}
}
}
}
int main()
{
getSG();
int n;
while(scanf("%d",&n) != EOF){
if(sg[n]== 0) printf("Cici\n");
else printf("Kiki\n");
}
return 0;
}