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

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

HDU 3595 GG and MM 博弈  

2012-04-12 23:46:21|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=3595

题意是:MM和GG进行博弈游戏。一局游戏中有两堆石子,数目分别为a和b,可以从任意一堆中取另一堆石子数目的倍数个石子,谁无法取则这一局判负。MM和GG同时进行n局这样的博弈,每一回合都要对可以取石子的局进行拿取,谁无法拿取则负。MM和GG足够聪明,MM先取。

代码中写了自己的思想。总结一下就是延长自己的必胜局,加速结束自己的必败局。比赛时思路比较乱,虽然代码写得又臭又长,很多赘余,但压时间线过这道题還是挺开心的。

代码如下:

#include <stdio.h>
struct xx
{
    int bushu;
    int sf;  //sf=0代表MM输,1则赢    
}x[1001][1001];//定义结构体,bushu表示这一局走多少步可以结束,sf代表先走者的胜负

void init()
{
    int i,j,m,n,temp_bushu,temp_sf,flag,k,maxbs;
    x[0][0].bushu=0;//初始化 ,也可以不用初始化,i直接从0开始,比赛时比较紧张,没有思考这些
    x[0][0].sf=0;
    x[1][0].bushu=0;
    x[1][0].sf=0;
    x[1][1].bushu=1;
    x[1][1].sf=1;
    //x[2][0].bushu=0;
    //x[2][0].sf=0;
    for(i=2;i<1001;i++)
        for(j=0;j<=i;j++)
        {
             if(j==0)//只要有一个数据为0则bushu为0,胜负为负。
             {
                x[i][j].bushu=0;
                x[i][j].sf=0;       
             }              
             else
             {
                k=i/j;//k记录i,j之间的倍数关系
                m=i;
                maxbs=-1;//保留可走的最大步数
                while(k--)//因为先走的人有不同的选择,肯定会选令自己胜的方法走,所以查找x[i][*]中有无能走到并胜利的方法
                {
                      flag=0;
                      m-=j;                     
                      if(m<j)
                      {
                          temp_bushu=x[j][m].bushu+1;
                          if(x[j][m].sf==1)
                                 temp_sf=0;
                          else
                                 temp_sf=1;
                      }
                      else
                      {
                          temp_bushu=x[m][j].bushu+1;
                          if(x[m][j].sf==1)
                                 temp_sf=0;
                          else
                                 temp_sf=1;
                      }                     
                      if(temp_sf==1)//如果找到胜利的办法,则直接跳出循环
                      {
                          x[i][j].bushu=temp_bushu;
                          x[i][j].sf=temp_sf;
                          flag=1;
                          break;             
                      }
                      if(temp_bushu>maxbs)
                      {
                          maxbs=temp_bushu;                   
                      }
                }
                if(flag==0)//没有找到胜利的办法,则保留最大步数****(下面解释为什么要保留最大步数),胜负设0(负)
                {
                     x[i][j].bushu=maxbs;
                     x[i][j].sf=0;          
                }   
             } 
        }   
}

int main()
{
    int n,a,b,bs,max,win;
    init();
    while(scanf("%d",&n)!=EOF)
    {
       max=-1;
       win==1;
       while(n--)
       {
           scanf("%d%d",&a,&b);
           if(a<b)      //利用位运算,交换ab,使得a>b
               a^=b^=a^=b;
           bs=x[a][b].bushu;         
           if(bs>max)//max保留n局中走得最多步的局的步数,即回合数(以上步数都代表回合数)
           {
                max=bs;
                win=x[a][b].sf;            
           }          
       }
       if(win==1)//最后一个简单的判断
           printf("MM\n");
       else
           printf("GG\n");                         
    }
    return 0;   
}
//如果某人知道自己这一局必胜,那么肯定会利用最大的步数(回合数)来使这局持续时间更长。

  评论这张
 
阅读(184)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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