P1288 取数游戏II
2018-08-21 05:28:25来源:博客园 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言实现经典游戏——扫雷! 2020-04-17
- 用C++实现:回形取数 2020-03-25
- 小游戏二之---------------五子棋 2020-03-23
- Qt5小Demo之猜数字游戏 2020-03-19
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash