P9862 [CCC 2008 J5/S5] Nukit 题解

· · 题解

题目大意：已经说得够清楚了。

P9862 [CCC 2008 J5/S5] Nukit 题解

这是一道博弈论题，不会有人不知道什么叫博弈论吧。如果不知道，我们先介绍一下什么叫博弈论。

其实博弈论就是小学奥数题里的取石子游戏，每人可以取若干个物品，先取完者胜，也可以是报数等变形题。另一种就是 Nim 游戏，具体规则参见 P2197 【模板】Nim 游戏，不再讲述。

我们步入正题。由于字符个数很小，我们可以记录 dp_{a,b,c,d,ok}，其中 a,b,c,d 分别代表每种字符还剩几个。当 ok=0 时，表示 Patrick 取；当 ok=1 时则表示 Roland 取。再来考虑俩人的必胜策略。当 dp_{a,b,c,d,ok}=1 时表示 Patrick 有必胜策略；反之则没有。所以我们要求 dp_{a,b,c,d,ok} 是否等于 1 。我们又知道当一个状态为必胜状态时，下一步能够产生的所有状态都是必胜状态。当一个状态不必胜时，下一步能产生的状态中不必胜。我们知道了这个，在分类讨论，代码就好写了。

Tip：配合记忆化搜索味道更佳哦！

这里是代码（不会有人只看这里吧……）。