LOJ#551 Matrix

本地打表在线AC什么的最喜欢了。

题意

$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$和$\mathrm{B}\mathrm{o}\mathrm{b}$在玩游戏，他们要给一个$n\times n$的矩阵打标记。初始时没有任何标记，每一轮$\mathrm{B}\mathrm{o}\mathrm{b}$先手，两个人可以选一个格子打上自己的标记（$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}\to \mathrm{A},\mathrm{B}\mathrm{o}\mathrm{b}\to \mathrm{B}$），但如果选择了已经打过标记的格子就输掉游戏。

如果在某个时刻，存在一个长度为$n$的排列$p$使得对于$i=1,2,\dots ,n$，有第$i$行第$p_i$列的标记为$\mathrm{A}$成立，那么$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$获胜。

如果在$\lfloor \frac{n^2}{2}\rfloor$轮后，$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$依然没有获胜，那么$\mathrm{B}\mathrm{o}\mathrm{b}$获胜。

给定$T$组询问，每次给定一个数$n$，问在之前的游戏规则下：

$1$、双方记得之前的所有操作，$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$是否有必胜策略。

$2$、$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$只记得当前这一轮$\mathrm{B}\mathrm{o}\mathrm{b}$的操作，$\mathrm{B}\mathrm{o}\mathrm{b}$记得所有操作，$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$是否有必胜策略。

$T\le 100,n\le {10}^{18}$。

题解

这种题目就应该大力猜结论。

先考虑比较简单的第一问，在$n$比较大的平凡情况下，假设$\mathrm{B}\mathrm{o}\mathrm{b}$标记了第$x$行的某个格子，那么$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$就可以选择第$x$行的另一个格子（记为第$y$列）。之后，$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$选择第$y$列上的格子一定是不优的，因此对$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$来说，她可以将棋盘重新看作$(n-1)\times (n-1)$大小的。只要在$(n-1)\times (n-1)$时有必胜策略，那么$n\times n$时就一定有必胜策略。

那么暴搜最小的有必胜策略的$n$，可以本地发现$n=4$时有必胜策略，因此第一问的答案就是$[n\ge 4]$。

对于第二问，显然必胜策略应该避免选择已经标记过的格子。可以发现唯一的方法就是使棋盘上的格子两两匹配，对于每一个匹配，假如$\mathrm{B}\mathrm{o}\mathrm{b}$选择了其中一个，那么$\mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}$就立即选择另一个。

首先$n$为奇数的时候显然无解，考虑怎么在$n$为偶数的时候构造一种匹配方案，使得对于每一个匹配无论选择哪一个，总存在一个排列满足对应的位置都标记了$\mathrm{A}$。

先本地暴搜$n$小的情况（当然要加一点剪枝），可以发现$n=4$和$n=6$都是有解的。

那么对于更大的$n$，只要在对角线上依次放上$n=4$或$n=6$的，剩下的位置随便匹配即可。

比如下面就是$n=10$的构造方法，蓝色部分随意匹配即可。

于是第二问的答案就是$[n\ge 4,n\equiv 0(mod2)]$。

#include<cstdio>
#define int long long
signed main()
{
	int T,n;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		puts(n>=4?"Yes":"No");
		puts(n>=4&&!(n&1)?"Yes":"No");
	}
	return 0;
}