【题解】洛谷 P5932 [POI1999]多边形之战

wsyhb · 2022-02-09 12:15:28 · 题解

题解

首先，如果你画几个多边形来手玩，你会发现如下结论：

结论一：对于凸多边形中的任意一个三角形及它的任意一边，要让这个三角形的这条边成为操作后多边形的某边，必须删除这个三角形这一侧的其它所有三角形。

文字可能不是那么容易理解，下面举例说明：

如上图，这个 12 边形包含 10 个三角形，其中的红色数字表示它们的编号。

用 T_i 表示第 i 个三角形，那么要让 T_4 的 m_1 这条边成为操作后多边形的某边，必须删除 T_1,T_2 和 T_3；要让 T_4 的 f_1 这条边成为操作后多边形的某边，必须删除 T_6,T_7,T_8,T_9 和 T_{10}；要让 T_4 的 j_1 这条边成为操作后多边形的某边，必须删除 T_5。

是不是感觉这个结论很显然？不过还是要给出证明的：

设多边形边数为 n，容易验证 n=3,4,5 时结论一成立。
假设 n<k(k \ge 6) 时结论一成立，下证 n=k 时结论一仍然成立。

对于有两边都是整个多边形的边的三角形，结论一显然成立。

对于有至少两边都不是整个多边形的边的三角形 X，设它的三边分别为 a,b,c，且 a,b 都不是整个多边形的边。
（换句话说，a,b 这两侧都有其它三角形）
那么要使 a 成为操作后多边形的某边，必须删除以 a 为边的另一个三角形 Y。

考虑如何在删除三角形 Y 的同时不删除三角形 X：这相当于不能完全删除 Y 的 a 边另一侧（即包含三角形 X 的这一侧），于是包含三角形 X 的这一侧的部分可以被等效替换为一个单独的三角形 Z，而 Z 不能被删除。

等价替换后总的三角形个数变少了，于是多边形的边数也由 n=k 降到了 n<k。
根据归纳，要删除 Y（即让 Y 除 a 以外的两边成为多边形的边），必须删掉除 Y,Z 以外的所有三角形。
即结论一对于 X 的边 a 成立。
同理可证 X 的边 b,c 成立。

根据归纳，结论一对任意多边形的任意三角形的任意边成立。

回到原题，设黑色三角形每一侧的三角形个数分别为 x,y,z，那么问题转化为：

给定三堆石子，数量依次为 x,y,z。
两人轮流操作，每次选取一堆石子并从其中取走一颗。
当三堆石子中有至少两堆石子为空时，游戏结束。
进行最后一次操作的人失败。

说明：当黑色三角形有至少两边为多边形的边时，当前玩家把黑色三角形删除即可取得游戏的胜利。故造成这种局面的玩家失败。

我想到这儿的第一反应：直觉上，局面的胜负与 x,y,z 的奇偶性有关。（因为每次只取一颗石子）

但我并不是很确定具体结论，于是写了个程序打了下 x,y,z \le 10 的胜负状态：

（其中 \mathit{val}=0 表示该局面必败，\mathit{val}=1 表示必胜；程序见剪贴板）

这规律简直不要太明显：当 x+y+z 为偶数时必败，反之必胜。

更严谨地，我们有如下结论：

结论二：

当 x,y,z 中有至少 2 个 0 时，该局面必胜。
否则，该局面必胜当且仅当 x+y+z 为奇数。

证明：

1 显然，故接下来考虑 x,y,z 中有至多 1 个 0 的情况。
由于必存在某一时刻某堆石子被取空（或一开始就没有），故可以考虑只剩两堆石子 y,z(y,z>0) 的情况。

除非万不得已，玩家一定不会把这两堆石子中的某一堆取空。
即：除非 y=z=1，玩家一定不会把 y,z 中的任意一个变为 0。
这意味着最终的局面一定是 (0,0,1)（要操作该局面的玩家获得胜利）。
即：最终，不为空的这堆石子个数为 1。

而每次操作都会改变 x+y+z 的奇偶性，故 x+y+z 为奇数的局面必胜。

如何求 x,y,z 呢？
设黑色三角形三点编号为 a,b,c(a<b<c)，则 x 为三点编号均在 [a,b] 中的三角形个数，y 为三点编号均在 [b,c] 中的三角形个数，剩余三角形的个数即为 z。
（x,y,z 的顺序显然不影响答案）

于是这道题就做完了。

~~过程比较简单，但却写了一大堆，好累啊。~~

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,c;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    if(a>b)
        swap(a,b);
    if(a>c)
        swap(a,c);
    if(b>c)
        swap(b,c);
    int x=0,y=0,z=0;
    for(int i=1;i<=n-3;++i)
    {
        int p,q,r;
        scanf("%d%d%d",&p,&q,&r);
        if(p>=a&&p<=b&&q>=a&&q<=b&&r>=a&&r<=b)
            ++x;
        else if(p>=b&&p<=c&&q>=b&&q<=c&&r>=b&&r<=c)
            ++y;
        else
            ++z;
    }
    int cnt0=(x==0)+(y==0)+(z==0);
    if(cnt0>=2)
        puts("TAK");
    else if((x+y+z)&1)
        puts("TAK");
    else
        puts("NIE");
    return 0;
}