P10261 题解

qwer6 · 2025-07-01 14:36:52 · 题解

1. Description

给一个正多边形的顶点，两个玩家在自己的回合分别选择两个顶点连线，要求这条线不得于之前的任何一条线相交，如果这个玩家的回合后图中出现了三角形，那么这个玩家胜利。

2. Solution

我们手玩几个图形之后显然可以得到一个结论：如果在之前的回合中 (i,j) 这条线被连了，那么后面的玩家都不会使用 i 或 j 连接，否则就会输，那么这个问题就转换为了一个经典的 Nim 博弈问题，初状态显然：SG(0)=0,SG(1)=0。

那么 SG(n)=\operatorname {mex}(\{SG(i)\bigoplus SG(n-2-i)\}) (0\le i\le n-2)，可以使用一个 O(n^2) 的算法解决这个问题。

但是这样显然无法拿到满分，根据博弈题常见的套路，直接打表，使用瞪眼法可以得到结论：从 SG(69) 开始，每 34 项为一个周期，所以打一个表，然后就可以 O(1) 的解决问题了。

3. Code

/*by qwer6*/
/*略去缺省源与快读快写*/
const bool f[]={0,0,
                1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,
                1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,
                1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1};
int n;
signed main(){
    int t;
    read(t);
    while(t--){
        read(n);
        if(n<=69)puts(f[n]?"Lucija":"Ivan");
        else puts(f[(n-70)%34+70]?"Lucija":"Ivan");
    }
}