注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

博弈论(自学总结)  

2014-03-04 21:27:40|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
做了几道博弈论的题,真是考验智商,但总的思路其实只有一个:就是若全局只有2个状态:必胜和必败,而这两个状态可以改变的,如:先手必败到先手必胜。首先我们要避开一个误区:从一个先手必败状态可以推到先手必胜,因为退出的状态可以走到必败状态让对手输(这个结论是正确的),但注意!!:从先手必胜推到先手必败这是错误的,因为对手不会傻到走到你的必胜状态让你赢,他会尽可能地走别的路,当然如果他能走的路都是对手必胜的路,那么这个状态必败(有且只有这种推必败法才能成立)。 总结起来就是必败状态能推到必胜状态,而必败状态必须是所有的选择都是必胜状态才能得到。
举例说明:WIKIOI新井子棋:此题代码写了注释:
#include<cstdio>
#include<cstring>
#include<iostream>
int T,sg[10000],num[100],G,next[100],last[100],to[100];
void addedge(int x,int y){
next[++G]=last[x]; last[x]=G; to[G]=y;
next[++G]=last[y]; last[y]=G; to[G]=x;
}//边表 
int cal(int sta){
int temp=0;
for(int i=1;i<=12;i++) if(sta&num[i]) ++temp;
return temp;//统计STA中有几个1;位运算加速; 
}
int mex(int sta){
if(sg[sta]!=-1) return sg[sta];//记忆化 
int temp=cal(sta);//核对sta有几个1,记录到temp里; 
if(temp==1) return sg[sta]=0;//序列中只有1个1,那么无论位置如何,先手必败; 
if(temp==2) return sg[sta]=1;//序列中只有2个1,那么无论位置如何,先手必胜; 
for(int i=1;i<=12;i++)
if(sta&num[i]){
if(mex(sta-num[i])==0) return sg[sta]=1;//搜索枚举去掉哪个棋子(1个); 
for(int j=last[i];j;j=next[j])
if(num[to[j]]&sta)
if(mex(sta-num[i]-num[to[j]])==0) return sg[sta]=1;//SG性质,如果上一个
            //状态时先手必败,那么从那处过来必定是先手必胜;但反过来不一定(取第二个) 
}
return sg[sta]=0;//所以这边若所有必败到必胜的情况都没有,那么这个只能必败; 
}
int main(){
    //freopen("chess.in","r",stdin);
    //freopen("chess.out","w",stdout);
scanf("%d\n",&T);
memset(sg,-1,sizeof sg);
addedge(1 ,4);
addedge(3 ,4);
addedge(2 ,5);
addedge(6 ,5);
addedge(7 ,8);
addedge(11,8);
addedge(10,9);
addedge(12,9);
addedge(4 ,5);
addedge(5 ,9);
addedge(8 ,9);
addedge(8 ,4);//预处理12对相邻关系,建立边表关系; 
num[1]=1;
for(int i=2;i<=13;i++) num[i]=num[i-1]*2;//预处理2的i次方 
while(T--){
char d[100];
int sta=0;
scanf("%s",d);
for(int temp=1,i=0;i<12;i++)
if(d[i]=='1') sta+=num[i+1];//转化成二进制数sta 
if (mex(sta)==1)//DFS
printf("0");
else printf("1");
}
printf("\n");
return 0;
}
2.RZZ给我做的一题:N一开始是1,M是输入的数,每次NIC(人名)可以乘以2-9的数,而CINA也可以乘以2-9的数,NIC是先手,最后乘到N>=M的人先赢问谁有必胜策略。         
怎么做呢?就按照总结的思路, 首先N为1-9的数都是先手必胜,那我们要开始从必胜状态推必败状态了:要多种情况才推才行,所以我们思考,哪些大于9数除以2-9得到的值都在1-9这些必胜范围内,可以发现时10-18。19的话除以2就大于9。再从10-18这些必败状态开始推:他们中任意一个只要*2-9就能推到必胜状态了,所以10*2(下限)-18*9上限的这些数都是必胜状态,当然19也是必胜状态,因为20》19,类似的,我们得到一个朴素博弈算法:
 初始1-9为必胜,i=1,j=9(下限和上限)下一个就是i=j+1;j=j*2;再下一个就是i=j+1;j=j*9;归纳起来就是不断*9*2,这道题就轻松解决了!
  评论这张
 
阅读(83)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018