0649. Dota2 Senate¶
题目信息¶
- 题号:
0649
- 难度:
Medium
- 主题:
循环轮次、两方阵营、禁权、最优策略
- 原题:
- 重点:
参议员按字符串顺序循环行动、仍有权利者可永久禁止一名对方参议员、双方都采用最优策略、返回最终获胜阵营
题目重述¶
字符串 senate 按顺序记录参议员所属阵营:'R' 表示 Radiant,'D' 表示 Dire。游戏按字符串顺序循环进行,已经失去权利的参议员会被跳过。
每名仍有权利的参议员行动时,可以永久禁止一名对方参议员在当前及后续轮次中的全部权利;当某一阵营所有仍有权利的参议员都属于同一方时,该方可以宣布胜利。双方都采用能够使自己获胜的最优策略,返回 "Radiant" 或 "Dire"。senate.length 位于 [1, 10^4]。
自建示例¶
后出现的多数方可以反制:
输入:senate = "DRR"
输出:"Radiant"
解释:最前面的 D 先禁止第一个 R;剩余 R 随后禁止 D,最终只有 Radiant 参议员保有权利。
只有一个阵营:
输入:senate = "D"
输出:"Dire"
解释:开始时所有有权利的参议员都属于 Dire,因此可以立即宣布胜利。