admin 管理员组

文章数量: 1086019

博弈

hud6850 Game

实验室dalao的思路，本菜鸡比赛都是在想些假思路，给orz了

题意：
在直角平面坐标系中n个坐标，两个人博弈，从第一个点开始跳到其他的点上，每个点只能被经过一次，且 “一个点到下个点的距离” 要大于 “这个点到上一个点的距离” 才能跳。两人轮流跳，最后谁不能再跳了谁就输了，先手赢输出“YES"，后手赢输出“NO”。

思路：
给每个点标号1 ~ n，n个点建完全图有n * (n - 1) / 2条边，每条边按距离权值从大到小排序，每次选择当前距离最大且未标记的边标记为真，与真边直接相邻且为标记的边标记为假边，直到所有边标记完，检查1号点所有边中是否有真边，有就是先手赢，没有就是后手赢。
论证：
1、这里有点贪心的味道，因为每次跳跃只能跳向距离更大且未经过的点，我们把每轮标记的真边和真边所属的假边划分为一个集合，直到所有的边划分完，无论先手后手，只要到了真边那他就赢了，因为下一个人已经无路可走了。
2、按集合的划分规则我们可知真边和假边的连接情况，假边和真边是交替出现的，每条假边都至少与一条真边相连，如果先手一开始不能通过真边跳跃，那就会出现两种情况：
（1）后手就直接跳过真边，且该真边没有距离比他大与他相连的假边（这种距离比 他的的假边是属于前面集合的假边）先手就无路可跳了。
（2）后手直接跳过真边，但与该真边有距离比他大与他直接相连的假边（别的集合内的假边），先手是可以跳跃的，但后手就会跳过该假边的集合内的真边，每一轮后手都有路走，先手不一定有。最终先手会无路可走。

code：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
pair<int, int> pi[maxn];
int mp[maxn][maxn];
int cnt;
struct edge{int u, v;double w;bool operator < (const struct edge& a) const {return w > a.w; }} g[maxn * maxn];void add(int u, int v, pair<int, int> a, pair<int, int> b) {g[cnt].u = u;g[cnt].v = v;double w = 1.0 * (a.first - b.first) * (a.first - b.first);w += 1.0 * (a.second - b.second) * (a.second - b.second); g[cnt++].w = sqrt(w); 
}void init(int n){cnt = 0;memset(mp, -1, sizeof(mp));
}int main(){int t, n;scanf("%d", &t);while(t--) {scanf("%d", &n);init(n);for(int i = 1; i <= n; i++) scanf("%d %d", &pi[i].first, &pi[i].second);for(int i = 1; i < n; i++)for(int j = i + 1; j <= n; j++){add(i, j, pi[i], pi[j]);}sort(g, g + cnt);for(int i = 0; i < cnt; i++){int u = g[i].u, v = g[i].v;if(u > v) swap(u, v);if(mp[u][v] == -1){mp[u][v] = 1;  //1为真边，0为假边，以真边为集合中心，标记与他相连的假边for(int j = 1; j <= n; j++){if(j == u || j == v) continue;int x = u, y = j;if(x > y) swap(x, y);if(mp[x][y] == -1) mp[x][y] = 0;}for(int j = 1; j <= n; j++){if(j == v || j == u) continue;int x = v, y = j;if(x > y) swap(x, y);if(mp[x][y] == -1) mp[x][y] = 0;}}}bool flag = true;for(int i = 2; i <= n; i++)if(mp[1][i] == 1) {flag = false;break;}if(flag) printf("NO\n");else printf("YES\n");}}

本文标签： 博弈

版权声明：本文标题：博弈 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699469264a357449.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。