HDU - 1847 Good Luck in CET-4 Everybody!

题目链接:https://vjudge.net/problem/HDU-1847

思路

SG函数模板题

代码

#include <iostream>
#include <cstring>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int SG[maxn],f[maxn];
bool vis[maxn];

void init_SG(int N){
    int pos = 1;
    for(int j =1;j<=10000;j*=2) f[pos++] = j;
    for(int i = 1;i<=N;i++){
        memset(vis,0,sizeof vis);
        for(int j = 1;f[j]<=i; j++){
            vis[SG[i-f[j]]] = 1;
        }
        for(int j = 0;j<=N;j++){
            if(!vis[j]){
                SG[i] = j;
                break;
            }
        }
    }
}

int main(){
    // debug;
    ios;
    init_SG(1000);
    while(cin>>N){
        if(SG[N]) cout<<"Kiki\n";
        else cout<<"Cici\n";
    }

    return 0;
}