[CF1161C] Thanos Nim

传送门

题意:(2n)堆石子,每堆(a_i)个,先手每次选中(n)堆石子,并从每堆中拿走任意个(可以不同)。轮到某人时不足(n)堆则判负,问先手是否必胜。(nleq25,a_ileq 50).


显然,轮到某人时,若堆数在([n,2n))之间,他可以直接拿走(n)堆,取得胜利。这意味着只要某个人先手将某堆拿空,他将告负。

考虑什么时候一个人会将一堆拿空而告负,发现只会出现在(1)的个数在((n,2n])时。由此发现,若大小为(1)的堆数量在([1,n])内,他一定可以让一些堆的大小降为(1),使得对手将某些堆拿空。

回顾开始的胜利条件,我们发现它等价于大小为(0)的堆的数量在([1,n])时先手必胜,在((n,2n])时先手必败,否则考虑大小为(1)的堆的情况。发现与上一段中的情况完全相同,可以递归处理直到某个数量存在至少一堆。

因此我们得到了一个结论:若最小值出现次数超过(n)则先手必胜,否则先手必败。这是数学归纳法在OI上的良好应用。

原文地址:https://www.cnblogs.com/suwakow/p/11383327.html