题目链接

P1290 and UVA10368 （双倍经验【虽然标签差距很有趣】）

题目大意

给定两个数\(n\)和\(m\)，每次操作可以用较大数减去较小数的正整数倍，不可以减成负数。

先获得一个\(0\)的人获胜，问先手是否必胜。

\(n,m \leq 2^{31}-1\)

多组数据。

Solution

一眼博弈论题吧2333

\(SG\)函数和递归操作应该是摆在眼前的

先记较大数为\(n\)，较小数为\(m\)

三种情况：

1.如果当前态的\(n\)和\(m\)中有一个已经是\(0\)了

显然\(SG(now)=0\)，这个人一定输了

2.如果\(n\)已经是\(m\)的倍数

一步操作就可以获胜，\(SG(now)=1\)这个人一定赢了

（上两个都是终止态）

3.\(SG(n,m)=SG(n\space mod \space m,m)\)

这里需要理解一下:

我们假定我们要让这个式子成立

\[SG(n,m) \rightarrow SG(n-k \times m,m)
\]

通过控制\(k\)的大小进行博弈，可以使得

\[SG(n \space mod \space m,m)= SG(n,m)
\]

得证（其实对于“通过控制\(k\)的大小进行博弈”感性理解一下吧，具体过程不展开了）

CODE

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm {

inline int read() {

    int res = 0, f = 1;

    char k;

    while (!isdigit(k = getchar()))

        if (k == '-')

            f = -1;

    while (isdigit(k)) res = res * 10 + k - '0', k = getchar();

    return res * f;

}

inline bool work(int n, int m) {

    if (!m)

        return 0;

    if (n/m == 1)

        return !work(m, n % m);

    return 1;

}

signed main() {

	int x,y;

    while (1) {

        x = read();

        y = read();

        if(x==y&&y==0) break;

        if (work(max(x, y), min(x, y)))

            puts("Stan wins");

        else

            puts("Ollie wins");

    }

    return 0;

}

}  // namespace yspm

signed main() { return yspm::main(); }

(可以发现这段代码是在\(Libre\) \(OJ\)上格式化过的吧2333)

总结

博弈论题要考虑完整情况，对于有些子问题可以先手动博弈一下，就会迎刃而解了

巴特西

LGOJ1290 欧几里德的游戏

题目链接

题目大意

Solution

CODE

总结

最新文章

热门文章