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;

}