多边形之战

Time Limit:1 SecMemory Limit:128 MB

Submit:Solved109:73

[Submit][Status][Discuss]

多边形之战是一款双人游戏。游戏是在一个有n个顶点的凸多边形上进行的。这个凸多边形的n-3条对角线将多边形分为n-2个三角形，在多边形的顶点相交。三角形中的一个被染成黑色，其余是白色。双方轮流玩游戏，轮到一方时，他必须沿着画好的对角线，从多边形上切下一个三角形。切下黑色三角形的一方获胜。

注:如果连接多边形中任何两点的线段完全包含在这个多边形中，则称为凸多边形。

求解任务：

请设计程序：

·读入对多边形的描述。

·确定先走的一方能否获胜。

·输出结果。

第一行是整数， 4 <= n <= 50000。表示多边形顶点数，多边形顶点顺时针从0到n-1。然后N-2行描述形成多边形三角形。第i+1行， 1 <= i <= n-2.分隔三个空间的非负整数a、 b、 c，它们是第一个三角形的顶点号。第一个给出的三角形是黑色的。

唯一的行应该包含一个单词：

TAK(波兰文“是”)，说明先走的一方有必胜策略，或者说

NIE(波兰文“否”)，说明先走的一方没有必胜策略。

6 0 1 2 2 4 3 4 2 0 0 5 4

TAK

有邻近的多边形连接，问题变成了一棵树，有一个节点是黑色节点，每次删除一个叶节点，可以删除黑色节点赢得黑色节点作为根，如果黑色节点只有一个儿子，第一手必须赢①只有三点，一个黑色节点只有两个儿子。如果你先输，你必须先输②假如节点再多，而且黑色节点有两个以上的儿子，那么假如有奇数的白点，先手一定能删除先手必败的情况②，如果先手必胜有偶数白点，后手一定能删除先手必败的情况②，先手必败

谁让你的博客写得这么好，我就转载~~

出处：膜力传送门

粘上别人家的代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 50005int n,x,y,z,cnt,son;int f[N];struct hp{int x,y,id;}e[N*3];int cmp(hp a,hp b){    return a.x<b.x||(a.x==b.x&&a.y<b.y);}int find(int x){    if (x==f[x]) return x;    f[x]=find(f[x]);    return f[x];}int main(){    scanf("%d",&n);    for (int i=1;i<=n-2;++i)    {        scanf("%d%d%d",&x,&y,&z);        if (x>y) swap(x,y);        if (y>z) swap(y,z);        if (x>y) swap(x,y);        e[++cnt].x=x,e[cnt].y=y,e[cnt].id=i;        e[++cnt].x=y,e[cnt].y=z,e[cnt].id=i;        e[++cnt].x=x,e[cnt].y=z,e[cnt].id=i;    }    sort(e+1,e+cnt+1,cmp);    for (int i=1;i<=n-2;++i) f[i]=i;    for (int i=2;i<=cnt;++i)        if (e[i-1].x==e[i].x&&e[i-1].y==e[i].y&&find(e[i-1].id)!=find(e[i].id))        {            f[find(e[i].id)]=find(e[i-1].id);            if (e[i].id==1||e[i-1].id==1) ++son;        }    if (son<=1) puts("TAK");    else    {        if (n%2) puts("NIE");        else puts("TAK");    }}