杭电多校第七场 1007 Game 题解

题目大意

给你n个点，你需要从第一个点开始，先任意选择一个点，之后每次需要移动比之前的距离更远，且这个点没有被使用过，a先手，b后手，a和b都采用最佳策略，如果不能移动则算输，求a是否能取胜。

解题思路

这博弈太难了。。

我们先可以按照边的大小来排序。

按照不同的边的大小，从大到小把点可以分到不同的集合。

按照能组成边的大小，能够构成一个点集。

如果第一个点在最后一个集合，且最后一个集合只有第一个点，则a必输。

否则a必赢。

如果第一个点不在最后一个集合或者集合不止一个数，则先手可以选择同集合的，而后手只能跨集合，则最后后手则会没有集合可以选，就必赢。

如果第一点在最后一个集合且只有一个数，则相当于先手需要不断的跨集合，后手选择同集合，则必输。

第一个点在最后一个集合，则说明能与他构成边的点之前都被用过了，导致第一个点被剩下了。

那我们只需要从大到小枚举所有的边，如果枚举到的边都没被标记，则将两点标记，如果这条边包含了第一点，则必胜。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2020;
int vis[N];
struct n {
	int x, y;
}node[N];
typedef struct{
	int a, b;
	ll val;
}s;
vector<s> v;

ll dis(n a, n b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int cmp(s a, s b) {
	return a.val > b.val;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) {
			vis[i] = 0; cin >> node[i].x >> node[i].y;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++)
				v.push_back({ i,j,dis(node[i],node[j]) });
		}
		sort(v.begin(), v.end(), cmp);
		int flag = 0;
		for (auto x : v) {
			s t = x;
			if (vis[t.a] || vis[t.b]) continue;
			vis[t.a] = vis[t.b] = 1;
			if (t.a == 1 || t.b == 1) {
				flag = 1;
				break;
			}
		}
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}