题目描述
给你n个节点的凸包(未连线),每次选择两个点连一条线,不能与之前出现的线有相交。当出现一个凸包的时候游戏结束
谁最后无法移动了就输了,现在问 是先手必胜还是后手必胜。
HDU描述的是当出现一个三角形时 游戏结束。其实是一个意思,HDU的范围大一点 涉及循环节。
做法:SG函数。如果你是第一次听说SG函数。看链接:知乎
而对于这题的分析呢。
每一个点集都可以被一条直线分割成一个包含两部分的子局面,根据SG函数从前往后推
那么对于当前局面SG(x),它的后继局面为 任选两个点连接后,得到的局面是被该线分割成两部分,如果下一个人在这条线的两个端点任意一个出发再连一条线,则下下个人就可以连成三角形使得游戏结束,因此下一个人必不会再从这两个端点连线。因此后继局面为sg(i)与sg(x-i-2) [0<=i<=x-2]
即得到sg函数为: SG(X)=mex{sg(i)^sg(x-i-2)} [0<=i<=x-2]
对于GYM的这道题 直接推SG数组即可。
对于HDU 的打表找循环节
由于数据的n很大,打表出前1000项观察可以得到循环节。。。打表
代码参考来自:博客
/*
因为一条直线把当前局面分割成两个子局面,
i-2是连接完直线后剩下的点,所以两个子局面的异或就是sg[j]^sg[i-2-j]
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
int sg[maxn],s[maxn];
void SG()
{
sg[1]=0,sg[2]=1;
for(int i=3;i<=5000;i++){
memset(s,0,sizeof(s));
for(int j=0;j<=i-2;j++) //所有子局面
s[(sg[j]^sg[i-2-j])]=1;
for(int j=0;;j++){
if(!s[j]){
sg[i]=j; break;
}
}
}
}
int main()
{
SG();
int t; scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
if(sg[n]) puts("First");
else puts("Second");
}
return 0;
}
HDU 题 代码参考:博客
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 1000 + 10;
int vis[MAXN];
int SG[MAXN];
int mex(int x)
{
if(SG[x] != -1)
return SG[x];
memset(vis, 0, sizeof(vis));
for(int i=0;i<=x-2;i++)
vis[mex(i) ^ mex(x-2-i)] = 1;
for(int i=0;;i++) if(!vis[i])
{
SG[x] = i;
break;
}
return SG[x];
}
int main()
{
memset(SG, -1, sizeof(SG));
for(int i=0;i<200;i++)
SG[i] = mex(i);
int T;
scanf("%d", &T);
while(T--)
{
int n, x;
scanf("%d", &n);
int ans = 0;
for(int i=0;i<n;i++)
{
int x;
scanf("%d", &x);
if(x < 100) ans ^= (SG[x]);
else
{
x -= 60;
x %= 34;
ans ^= SG[x + 60];
}
}
if(ans) printf("Carol\n");
else printf("Dave\n");
}
return 0;
}