博弈---ZOJ 2083 Win the Game(染绳子)

本文主要是介绍博弈---ZOJ 2083 Win the Game(染绳子)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2083

大意：两个人分别对n条绳子染 每次染m长 最后染不下的输，问先手胜负

思路：每一条绳子看做一个子问题(求每个绳子的SG再异或就是整个事件的SG)，每条绳子 染的m的段 左右两端各一段，

分别求这左右两端的SG再异或 通过SG打表或递归求出整个绳子的各地方的SG

#include<stdio.h>
#include<string.h>
int fib;
int SG[60];void getsg(){bool vis[56];memset(SG,0,sizeof(SG));for(int i=2;i<=50;i++){ //i 为当前总长度memset(vis,0,sizeof(vis));for(int j=0;j+2<=i;j++)  //j 为左端长度vis[SG[j]^SG[i-j-2]]=1;for(int k=0;k<=55;k++)if(vis[k]==0){SG[i]=k;break;}}}int main(){fib=2;getsg();int n,t;int sum=0;while(~scanf("%d",&n)){sum=0;while(n--){scanf("%d",&t);sum^=SG[t];}if(sum==0)printf("No\n");else printf("Yes\n");}return 0;
}

另外还有一种题型；

//将上题的线段改为环 做法一样先手先取一段m 问先手胜负

//思路还是一样 先手先取一段，破环为线段，现在就是换对手考虑线段

//做法还是一样 这边改为SG(n-m)  然后判断胜负条件改为和原题相反(应该懂吧？)

这篇关于博弈---ZOJ 2083 Win the Game(染绳子)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---