Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3895: 取石子

题目链接

传送门
Description
Alice和Bob两个好朋含友又开始玩取石子了。游戏开始时,有N堆石子排成一排,然后他们轮流操作(Alice先手),每次操作时从下面的规则中任选一个:
- 从某堆石子中取走一个
- 合并任意两堆石子

不能操作的人输。Alice想知道,她是否能有必胜策略。

Input

第一行输入T,表示数据组数。
对于每组测试数据,第一行读入N。
接下来N个正整数a1,a2…an,表示每堆石子的数量。

Output

对于每组测试数据,输出一行。
输出YES表示Alice有必胜策略,输出NO表示Alice没有必胜策略。

Sample Input

3

3

1 1 2

2

3 4

3

2 3 5

Sample Output

YES

NO

NO

HINT

100%的数据满足T<=100, N<=50. ai<=1000

题解

这个题在不考虑一切的情况下 至少我们知道当先手能把操作数控制在奇数的时候 这就是一个必胜策略
所以这个题变成了一个如何控制操作数的题
你怎么才能知道操作数呢
首先 对于只有一个石子的一堆 操作数显然为1
对于有>1个石子的一堆 它的操作数是ai+1 这是为什么呢 你需要考虑合并问题
在1那里你为什么不用考虑呢 因为上面你合并完之后到了下面
然后用dp[i][j]表示i堆只有一个石子 其他的石子堆总操作数是j
当dp[i][j]=1时代表这是一个N-position
反之这是一个P-position
然后进行dp转移就好

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏