题解

思路

关键支配关系

把“当前桌面上的牌”看成状态。若当前是某张牌 $v$，对手可以选择任意攻击值大于 $v$ 防御值的牌。

在所有能应对的牌中，只需要考虑防御值最大的一张 $u$。因为能击败 $u$ 的牌一定也能击败任何防御值不超过 $u$ 的牌；所以选择 $u$ 对下一位玩家最不利，不会比选择其他牌差。于是每个状态至多只有一个有效后继。

做法

子任务 1：完整博弈图

当 $n,m\le 50$ 时，枚举每张牌能转移到的所有对方牌，得到一般有向二分图。终止状态（没有后继）对当前牌的持有者为胜。反向拓扑判定：

• 若一个状态能转移到“对方必败”状态，则当前状态必胜；
• 若一个状态的所有后继都是“对方必胜”状态，则当前状态必败；
• 最后未确定的状态位于或能到达无限循环，为平局。

复杂度 $O((n+m)^2)$。

子任务 2：扫描最大防御

对每张牌扫描对方全部牌，在攻击值严格大于当前防御值的牌中取防御值最大者，建立每点出度至多为一的函数图，再沿函数图判定胜、平、负。

复杂度 $O(nm)$。

子任务 3：排序与函数图

分别把双方的牌按攻击值从大到小排序，并维护每个前缀中防御值最大的牌。对当前牌 $v$，二分找到对方攻击值大于 $v$ 防御值的最长前缀；此前缀的最大防御牌就是唯一需要保留的后继。

在函数图中，记 $res(v)$ 为当前桌面牌持有者的结果：胜为 $1$、平为 $0$、负为 $-1$。

• 无后继时，下一位玩家无法应对，所以 $res(v)=1$；
• 有后继 $u$ 时，轮到另一方，故 $res(v)=-res(u)$；
• 进入有向环时游戏可以无限持续，环及其入树上的相应未定状态均为平局。

迭代遍历函数图即可，避免深递归。最后只统计 Monocarp 的 $n$ 个状态。

正确性证明

最大防御的合法应对牌支配其余所有合法应对牌，因此保留该牌不会改善下一位玩家的处境，也不会改变最优胜平负。压缩后的每个状态只有唯一后继：终止点由无法应对直接确定胜负，沿边时双方视角取反，进入环则双方都能使游戏无限延续。故函数图上的结果与原博弈完全一致，统计 Monocarp 对应状态即可得到答案。

复杂度

完整博弈图算法为 $O((n+m)^2)$，逐牌扫描算法为 $O(nm)$。满分做法的排序、二分和函数图遍历总复杂度为 $O((n+m)\log(n+m))$，空间复杂度为 $O(n+m)$。