本文共 2264 字,大约阅读时间需要 7 分钟。
#includeusing namespace std;const int f[11] = {1,2,4,8,16,32,64,128,256,512,1024};int dp[1000+5];int main() { dp[0] = 0; bool flag; memset(dp,0,sizeof(dp)); for(int i = 1; i <= 1005; ++i){ flag = false; for(int j = 0; f[j] <= i && j < 11; ++j){ if(dp[i-f[j]] == 0){ //如果先手 能够让取牌后让后手进入 必败状态 则 先手胜 (这是个递推的过程) flag = true; break; } } if(flag){ dp[i] = 1; } else{ dp[i] = 0; } } int n; while(scanf("%d",&n) != EOF){ if(dp[n]){ printf("Kiki\n"); } else{ printf("Cici\n"); } } return 0; }
可以把dp状态打出来,就会发现,只有n%3 == 0时候 先手会输
SG函数实现:
SG函数:
首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c),那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集,所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。
本质也是递推的过程#includeusing namespace std;#define N 1000+5int sg[N];int f[] = {1,2,4,8,16,32,64,128,256,512,1024};bool vis[N];int main() { int n,i,j; for(i = 1; i <= N; ++i){ memset(vis,false,sizeof(vis)); for(j = 0; i >= f[j] && j < 11; ++j){ vis[sg[i-f[j]]] = true; //记录这一轮所有可能的后序状态,如果vis[0] = true表示可以让对手进入必败态 } for(j = 0; ; ++j){ if(!vis[j]){//如果后续状态可以取到0则表示 不能让后手进入 必败态 sg[i] = j; break; } } } for(int i = 0; i < 100; ++i){ printf("%d %d\n",i,sg[i]); } while(scanf("%d",&n) != EOF){ if(sg[n]){ printf("Kiki\n"); } else{ printf("Cici\n"); } } }
参考: