AGC 002 E 题解

发布时间 2023-08-11 16:12:35作者: MrcFrst_LRY

原题传送门

题意:给一个正整数序列 \(a\),两人轮流操作直到不能再进行任何操作,每次操作可以将序列中的一个最大的数变为 \(0\),或者将序列中所有正整数减去 \(1\)。当序列中所有数都为 \(0\) 的时候,操作结束。执行最后一次操作的人失败。求必胜客必胜者。

首先注意到删最大值,所以很容易想到将序列 \(a\) 从大到小排序,然后将所有数减去一的话,感性理解一下,就好像把一块板子往上抬高一个单位,然后我们只关心板子上方的数。因为我们排了序,所以第一个操作也可以视作把最左边的数删掉,也就是用一块板子放在左边,然后每次把它往右挪一个单位,我们只关心这块板子右侧的数。

但是,挪动板子这东西感觉不是很友好。(大概是我太菜了不会搞这种。所以我们尝试转化成常见的问题。那么也就是
第一篇题解
那样,将全局视作一个柱状图(或者说网格图可能更合适。然后将挪动板子视作点的移动。具体来说,我们最开始在原点\((0,0)\)处,将挪动左边的板子视作往右走一格,挪动下面的板子视作往上走一格,那么我们任何时候就都只关心右上方的点了。这大概算是对问题的一个转化或者说直观化。

此时,失败局面就很显然了,当处于图的边界时就输了。然后考虑倒推,这个借助图也很容易解决,从必败点往前倒退一步显然便是必胜点,再往前倒退一步就是必败点。解释就是……感性理解一下,你在这个点一定可以往上面或者右边走一步,而不管怎么走都会走到必败点,所以走完之后,轮到对方走的时候对方一定就处于必败点,所以这个点就是必胜点了。以此类推,手玩一下会发现最后会呈现出黑白点相间铺满整张图的场景

然后只需要判断原点是必胜点还是必败点就好了。

一种很直观的方式就是
第一篇题解
那样。发现一条斜率为 \(1\) 的直线上的点颜色相同,然后就可以乱搞了。

但是我想,能不能用自己的方式理解一下?

我们发现 \(a\) 的值域很惊悚(。所以手动将整张图构造出来的想法显然不现实。那么我们就得利用我们推断必胜\(/\)必败点的方式。

是从边界开始,每次分裂成两个点,分别是往下和往左走一格。那么就是说我们从原点开始博弈,每一次不管先手往哪里走,后手都可以进行与他相反的操作把当前的局势值变为 \(0\),大概就这样吧,可能参照了一点 \(Nim\) 博弈的思路。

然后就可以开始乱搞了。不多说了,结束。