P2597 - 乒乓球(语法周赛 Round 20（思维场）)

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：5 解决：4

提交提交记录统计流程图露一手!

小明和小红在打乒乓球比赛。

规则是这样的：对于每一颗球，如果小红赢，小红得一分，如果小明赢，小明得一分。谁的得分首先大于等于 $11$ 分，且比对方的得分高出至少 $2$ 分，则赢得此局比赛。

在记录了 $n$ 颗球的胜负关系后，聪明的裁判员大翼发现：对于任意第 $i(i>k)$ 颗球来说，第 $i$ 颗球的胜负关系，与第 $i-k$ 颗球的胜负关系一模一样。因此，大翼只记录了前 $k$ 颗球的胜负关系。

然而，在记录完毕后，他发现一个重要的问题：他忘记统计两个人分别赢了几局了！

这真是好尴尬啊。还是请你帮他还原一下最终的结果吧！

第一行输入 $n,k$ ，如题所述。

接下来一行一个长度为 $k$ 的字符串，第 $i$ 个字符是 A 表示第 $i$ 局小明赢了，B 表示第 $i$ 局小红赢了。

第一行输出两个整数 X:Y，分别表示最后小明/小红赢了几局。

20 3
AAB

1:0

20 3
AAB

1:0

最终的序列实际上是 AABAABAABAABAABAABAA，在第 $16$ 颗球结束时，小明和小红的部分是 $11:5$ ，小明赢得一局。在 $20$ 颗球记录完毕时，当前比分是 $3:1$ 。

1000 6
AABBAB

24:23

数据范围

对于 $5\%$ 的数据：字符串中只包含 A。

对于 $30\%$ 的数据： $n\leq 10^7$ 。

对于另外 $30\%$ 的数据：保证无论是谁得分到达 $11$ 分时，必定取得这局的胜利。

对于另外 $15\%$ 的数据：保证 $n$ 是 $k$ 的倍数。

对于 $100\%$ 的数据： $n\leq 10^{18},k\leq 10^5$ 。

语法周赛

提交提交记录统计露一手!