【AGC002E】Candy Piles

首先可以把模型转换一下:

把\(a\)按照从大到小排序,可以画出一个\(n\)列每一列高度为\(a_i\)的多边形。

那么两种操作可以理解为:

  1. 将最左边一列删掉
  2. 将最下边一行删掉

我们可以在平面上放一个点\(x,y\)表示\([1,x)\)的列已经被删除,\([1,y)\)的行已经被删除。

那么每次操作就是把这个点向上或者向右移动,不能移动出多边形,不能移动者输。

标记一个格子先手必胜为\(1\),后手必胜为\(0\)。

那么可以证明,对于一个多边形内的点\((x,y)\),它和\((x-1,y-1)\)的标记一定相同。

如果\((x,y)\)为\(0\),那么在\((x-1,y-1)\)处无论先手怎么移动,后手都能移动到\((x,y)\),于是\((x-1,y-1)\)为\(0\)。

如果\((x,y)\)为\(1\),那么考虑反证,如果\((x-1,y-1)\)为\(0\),必有\((x-1,y)\)和\((x,y-1)\)都为\(1\);那么由于\((x,y)\)为\(1\),\((x-1,y)\)和\((x,y-1)\)的后继状态必须有一个\(0\),所以又有\((x-1,y+1)\)和\((x+1,y-1)\)为\(0\);又因为\((x,y)\)的后继状态必须有一个\(0\),而两个\(0\)是不能相连的(\(0\)的后继状态一定都是\(1\)),所以矛盾。

画出图来就是:

$$\begin{matrix}
0&?&\\
1&1&?\\
0&1&0\\
\end{matrix}$$

在\(?\)处产生矛盾。

所以就可以轻松解决了。边界处稍微计算一下即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz