ABC380F Exchange Game

Problem Link

题目大意

Takahashi 和 Aoki 在玩一个卡牌游戏，每张卡牌上写有一个数字。

初始时 Takahashi 有 N 张牌，Aoki 有 M 张牌，桌上还有 L 张牌。游戏规则如下：

• 轮到某个玩家的回合时，该玩家从手中打出一张牌（记作 k）置于桌子上，并允许从桌子上拿取不超过一张数值小于 k 的牌。
• 当一个玩家不能进行上述操作时，对方获胜，游戏结束。

若 Takahashi 先手，双方都知道所有牌的布局，问最优策略下谁是必胜者。

N+M+L\le 12

思路分析

令 N+M+L=|S|。

赛时一直在想状压，如设 O(3^{|S|}) 或者 O(2^{2\cdot |S|}) 的状态数，发现转移式并不是很直观。

不是，|S|\le 12 想啥状压呢？记搜模拟一遍就做完了啊（

将牌的布局压缩成一个数，函数 dfs(i) 表示牌的布局为 i 时先手的胜败情况，|S|^2 模拟每一次操作过程即可。

由于状态数有 3^{|S|} 种，故总复杂度 O(3^{|S|}\cdot |S|^2)。

Submission