题解 P2252 【取石子游戏】

· · 题解

发一个考试中比较实用的做法。

对于mn <= 5000^2

首先针对nm比较小的情况，由于

    "必胜情况存在，当且仅当存在策略，使对手不存在必胜情况"

然后我们就得到了dp公式递推公式
时间复杂度O(mn)

对于更大的情况

70分做法

我们发现绝大多数情况都是可以必胜的，直接输出1
当然出题人不会这么轻易放过你的，所以只能拿70分

100分做法

我们把打的表格放出来，发现存在一个规律，即必败的点在两条直线上，而且经过原点，这就是规律。
至于为什么在两条直线上，是因为nm是可以互换的。
然后我们求出斜率的平均值，最后判断一下就好了。
判断的时候直接相等肯定是不行的，因为这是浮点数比较，还是我们估计的浮点数，所以我们需要一个eps。这个eps，可以用统计的方法算出来。

求斜率和eps

首先剔除n>m情况的数据
设k为我们的估计的斜率，有k=\sum \frac y x 然后有

eps = \frac {\sum |k'-k|} n

其中k'是实际的斜率
在|\frac nm - slope| <= eps的情况下，极大概率是必败的。当然也要考虑mn颠倒的情况。

源程序

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;

int n, m, vis_r[N], vis_c[N], vis_x[N << 1]; // x - y + N   exist 0

int G[N][N];

double slope = 1.618959789221876;
double eps = 3e-4;
int main() {
    scanf("%d%d", &n, &m);
    if(n < N && m < N)
    {
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                // val[i][j]
                if(!vis_r[i] && !vis_c[j] && !vis_x[i - j + N]) {
                    G[i][j] = 0;
                    vis_r[i] = vis_c[j] = vis_x[i - j + N] = 1;
                }
                else {
                    G[i][j] = 1;
                }
            }
        }
        cout << G[n][m] << endl;

    }
    else
    {
        if(abs(1.0*n/m - slope) <= eps || abs(1.0*m/n - slope) <= eps)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }

    return 0;
}