HDOJ 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然后做个标记就能知道必败点和必胜点了，只要注意界限问题

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int main( )
 8 {
 9     int N;
10     while( scanf("%d",&N) != EOF )
11     {
12         bool fell,vis  = true;
13         while( N != 1 )
14         {
15            if( vis ) 
16            {
17                int add;
18                if( N%9 ) add = 1;
19                else      add = 0;
20                   N = N/9+add;
21                fell = true;
22                vis  = false;
23            }
24            else 
25            {
26                int add;
27                if( N%2 ) add = 1;
28                else      add = 0;
29                    N = N/2+add;
30                fell = false;
31                vis  = true;
32            }
33         }
34         if( fell ) printf("Stan wins.\n");
35         else       printf("Ollie wins.\n");
36     }
37     return 0;
38 }