//HDOJ 2999 Stone Game, Why are you always there? 博弈 SG函数
/*
题意:有n个石子排成一行,每次只能取走连续的f个石子,f为给定的一个集合。
问先手 胜负态
思路:局面不可能存在无法判断的情况
假设有4个石子 集合中只有一个数2
则后继状态有{0,2}{1,1},{2,0}
因为{0,2}和{2,0}表示一样的状态 因此可以加一个剪枝
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 105
#define M 1005
int n,cnt;
int op[N],sg[M];
int mex(int n){
int i,j;
bool vis[1005];
if(sg[n] != -1)
return sg[n];
memset(vis,false,sizeof(vis));
for(i = 1; i < cnt && op[i] <= n; ++i){
for(j = 0; j+op[i] <= n && j < n/2+1 ; ++j){
if(sg[j] == -1)
sg[j] = mex(j);
if(sg[n-j-op[i]] == -1)
sg[n-j-op[i]] = mex(n-j-op[i]);
vis[sg[j]^sg[n-j-op[i]]] = true;
}
}
for(i = 0; ; ++i)
if(vis[i]==false)
return i;
}
int cmp(const void *a,const void *b){
return *(int *)a - *(int *)b;
}
int main(){
int i,k,m;
while(scanf("%d",&n)!=EOF){
for(i = 1; i <= n; ++i)
scanf("%d",&op[i]);
qsort(op+1,n,sizeof(op[0]),cmp);
cnt = 2;
for(i = 2; i <= n; ++i)
if(op[i] != op[i-1])
op[cnt++] = op[i];
memset(sg,-1,sizeof(sg));
scanf("%d",&k);
while(k--){
scanf("%d",&m);
if(sg[m] == -1)
sg[m] = mex(m);
puts(sg[m]?"1":"2");
}
}
return 0;
}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭州电子科技大学hdoj1002,大整数相加问题
包括简单数学 组合数学 动态规划 贪心算法 母函数 搜索算法 组合博弈论 计算几何 等等
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
杭电acm解题报告 详细解析2000-2099 适合acm初学者
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码