B. Universal Solution - 猫娘的必胜猜拳秘籍喵~

哈喽，各位小伙伴们，你们好呀！我是你们的猫娘小助手~ (ฅ´ω`ฅ)

今天我们要来对付一个玩“石头剪刀布”的笨笨机器人！这个机器人的策略也太好猜了，简直就是送分题嘛。就让本猫娘来教你如何轻松地获得最多的胜利吧，喵~

题目大意喵~

是这样的，我们发现了一个玩“石头剪刀布”的机器人。这个机器人有一个固定的出招序列 s，比如 "RSP"。

游戏开始前，机器人会秘密地选择一个起始位置 pos。

• 第一回合，它会出 s[pos]。
• 第二回合，它会出 s[pos+1]。
• 第三回合，它会出 s[pos+2]。
• ...以此类推。如果到了序列末尾，它会绕回到开头继续出招。

我们要和它玩 n 个回合（n 是序列 s 的长度）。我们已经知道了它的序列 s，但不知道它会从哪个 pos 开始。

我们的任务是，设计一个我们自己的出招序列 c (长度也是 n)，使得无论机器人从哪个位置 pos 开始，我们赢的平均局数最多！

解题思路的说！

哼哼，想在猜拳上赢过本猫娘？没门！(>^ω^<)

这个问题的关键点在于“最大化平均胜利次数”。听起来有点复杂，但其实可以把它转换成一个更简单的问题哦。

最大化平均胜利次数，就等同于最大化在所有 n 种可能的开局下的总胜利次数！

让我们换个角度思考~

通常我们会想：

如果机器人从 pos=1 开始，我能赢多少局？ 如果机器人从 pos=2 开始，我能赢多少局？ ... 然后把这些胜利次数加起来。

这个思路太麻烦啦！就像数一堆混在一起的毛线球，会头晕的。

不如我们这样想，喵~ 让我们关注我们自己的每一招：

在第 k 回合，我们出招 c_k。那么在所有可能的机器人开局下，这一招 c_k 能为我们带来多少次胜利呢？

我们来分析一下第 k 回合：

• 如果机器人从 pos=1 开始，它会出 s[k]。
• 如果机器人从 pos=2 开始，它会出 s[k+1]。
• ...
• 如果机器人从 pos=n 开始，它会出 s[k+n-1] (注意要取模，会绕回来的)。

你会发现，当 pos 从 1 遍历到 n 时，机器人在第 k 回合出的招，正好把整个序列 s 里的 s_1, s_2, ..., s_n 全部出了一遍！

所以！对于我们第 k 回合的出招 c_k 来说，它相当于和机器人序列 s 中的每一个字符都对战了一次！

那么，为了让 c_k 赢得最多，我们应该出什么呢？

• 如果我们出 布(P)，我们就能赢下 s 中所有 石头(R) 的情况。
• 如果我们出 石头(R)，我们就能赢下 s 中所有 剪刀(S) 的情况。
• 如果我们出 剪刀(S)，我们就能赢下 s 中所有 布(P) 的情况。

Aha! 答案是不是就出来啦？(ΦωΦ)

我们只需要统计一下序列 s 中，'R', 'S', 'P' 哪个字符出现的次数最多。然后，我们每一招都出能克制这个最多字符的招式！

比如说，如果 s 中 'R' 最多，那我们就每一把都出 'P'，这样就能最大化我们的胜利次数了！

总结一下我们的必胜策略：

1. 数一数机器人的序列 s 中 'R', 'S', 'P' 的数量。
2. 找到数量最多的那个字符。
3. 我们的策略就是，n 个回合，每一回合都出能克制那个最多字符的招式！

这样一来，不管机器人从哪里开始，我们的总胜利数都是最大的！是不是超级简单呢？

题解代码喵

下面是解题的代码，本猫娘加上了一些可爱的注释哦~

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void solve() {
    std::string s;
    std::cin >> s;
    int n = s.length();

    // Step 1: 先数一数 R, S, P 各有多少个，就像数小鱼干一样~
    int countR = 0;
    int countP = 0;
    int countS = 0;

    for (char ch : s) {
        if (ch == 'R') {
            countR++;
        } else if (ch == 'P') {
            countP++;
        } else { // ch == 'S'
            countS++;
        }
    }

    // Step 2: 看看哪个最多呢？(ฅ´ω`ฅ)
    // 然后找到克制它的最佳选择！
    char best_response_char;
    if (countR >= countP && countR >= countS) {
        // 'R' (石头) 最多，我们就出 'P' (布) 来克制它
        best_response_char = 'P';
    } else if (countP >= countR && countP >= countS) {
        // 'P' (布) 最多，我们就出 'S' (剪刀) 来克制它
        best_response_char = 'S';
    } else {
        // 'S' (剪刀) 最多，我们就出 'R' (石头) 来克制它
        best_response_char = 'R';
    }

    // Step 3: 然后...嘿嘿，每一局都出这个！让它无路可逃！
    // 构造一个长度为 n，并且所有字符都是我们最佳选择的答案字符串
    std::string result(n, best_response_char);
    std::cout << result << "\n";
}

int main() {
    // 加上这个可以让输入输出更快哦，就像猫猫跑得一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点小课堂~

1. 贪心算法 (Greedy Algorithm)

这道题的解法就是一种典型的贪心算法。

贪心算法就是，在每一步选择中，都采取当前状态下最好或最优的选择，从而希望能导致全局最好或最优的解。就像猫猫总是会先吃掉眼前最大块的鱼干一样！(๑´ڡ`๑)

在这个问题里，我们对自己的每一次出招都做出“局部最优”的选择（即选择能赢 s 中最多字符的招式），而这个选择恰好就导向了“全局最优”的结果（总胜利次数最多）。

2. 贡献法 / 交换求和顺序

我们解题思路的核心，就是把计算总胜利次数的方式从“按机器人的开局来算”转变成了“按我们自己的每一招的贡献来算”。这种思想在算法竞赛中非常有用，有时也被称为贡献法。

从数学上讲，我们是把一个双重求和的顺序交换了一下： 总胜利数 = ∑(对于每个开局pos) [ ∑(对于每一回合k) [c_k是否胜利] ] 交换后变成： 总胜利数 = ∑(对于每一回合k) [ ∑(对于每个开局pos) [c_k是否胜利] ]

这个小小的改变，让内层的求和变得非常容易计算，问题也就迎刃而解啦！

---

好啦，今天的题解就到这里啦！希望本猫娘的讲解对你有帮助。下次遇到类似的题目，也要记得从不同的角度去思考问题哦！拜拜喵~ (´• ω •`)ﾉ