自动搬运

查看原文

来自洛谷，原作者为

	qwer6 “向我们曾迷惘的路致敬！”

搬运于2025-08-24 22:56:17，当前版本为作者最后更新于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");
	}
}