HDU1517 A Multiplication Game(博弈)

题目链接。

题意：

两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。

分析：

如果是加法就好做了。凑到剩下的数能整除11，然后对称着加。问题是乘法。

所以寻找必胜点（段）。以1000为例。

1000 | 999 ... 112 | 若占住999到112，则对手必胜。必须让对手占领此段。

1000 | 999 ... 112 | 111 ... 56 | 因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。

如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1

AC代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long  LL;

int main() {
    LL n;
    while(cin >> n) {
        int cnt = 0;

        while(n > 1) {
            cnt++;
            if(cnt & 1) {
                n = (n-1)/9+1;
            } else {
                n = (n-1)/2+1;
            }
        }

        if(cnt & 1) cout << "Stan wins.\n";
        else cout << "Ollie wins.\n";
    }

    return 0;
}

View Code

上面是将必胜区间、必败区间，分别讨论，下面的思路就更神奇了。

如果输入是 2 ~ 9 ，因为Stan 是先手，所以Stan 必胜
如果输入是 10~18 ，因为Ollie 是后手，不管第一次Stan 乘的是什么，Stan肯定在 2 ~ 9 之间，
如果Stan乘以 2 ，那么Ollie就乘以 9 ，就到18了，如果Stan乘以 9 ，
那么Ollie乘以大于1的数都都能超过 10 ~ 18 中的任何一个数。Ollie 必胜
如果输入是 19 ~ 162，那么这个范围是 Stan 的必胜态
如果输入是 163 ~ 324 ，这是又是Ollie的必胜态
............
必胜态是对称的！！！
如果＂我方＂首先给出了一个在Ｎ不断除１８后的得到不足１８的
数Ｍ，＂我方＂就可以取得胜利，然而双方都很聪明，所以这样胜负就决定于Ｎ了，如果Ｎ不断除
１８后的得到不足１８的数Ｍ，如果１＜Ｍ＜＝９则先手胜利，即Stan　wins．如果９＜Ｍ＜＝１８
则后手胜利．

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long  LL;

int main() {
    LL n;
    while(cin >> n) {

        while(n > 18) { //对手最大可以从9开始操作
            n = (n-1) / 18 + 1;
        }

        if(n <= 9) cout << "Stan wins.\n";
        else cout << "Ollie wins.\n";
    }

    return 0;
}

View Code

第一个分析摘自 http://www.cnblogs.com/lonelycatcher/archive/2011/08/20/2147430.html

第二个分析摘自 http://www.cnblogs.com/kuangbin/archive/2011/08/29/2158581.html