首页 > 代码库 > BZOJ 1874 取石子游戏 (NIM游戏)
BZOJ 1874 取石子游戏 (NIM游戏)
题解:简单的NIM游戏,直接计算SG函数,至于找先手策略则按字典序异或掉,去除石子后再异或判断,若可行则直接输出。
#include const int N=1005;int SG[N],b[N],hash[N],a[N],sum,tmp,i,j,n,m; void FSG(int s){ SG[0]=0; for(int i=1;i<=s;i++){ for(int j=1;b[j]<=i&&j<=m;j++)hash[SG[i-b[j]]]=i; for(int j=0;j<=s;j++)if(hash[j]!=i){SG[i]=j;break;} } } int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); scanf("%d",&m); for(i=1;i<=m;i++)scanf("%d",&b[i]); FSG(N); for(i=1;i<=n;i++)sum^=SG[a[i]]; if(!sum){printf("NO");return 0;} for(i=1;i<=n;i++){ tmp=sum^SG[a[i]]; for(j=1;b[j]<=a[i]&&j<=m;j++) if(!(tmp^SG[a[i]-b[j]])){ printf("YES\n%d %d",i,b[j]); return 0; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。