[题解] [CF1434E] A Convex Game

[题解] [CF1434E] A Convex Game

给一个长为 $n$ 的单增序列 $v$,两人轮流选数,要求两人选出的数是 $v$ 的子序列且差分数组也单增,无法选的人输。求 SG 值。

$T$ 组询问。$1\le T\le 1000,1\le v_i,\sum n\le 10^5$。


我们有个结论,SG 值是 $O(\sqrt V)$ 的(事实上遇到这种有限状态上转移的游戏都应该想下这个)。证明:每次选出的差都要严格大于上一次的差,差的总和 $\le V$,于是一次游戏最多只能选根号个,而 SG 值是不大于最长转移次数的。

对于位置 $j$,我们分别对每种可能的 SG 值 $i$ 算出 $p_{i,j}$:如果要从这个位置开始然后得到 $i$ 这个 SG 值,最远可以跳到哪儿。考虑记一个 $pos_{i,j}$,代表我们现在选到了第 $j$ 个数,然后要使 选了下一个后 SG 值为 $i$,下一个最大能选到哪儿。于是就有
$$
p_{i,j}=\min_{0\le k<i}pos_{k,j}
$$
考虑转移,从右到左计算,对一个 $j$ 计算得到 $p_{i,j}$ 后我们就可以把前 $i-1$ 个数从左到右划成很多段,第一段转移过来的话 SG 值是 $1$,第二段转移过来 SG 值是 $2$,以此类推。我们就需要依次把这些段的 $pos_{i,k}$ 和我们当前的位置 $j$ 取 $\max$。那么怎么维护呢?开根号棵线段树?

其实我们发现由于我们是倒着枚举 $j$ 的,于是每个 $pos_{i,j}$ 只会被更新一次,于是我们用一个并查集做区间赋值即可。最后我们要算答案,只需要找到从每个位置开始的 SG 值然后取 $\mathrm{mex}$ 即可。

时间复杂度 $O(TV+n\sqrt V)$,但实际上没按秩合并的并查集复杂度不能算常数,但你考虑你不管那么多。

mivik.h / 代码

作者

Mivik

发布于

2021-04-16

更新于

2024-04-30

许可协议

评论