CF1392D Omkar and Bed Wars

Omkar 正在玩他最喜欢的像素风格电子游戏 Bed Wars！在 Bed Wars 中，有 $n$ 个玩家围成一个圈排列，对于所有满足 $2 \leq j \leq n$ 的 $j$，第 $j-1$ 号玩家在第 $j$ 号玩家的左边，第 $j$ 号玩家在第 $j-1$ 号玩家的右边。此外，第 $n$ 号玩家在第 $1$ 号玩家的左边，第 $1$ 号玩家在第 $n$ 号玩家的右边。 现在，每个玩家正在攻击他们左边或右边的玩家。这意味着每个玩家当前可能被 $0$、$1$ 或 $2$ 个其他玩家攻击。Bed Wars 的一个关键策略是：如果某个玩家正好被 $1$ 个其他玩家攻击，那么他们应该合理地反击那个玩家。如果某个玩家被 $0$ 或 $2$ 个其他玩家攻击，那么根据 Bed Wars 的策略，这个玩家可以合理地攻击任意一个相邻的玩家。 不幸的是，可能有些玩家没有正确遵循 Bed Wars 的策略。Omkar 知道每个玩家当前正在攻击谁，并且他可以和任意数量的玩家交谈，让他们改变攻击目标——也就是说，如果某个玩家当前攻击左边的玩家，Omkar 可以说服他们改为攻击右边的玩家；如果他们当前攻击右边的玩家，Omkar 可以说服他们改为攻击左边的玩家。 Omkar 希望所有玩家都能按照逻辑行动。请计算 Omkar 至少需要和多少个玩家交谈，才能使得在所有被交谈过的玩家改变攻击目标后，所有玩家都能按照 Bed Wars 的策略合理行动。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2 \times 10^5$），表示本局 Bed Wars 的玩家（即床）的数量。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。第 $j$ 个字符为 L，表示第 $j$ 个玩家正在攻击他左边的玩家；为 R，表示第 $j$ 个玩家正在攻击他右边的玩家。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数：Omkar 至少需要和多少个玩家交谈，才能使所有玩家都能按照 Bed Wars 的策略合理行动。 可以证明，在给定的约束下，Omkar 总能实现目标。

在第一个测试用例中，第 $1$ 号和第 $2$ 号玩家互相攻击，第 $3$ 号和第 $4$ 号玩家互相攻击。每个玩家都正好被 $1$ 个其他玩家攻击，并且都在反击攻击他们的玩家，所以所有玩家都已经按照 Bed Wars 的策略合理行动，Omkar 不需要和任何人交谈，答案为 $0$。 在第二个测试用例中，并不是所有玩家都合理行动：例如，第 $3$ 号玩家只被第 $2$ 号玩家攻击，但没有反击他。Omkar 可以和第 $3$ 号玩家交谈，将攻击方式改为 LRLRRL，此时所有玩家都能按照 Bed Wars 的策略合理行动，答案为 $1$。 由 ChatGPT 4.1 翻译