1 条题解
-
0
对于果农 ,最优的操作是在剩余字符串还有 的时候,选 ,否则选 。所以当两个果农刚好能一人选一次到游戏结束时,子串中一定满足 。
- 当 时,果农 能在两人一人选一次后多选一次,玩家一获胜。
- 当 时,
- 当 时,在倒数第二轮选完之后,刚好只剩下两个 、一个 。果农 获胜。
- 剩余其他情况下,带倒数第二轮选完之后会剩下两个 和若干个 ,果农 获胜。
果农 获胜的数量就是所有满足的 或 的子串数量。
设 表示前 位的 的数量,所有以第 位结尾的子串中,果农 获胜的数量为满足 且 或 的 的数量(满足 或 ,其中 表示的是 的子串中的 数量。
最后只需要统计出满足 且 或 的 的数量即可。
时间复杂度: 。
信息
- ID
- 8292
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 9
- 已通过
- 3
- 上传者