[博弈论]HDU 1517


http://acm.hdu.edu.cn/showproblem.php?pid=1517

题目大概意思是:先给出个数字1,然后第一个人乘以2到9中的一个数,第二个人将得到的数再乘以2到9中的一个数,轮流下去,直到其中一个人乘后超过给定的数n,则他win.

就是找必败态
>=162为p
(162/9)18——161为N 想要进入必败态你就赢了,所以范围大
(17/2)9——17为P 进入N必胜态你就输了,玩家没办法才要进入,所以范围小
(8/9)1——8为N
—————————
这题其实不是求必败点,必胜点,而是求必败段,和必胜段,经过推敲后发现转换下就变成求必败,必胜段的左届,比如162,那很明显>=162/9的都是必胜点,那由博弈的思想得到,任意一步都进入必胜点的是必败点,那又很明显这个值处以2的那一段都是必败点,然后再根据博弈的思想,通过一步能进入必败点的必是必胜点,那很明显这个值再除以9的明显又是必胜点,如此往复,不断的处于2和9然后做个标记就能知道必败点和必胜点了,只要注意界限问题

—————————

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i=1,t=n,add;
        while(t!=1)
        {
            if(i%2==1)
            {
                if(t%9>0) add=1;
                else add=0;
                t/=9;
                t+=add;
            }
            else
            {
                if(t%2>0) add=1;
                else add=0;
                t/=2;
                t+=add;
            }
            i++;
        }
        if(i%2==0) printf("Stan wins.n");
        else printf("Ollie wins.n");
    }
    return 0;
}

发表评论