题目链接:Click
here~~
这两天看了下博弈,整理下思路吧。
先引入必胜点和必败点两个概念:
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。
必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
对于这两个概念的描述,我开始的时候也搞不懂。
其实可以从字面理解,简单说来,就是当你走到某一点的时候,如果你无论怎么走也不能赢对方,此时你必败,这个点就叫做必败点。
算法实现:
步骤1:将所有终结位置标记为必败点(P点);(终结位置指的是不能将游戏进行下去的位置)
步骤2:将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
步骤4:如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。
好了,下面通过这道题来理解下吧。
题意:
你和一个人玩游戏,给你一个数字n,每次操作可以从2~9中任选一个数字,并把它与p相乘,(游戏开始时p=1)
两人轮流操作,当一个人操作完后p>=n,这个人就是胜者。
解题思路:
由于每次都是从p=1开始的,所以只要判断每个游戏中1为必败点还是必胜点即可。(以下各式 / 均为取上整)
依照上面所提到的算法,将终结位置,即[n,无穷]标记为必败点;
然后将所有一步能到达此必败段的点标记为必胜点,即[n/9,n-1]为必胜点;
然后将只能到达必胜点的点标记为必败点,即[n/9/2,n/9-1]为必败点;
重复上面2个步骤,直至可以确定1是必胜点还是必败点。
#include <math.h>
#include <stdio.h>
int main()
{
unsigned int n,x;
while(~scanf("%u",&n))
{
for(x=0;n>1;x++)
{
if(x&1)
n = ceil(n*1.0/2);
else
n = ceil(n*1.0/9);
}
puts(x&1?"Stan wins.":"Ollie wins.");
}
return 0;
}
分享到:
相关推荐
ACM HDU 1404 Digital Deletions(博弈).docx
杭电ACM课件2014版之(HDUACM201403版_12)组合博弈入门
杭电的组合博弈课件与oj题目详解,ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate ProgrammingContest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队...
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDUACM201303版_10搜索入门
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM ...(lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
很好很经典的组合博弈的讲义,HDU 大家下来看看很好
博弈初学者可以试一下,里面是HDU的可见ppt
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
很适合ACM初学者的文档, 题目,代码,解体思路一应俱全
涵盖注册、入门的十题答案,适合刚刚接触hdu的同学。
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
杭电组合博弈课件