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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]A.Alice and Bob  

2011-11-09 12:22:33|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2011年成都赛区A题的题解。

这是一道博弈动规题目。

首先,我们把数字分成4类,1,,2,大于1的奇数,大于2的偶数。

一个大于3的奇数是等价于3的,因为,总可以对手减一个,你也减一个,就又变成了一个大于3的奇数或者3,总可以让它变成3。因此所有大于1的奇数都等价于3。同理,所有大于2的偶数等价于4。

所以我们用f[a][b][c][d]表示有a个1,b个2,c个3,d个4是不是一个必胜态,然后动规求解就好了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2011-11-09

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

bool calced[51][51][51][51];

bool f[51][51][51][51];

int F(int a,int b,int c,int d)

{

    if (!calced[a][b][c][d])

    {

       if (a>=1&&!F(a-1,b,c,d)) f[a][b][c][d]=true;

       if (b>=1&&!F(a+1,b-1,c,d)) f[a][b][c][d]=true;

       if (c>=1&&!F(a,b+1,c-1,d)) f[a][b][c][d]=true;

       if (d>=1&&!F(a,b,c+1,d-1)) f[a][b][c][d]=true;

      

       if (a>=2&&!F(a-2,b+1,c,d)) f[a][b][c][d]=true;

       if (b>=2&&!F(a,b-2,c,d+1)) f[a][b][c][d]=true;

       if (c>=2&&!F(a,b,c-2,d+1)) f[a][b][c][d]=true;

       if (d>=2&&!F(a,b,c,d-2+1)) f[a][b][c][d]=true;

      

       if (a>=1&&b>=1&&!F(a-1,b-1,c+1,d)) f[a][b][c][d]=true;

       if (a>=1&&c>=1&&!F(a-1,b,c-1,d+1)) f[a][b][c][d]=true;

       if (a>=1&&d>=1&&!F(a-1,b,c+1,d-1)) f[a][b][c][d]=true;

       if (b>=1&&c>=1&&!F(a,b-1,c-1+1,d)) f[a][b][c][d]=true;

       if (b>=1&&d>=1&&!F(a,b-1,c,d-1+1)) f[a][b][c][d]=true;

       if (c>=1&&d>=1&&!F(a,b,c-1+1,d-1)) f[a][b][c][d]=true;

      

       calced[a][b][c][d]=true;

    }

    return f[a][b][c][d];

}

 

int main()

{

    int TC;

    cin>>TC;

    for (int tc=1;tc<=TC;tc++)

    {

        int N,a=0,b=0,c=0,d=0;

        cin>>N;

        for (int i=0;i<N;i++)

        {

            int t;

            cin>>t;

            if (t==1) a++;

            else if (t==2) b++;

            else if (t%2==1) c++;

            else d++;

        }

        cout<<"Case #"<<tc<<": "<<(F(a,b,c,d)?"Alice":"Bob")<<endl;

    }

    return 0;

}

 

  评论这张
 
阅读(590)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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