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

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]取数游戏  

2015-08-07 17:13:57|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:博弈论。

Link&Limit


        [洛谷1288]  [codevs1037]
        时间限制:1000ms  空间限制:131072kb

Description


        有一个取数的游戏。初始时,给出一个环,环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后,将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏,两人轮流取数,取数的规则如下:
        (1)选择硬币左边或者右边的一条边,并且边上的数非0;
        (2)将这条边上的数减至任意一个非负整数(至少要有所减小);
        (3)将硬币移至边的另一端。
        如果轮到一个玩家走,这时硬币左右两边的边上的数值都是0,那么这个玩家就输了。
        如下图,描述的是Alice和Bob两人的对弈过程,其中黑色节点表示硬币所在节点。结果图(d)中,轮到Bob走时,硬币两边的边上都是0,所以Alcie获胜。
[题解]取数游戏 - TsReaper - TsReaper的博客
        现在,你的任务就是根据给出的环、边上的数值以及起点(硬币所在位置),判断先走方是否有必胜的策略。

Input Format


        第一行一个整数N(N≤20),表示环上的节点数。
        第二行N个数,数值不超过30,依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。

Output Format


        仅一行。若存在必胜策略,则输出“YES”,否则输出“NO”。

Sample Input #1


4
2 5 3 0

Sample Output #1


YES

Sample Input #2


3
0 0 0

Sample Output #2


NO

        由于至少有一个0,说明游戏是在一条链,而不是一个环上进行的。显然,一方如果路过一条边,必然会把边上所有的数取走,否则另一方可以原路返回。这样不管一方怎么走,另外一方总有退路可走,不是最优走法。
        既然已经知道游戏的胜负和边上的数值无关(只和是不是0有关),问题就变得简单很多了。如果出发点位于链的端点,那么若这条链有奇数条边,那么先手胜,否则先手负(大家可以自己画一画)。如果出发点位于链的中间,那么我们只要选择一个方向走一步,就变成了出发点在端点的问题。由此就可以得出答案。

#include <stdio.h>
int n,x[21];
int main()
{
int i,l,r;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&x[i]);
for(l=0;x[l+1];l++);
for(r=0;x[n-r];r++);
if((l&1)||(r&1)) printf("YES");
else printf("NO");
return 0;
}

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

历史上的今天

评论

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

页脚

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