P1288 取数游戏II

2018-08-21 05:28:25来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

luogu原题

最近刚学了博弈论,拿来练练手qwq

其实和数值的大小并没有关系

我们用$N/P$态来表示必胜/必败状态

先在草稿纸上探究硬币在最左侧(其实左右侧是等价的)的一条长链的$N/P$态,设链长为$n$

我们用$1$代替其他所有非$0$数

$n=2: 11$  $N$态

$n=3: 111$ $P$态

......

我们发现,当$n$为奇数时,则为$P$态,反之为$N$态。

于是我们就找到了硬币在最左侧时的答案。

但是,实际上硬币并不一定在最左侧

此时我们只需要分别判断硬币左边的链和硬币右边的链,只要有一种为$N$态,则Alice赢,反之Bob赢(双方都会选择最优走法)。

代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
int a[43],n,l=1,r=1; //记得要算上硬币所在的点
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[n+i]=a[i];
    for(int i=n;a[i];--i) ++l; //左侧判断
    for(int i=n+1;a[i];++i) ++r; //右侧判断
    if((l&1)&&(r&1)) printf("NO"); //任何一个为奇数则Alice赢
    else printf("YES");
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hdu-2553 N皇后问题(搜索题)

下一篇:hdu-1338 game predictions(贪心题)