CF1739 C. Card Game

标签：打出 号牌 然后 玩家 回合 CF1739 Game 如果 Card

题目链接

题意简述

有这样一个游戏 , 有一摞编号为 \(1\sim n\) 的卡片( 保证 \(n\) 为偶数),编号大的卡片比编号小的卡片更"强".
两名玩家玩这个游戏,他们平均分这 \(n\) 张卡片 ,即每个人有 \(n \over 2\)张卡片.这也就意味着一张牌只可能属于一个玩家.
每一个玩家的回合: 第一个玩家先出牌,然后下一个玩家出一张更强的牌. 如果一个玩家出牌后对手没有更大的牌,那么这个玩家就赢了. 一个玩家的回合结束后,轮到另一个玩家的回合. 如果某个回合结束后两个玩家都没有牌了,那么游戏平局.

给你牌的个数 \(n\) ,请分别计算出 玩家 \(A\) 赢, 玩家 \(B\) 赢,平局 的牌的分配方法数

样例

点击查看样例

分析

解法有很多,官方题解是 \(DP\) 或 组合数学(详见 \(Tutorial\) )

下面给出另一种解法(其实是没看懂官方题解)

注意,在一个玩家的回合结束后,另一个玩家的回合开始,这意味着: A打出牌后,B跟着打出,然后B再打出牌,A再跟着打出.

考虑 \(n\) 张牌的情境.
如果 \(A\) 拿 \(n\) 号牌, 那么 \(A\) 一定获胜.
下面只考虑 \(B\) 拿 \(n\) 号牌的情况

\[tips:事实上,\ A\ 必须首先打出一张比\ B\ 的手牌里除\ n\ 以外的牌都大的牌,把\ B\ 的\ n\ 号牌逼出来,否则:如果给\ B\ 机会先打了一张小牌,然后\ B\ 把\ n\ 打出来,那么\ A\ 就输了. \]

如果 \(B\) 拿 \(n\) 号牌
  如果 \(B\) 拿 \(n-1\) 号牌,那么无论 \(A\) 打出任何牌 , \(B\) 用 \(n\) 号牌响应,然后打出 \(n-1\) 号牌即可获胜.
  如果 \(A\) 拿 \(n-1\) 号牌,
    如果 \(B\) 拿 \(n-2\) 号牌 ,那么 \(B\) 赢了,因为①如果 \(A\) 打出 \(n-1\) 号牌时, \(B\) 使用 \(n\) 号牌,然后打出 \(n-2\) 号牌,然后 \(B\) ,获胜.②如果 \(A\) 打出其他牌, \(B\) 使用 \(n-2\) 号牌,然后打出 \(n\) 号牌即可获胜.
    如果 \(A\) 拿 \(n-2\) 号牌
      如果 \(B\) 拿 \(n-3\) 号牌 : \(A\) 先出 \(n-2\) 号牌把 \(B\) 的 \(n\) 号牌逼出,然后 \(B\) 出 \(n-3\) 号牌, \(A\) 用 \(n-1\) 号牌响应 .然后再轮到 \(A\) 出牌,注意,由于\(n-3 \sim n\) 的牌都用掉了,此时相当于从 \(n-4\) 的牌堆中出牌.
      如果 \(A\) 拿 \(n-3\) 号牌, \(B\) 输了 , \(A\) 先逼出 \(B\)的 \(n\) 号牌 ,然后 \(B\) 剩下的牌比 \(A\)所有牌都小. \(B\) 无论出哪张, \(A\) 都能响应,然后 \(A\)再出一张牌 ,\(B\) 就无法响应了.

\(B\) 拿 \(n-4\) 号牌\(:\) 首先 \(A\) 出 \(n-1\) 或 \(n-2\) 号牌(这是最优的出法,否则 \(A\) 必输) 然后 \(B\) 用 \(n\) 号牌响应,然后 \(B\) 出 \(n-4\)号牌,然后 \(A\) 可以出 \(n-3\) 或者 \(n-1\) 和\(n-2\)的其中一张(上次用完后剩下的那张).这样 \(B\) 就输了.

\(A\) 用 \(n-1\) 或 \(n-2\) 号牌响应(第一次没用的剩下的那张牌.).然后问题转化成了开始的情形(由于 \(n-3 \sim n\) 号牌都打掉了)

代码

标签：打出,号牌,然后,玩家,回合,CF1739,Game,如果,Card
From： https://www.cnblogs.com/oijueshi/p/cf1739c.html