5932 多边形之战

· · 题解

题意

n 个点的凸多边形，分成了 n-2 个三角形，

每次可以选择一个在边界上的三角形（有两条边裸露在外面），然后删除它。

第一个给出来的三角形是目标三角形，问先手能否保证自己先删到。

解法

可以发现我们只在意最终三角形裸露情况（有两边裸露就删除它），其他三角形如何删除不重要。

转化成三个数，每次选择一个减少 1 ，最后减少到形如 x,0,0 时的先手胜利。

首先判掉样例的情况，即已经有两边裸露。

尝试从奇偶性入手（三堆顺序无关），列出来下面一张表。

状态 胜负状态

100 必胜

111 必胜

110 必败

000 必败

最终胜利状态为 100 或者 000 ，但是 000 只有在有两边裸露的前提下才能获胜（判了）

解释一下操作策略

必胜策略：

如果是 100，将一个 0->1 然后转成 110，后手跳不出 110

如果是 111，随意操作一个转成 100，后手跳不出 110

必败策略：

如果是 110，当操作 0->1 时，后手直接任意一个 1->0 跳不出去，如果操作 1->0 则后手操作 0->1 跳不出来。

如果是 000，除了判掉的特殊情况，任意操作转化成 100，后手直接又转回 110 跳不出去。

所以判断奇偶性即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define dd double
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
//#define getchar gc
ll read()
{
    char c;
    ll w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    ll ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
void pc(char c,int op)
{
    static char buf[1<<16],*s=buf,*t=buf+(1<<16);
    (op||((*s++=c)&&s==t))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
    if(x>9)wt(x/10);
    pc('0'+x%10,0);
}
void wts(int x,char op)
{
    if(x<0)pc('-',0),x=-x;
    wt(x);pc(op,0);
}
const int xx=2e5+5;
int n;
signed main(){
    n=read();
    int a=read(),b=read(),c=read();
    if(a>b)swap(a,b);
    if(a>c)swap(a,c);
    if(b>c)swap(b,c);
    int x=b-a-1,y=c-b-1,z=a+n-c-1;
    if((!x)+(!y)+(!z)>=2)puts("TAK");
    else if(((x&1)+(y&1)+(z&1))&1)puts("TAK");
    else puts("NIE");
    pc('1',1);
    return 0;
}