Good Luck in CET-4 Everybody! HDU - 1847

题意:一堆n个的牌,每次抽1,2,4,8(2^k)张,最后不能取的输

思路:

直接手写博弈树,发现3的倍数一定为必败态.大胆猜想必败态,借着接着从3个性质证明

1. 当n=0(终止状态) 必败

2.对于当前局面是必败的,任何操作都只能转移到必胜态

3.对于当前局面必胜,可以转移到必败态

证明:

1.显然成立

2.   即  因为 2^k不可能有因数3,因此一定不能整除,所以对于当前为必败态的局面,任何操作都只能转为必胜态

3. 对于一个数n , 我们要证明,在n%3!=0的情况下, 一定存在一个k,  使得 . 打表表明在n <= 1000 的情况下一定成立.    等价    n%3=0,1,2    2^k%3=0,1,2  证毕

看了下网上说的是Bash博弈,想想有道理. 但是大多数博客对结论没证明

对于递归和非递归的版本,  sg上限是 1000

#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1005;
const int MOD=1e9+7;
const double EPS=1e-10;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}

int main(void){
    int n;
    while(scanf("%d",&n)==1){
        if(n%3==0)  printf("Cici\n");
        else    printf("Kiki\n");
    }
}

作为第一题博弈题,再写一遍get_sg和dfs版本

//SG函数版本
#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=10005;
const int MOD=1e9+7;
const double EPS=1e-10;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sg[N];
bool vis[N];
int f[N];
void get_sg(){
    int t=1;
    for(int i=1;i<=20;i++){
        f[i]=t;
        t*=2;
    }
    memset(sg,0,sizeof sg);
    sg[0]=0;
    for(int n=1;n<=1000;n++){
        memset(vis,0,sizeof vis);
        for(int j=1;j<=20&&n>=f[j];j++) vis[sg[n-f[j]]]=1;
        for(int i=0;i<=1000;i++){
            if(!vis[i]){
                sg[n]=i;
                break;
            }
        }
    }
    return ;
}
int main(void){
    get_sg();
    int n;
    while(scanf("%d",&n)==1){
        if(sg[n])   printf("Kiki\n");
        else    printf("Cici\n");
    }

    return 0;
}

//sg_dfs版
#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=10005;
const int MOD=1e9+7;
const double EPS=1e-10;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sg[N];
int f[N];
int sg_dfs(int n){
    if(sg[n]!=-1)   return sg[n];
    bool vis[50];
    memset(vis,false,sizeof vis);
    for(int i=1;i<=30&&f[i]<=n;i++){
        sg_dfs(n-f[i]);
        vis[sg[n-f[i]]]=1;
    }
    for(int i=0;i<=1000;++i){
        if(!vis[i]){
            return sg[n]=i;
        }
    }
}
int main(void){
    memset(sg,-1,sizeof sg);
    int t=1;
    for(int i=1;i<=20;i++)  f[i]=t,t*=2;
    sg_dfs(1000);
    int n;
    while(scanf("%d",&n)==1){
        if(sg[n])   printf("Kiki\n");
        else    printf("Cici\n");
    }

    return 0;
}