2020 Multi-University Training Contest 7

http://acm.hdu.edu.cn/contests/contest_show.php?cid=885

1007 - Game

题意：二维平面上给定 n 个点，要求从第一个点开始移动到任意一个没有到过的点，并且移动的距离要比上一次远。两个人轮流操作，不能移动的输，问先手能否赢。

博弈

做法一：直接dfs记忆化搜，其实不需要记录vis过的点，也就是说“不能走到走过的点”这个限制是假的。

假设之前 A 走到过 j，现在 B 由 i 又走到 j，下一步由 A 来操作。

如果此时 A 没法移动了，那么当 A 第一次在 j 点时，A 就可以移动到 i，也就限制了 B 不能再走到 j 了，也就相当于这样的困境不会出现。

而如果此时 A 可以移动，假设 A 走到了 k，那么 A 完全可以在第一次到 j 时直接走到 k。

如果是由 A 从 i 走到 j，那么是否进行这个操作的决定权还是在于 A。

也就是说，能否走重复点并不会增大或减小每个人对局面的主动性。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
const double eps = 1e-5;
int T;
bool same(double x, double y) { return abs(x - y) < eps; }
int n;
double x[N], y[N];
double dist(int i, int j) {
    return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}
int dp[2010][2010];
bool dfs(int u, int v) {
    if (~dp[u][v])return dp[u][v];
    for (int i = 1; i <= n; i++) {
        if (dist(v, i) - dist(u, v) <= eps)continue;
        if (dfs(v, i)) {
            return dp[u][v] = 0;
        }
    }
    return dp[u][v] = 1;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf", &x[i], &y[i]);
        }
        memset(dp, -1, sizeof(dp));
        bool flg = 0;
        for (int i = 2; i <= n; i++) {
            if (dfs(1, i)) {
                flg = 1;
                break;
            }
        }
        puts(flg ? "YES" : "NO");
    }
    return 0;
}

做法二：

第一种做法总还是感觉证明理解起来不太舒服，所以还是推荐第二种。很妙的构造方法。

找到图上所有相距最远的点，从图上删掉。再重复。直到最后没有点了，或者只剩一个点。如果只剩一点，且该点是第一个点，则先手败，否则先手胜。

这样操作会把所有点按照从它出发的最远距离进行划分，如上图，在同一块里的所有点，从它出发的最长边长度相同。并且所有点只会出现在一块里。

可以发现，除了第一块可能只有一个点，其它所有块里至少有两个点。

设先手为黑色，后手为红色。

先手从 1 出发，如果 1 所在的块至少有两个点，则先手总是可以在块内移动，而由于下一次移动必须更远，而这一块里所有点不可能移动到更远的点了（否则它一定在后面某块），所以后手必须在块间移动，那么迟早后手会移动到最后一块，这时后手下一次就没法再移动了。

而如果 1 所在的块只有一个点，即 1 在第一块，且第一块只有一个点。那么先手不得不在块间移动，后手反而可以用上面的策略。

本题一方始终模仿另一方而始终不做出冒险行为，从而迫使另一方不得不做出改变而不得不冒险。如果能构造出这样的方案，就能得到正解。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
const double eps = 1e-5;
int T;
bool same(double x, double y) { return abs(x - y) < eps; }
int n;
double x[N], y[N];
double dist(int i, int j) {
    return sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
}
int vis[N];
typedef pair<int, int>pii;
vector<pii>vc;
double dis[2010][2010];
bool cmp(const pii& a, const pii&b) {
    return dis[a.first][a.second] > dis[b.first][b.second];
}
double t[N];
bool ck() {
    fill(vis, vis + n + 1, 0);
    for (pii p : vc) {
        if (!vis[p.first] || !vis[p.second]) {
            double d = dis[p.first][p.second];
            if (!vis[p.first] && !vis[p.second]) {
                vis[p.first] = vis[p.second] = 1;
                t[p.first] = t[p.second] = d;
            }
            else if (!vis[p.first]) {
                if (same(d, t[p.second])) {
                    vis[p.first] = 1;
                    t[p.first] = d;
                }
            }
            else {
                if (same(d, t[p.first])) {
                    vis[p.second] = 1;
                    t[p.second] = d;
                }
            }
        }
    }
    return vis[1];
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf", &x[i], &y[i]);
        }
        for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)dis[i][j] = dis[j][i] = dist(i, j);
        vc.clear();
        for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)vc.push_back(pii(i, j));
        sort(vc.begin(), vc.end(), cmp);
        if (!ck())puts("NO");
        else puts("YES");
    }
    return 0;
}