当前位置： 移动技术网 > IT编程>开发语言>C/C++ > P1288 取数游戏II

P1288 取数游戏II

2018年08月20日  | 移动技术网IT编程  | 我要评论

逆转三国维基,泰兴租房网,青岛市长张新起

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;
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网