其实我觉得这道题的处理挺巧妙的……想了好久才想出来
反正还是被 tly 给秒了 wtcl :(
# 题面
> HDU 6850
点击展开/折叠题面翻译
在二维平面上给定 $n$ 个点，一开始有一个石头在点 $1$。
先后手轮流操作，每次操作将石头移动到一个之前没有到过的点，且要求移动的欧几里得距离严格大于上一次移动（如果是第一次移动则视“上一次移动”距离为 $0$）。
不能移动的人输，问先手是否有必胜策略。
# 解析
发现很难找到必胜策略，但是可以很明显地找到两个结论，称相距最远的两个点为“直径”（可能有多个）：
- 如果点 $1$ 是直径的一个端点，则先手必胜，可以直接走直径，后手就不可能找到更远的点；
- 若点 $1$ 不在直径上，则先后手在任意时刻都“不愿意”走到直径上的点，若走到直径上的点，对手就可以走直径从而获胜。
先判断第一个结论，然后再看第二个结论。既然先后手的最优策略都不会想往直径上的点走，那就是说我们把当前直径上的点都删去，对先后手的最优策略以及NP状态都不会影响。
于是删去直径上的点（注意如果有多个相等的直径，要一起删去），就得到了一个子问题。对这个子问题再求直径，仍然判断两个结论，若满足结论2，则删去当前直径继续得到子问题……
什么时候会结束？
- 点 $1$ 变成当前直径的端点，先手必胜；
- 删的只剩 $1$ 这个点，后手必胜；
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int Ri(){
register int r=0,c=getchar(),b=1;
while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
return r*b;
}
const int N=2005;
typedef long long ll;
int cas,nedg,n,nstk;
ll pnt[N][2];
int stk[N*2];
bool del[N];
struct EDGE{
ll dis;
int x,y;
EDGE(){}
EDGE(int X,int Y){
x=X,y=Y;
dis=(pnt[X][0]-pnt[Y][0])*(pnt[X][0]-pnt[Y][0])+(pnt[X][1]-pnt[Y][1])*(pnt[X][1]-pnt[Y][1]);
}
friend bool operator <(const EDGE &a,const EDGE &b){return a.dis>b.dis;}
}edg[N*N];
int main(){
cas=Ri();
while(cas--){
n=Ri();
for(int i=1;i<=n;i++) pnt[i][0]=Ri(),pnt[i][1]=Ri(),del[i]=false;
nedg=0;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
edg[++nedg]=EDGE(i,j);
sort(edg+1,edg+1+nedg);
for(int i=1,j;i<=nedg;i){
for(j=i;j<=nedg && edg[i].dis==edg[j].dis;j++){
if(del[edg[j].x] || del[edg[j].y]) continue;
stk[++nstk]=edg[j].x,stk[++nstk]=edg[j].y;
}
i=j;
while(nstk) del[stk[nstk--]]=true;
if(del[1]) break;
}
if(del[1]) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
THE END
Thanks for reading!
> Linked 夏夜空-网易云