HDU-6850 (Game)

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6850

如果感觉不适请前往 [https://vagrantac.info/2020/08/12/杭电多校/HDU6850 Game/](https://vagrantac.info/2020/08/12/杭电多校/HDU6850 Game/)

题解

我使用的是标程的第二种解法，和当时在训练的想法是一样的，

首先简述一下我的想法，

以下直接忽略一个点不能走多次

使用数组 (dp[x][y]) 表示当前位置为 (x) 点，上一步为 (y) 点状态，(0) 表示必败态，(1) 表示必胜态。

也可以将 (x) 到 (y) 看作是一条边， (0) 表示走 (x) 到 (y) 这条边为必败态，否则为必胜态。

之后使用记忆化搜索进行搜索一下，

如果一条边 (x) 到 (y) 中 (y) 下一步没有点可走的话表示这个状态为必败态。

对于一个状态，如果它的下一个可以到达的所有的状态中存在必败态，(namo) 这个状态为必胜态，

否则为必败态。（关于必胜态和必败态，详细可以看一下博弈论）

下面是证明一下

这个题我上面的解法会有一个问题，就是出现环怎么办。

环的话，分类考虑一下就好了

如果 (dp[x][y]) 存在下一步状态并且存在 (z) 使得 (dp[y][z] = 0) ，那直接走这条边就好了，不需要考虑其他边，并且保证了必胜态了。

否则的话对于所有的 (z) 保证 (dp[y][z] = 1) ，那到达这个位置的时候注定了必败态了。

这个问题证明很简单，当然也是我第一次手推证明，之前的都是盲猜和结论题，推就完事了。

代码

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 2e3+55;
typedef long long ll;
ll cost[M][M];
int dp[M][M];
ll x[M], y[M];
int n;
int dfs(int xx, int yy) {
    if (dp[xx][yy] != -1) return dp[xx][yy];
    int b = 0;
    for (int i = 0; i < n; ++ i) {
        if (i == yy) continue;
        if (cost[yy][i] > cost[xx][yy]) {
            if (dfs(yy, i) == 0) {
                dp[xx][yy] = 1;
                return 1;
            }
            else b ++;
        }
    }
    dp[xx][yy] = 0;
    return dp[xx][yy];
}
int main() {
    int t;
    scanf("%d", &t);
    while (t --) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++ i) {
            scanf("%lld%lld", &x[i], &y[i]);
        }
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                cost[i][j] = (x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]);
                dp[i][j] = -1;
            }
        }
        int a = 0, b = 0;
        for (int i = 1; i < n; ++ i) {
            if (dfs(0, i) == 0) {
                a ++;
                break;
            } 
            else b ++;
        }
        if (a) printf("YES
");
        else printf("NO
");
    }
    return 0;
}

新赛季的开始