Moe's CF Life

喵好，指挥官！面对这个球赛谜题，是不是有点头晕目眩呀？别担心，让本喵来帮你理清思路，找到所有可能拿到球的小伙伴吧！nya~

题目大意

简单来说，就是有一场 n 个小伙伴围成一圈的传球游戏哦。他们从 1 到 n 顺时针编号。

游戏是这样的：

一开始，球在 x 号小伙伴手上。
总共要进行 m 次传球。
第 i 次传球的距离是 r_i。传球可以顺时针传，也可以逆时针传。
对于每一次传球，题目会告诉我们它的方向：
- '0' 代表顺时针。
- '1' 代表逆时针。
- '?' 代表方向不确定，两种方向都有可能。

我们的任务就是，在 m 次传球之后，根据这些信息，找出所有可能持有球的小伙伴的编号，并把他们从小到大排好序输出。很简单对吧？喵~

题解方法

这个问题呀，最关键的地方就在于那个神秘的 '?'。因为它，球的位置在每次传球后就不再是唯一的了，而是一个可能的位置集合。

那么，我们可以这样想，喵：

初始状态：游戏还没开始，球的位置是确定的，就在 x 号小伙伴那里。所以，我们用一个集合（set）来存放当前所有可能的位置，一开始里面只有一个元素：{x}。
递推过程：我们来模拟每一次传球。对于第 i 次传球（距离为 r_i，方向为 c_i），我们需要做的是：
- 创建一个新的空集合，用来存放这一次传球后球可能到达的位置。
- 遍历上一次传球后所有可能的位置。对于每一个可能的位置 p：
  - 如果方向 c_i 是 '0' (顺时针) 或者 '?' (不确定)，我们就计算出从 p 顺时针传 r_i 距离后的新位置，并把它加入新的集合里。
  - 如果方向 c_i 是 '1' (逆时针) 或者 '?' (不确定)，我们就计算出从 p 逆时针传 r_i 距离后的新位置，也把它加入新的集合里。
- 当遍历完所有旧的可能位置后，这个新的集合就包含了第 i 次传球后所有可能的位置啦。我们用这个新集合替换掉旧的集合。
循环往复：重复上面的递推过程 m 次。
最终结果：当 m 次传球全部模拟完毕后，我们最后的那个集合里，就是所有最终可能持有球的小伙伴的编号啦！因为 set 会自动帮我们排序和去重，所以直接输出集合里的元素就好，非常方便的说！

如何计算新位置呢？

这是个圈圈，所以要用模运算（Modulo Arithmetic）哦。假设有 n 个人，编号从 1 到 n。为了方便计算，我们先把编号减 1，变成 0 到 n-1 的范围。

顺时针：从 current_pos (1-indexed) 顺时针移动 r 步，新位置是 ( (current_pos - 1) + r ) % n + 1。
逆时针：从 current_pos (1-indexed) 逆时针移动 r 步，新位置是 ( (current_pos - 1) - r + n ) % n + 1。
- 这里 - r 之后可能会变成负数，所以要先 + n 再取模，保证结果是正的，喵~

题解

下面让我们一起看看这份代码是怎么实现我们刚才的想法的吧！

cpp

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

// 让输入输出快一点的小魔法，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// 解决单个测试用例的逻辑
void solve() {
    int n, m, x;
    std::cin >> n >> m >> x;

    // 使用 set 来存储球可能在的位置。
    // set 会自动处理重复元素并保持排序，超棒的！
    std::set<int> possible_positions;
    possible_positions.insert(x); // 初始位置是 x

    // 处理 m 次传球
    for (int i = 0; i < m; ++i) {
        int r;
        char c;
        std::cin >> r >> c;

        // 一个临时的 set，用来存放这次传球后新的可能位置
        std::set<int> next_possible_positions;

        // 遍历当前所有可能的位置
        for (int current_pos : possible_positions) {
            // 情况1：顺时针传球
            // 如果方向是 '0' (顺时针) 或 '?' (不确定)，就计算顺时针的位置
            if (c == '0' || c == '?') {
                // 玩家是1到n编号，我们先转成0到n-1来计算
                // (current_pos - 1 + r) % n 是新的0-indexed位置
                // 最后 +1 转回1-indexed编号
                int next_pos_cw = (current_pos - 1 + r) % n + 1;
                next_possible_positions.insert(next_pos_cw);
            }
            
            // 情况2：逆时针传球
            // 如果方向是 '1' (逆时针) 或 '?' (不确定)，就计算逆时针的位置
            if (c == '1' || c == '?') {
                // (current_pos - 1 - r) 可能是负数。
                // 在取模前先加上 n，可以保证结果总是正确的非负数。
                int next_pos_ccw = (current_pos - 1 - r + n) % n + 1;
                next_possible_positions.insert(next_pos_ccw);
            }
        }
        
        // 用这次传球后的新位置集合，更新我们的可能位置集合
        // std::move 比直接复制可能稍微快一点点哦
        possible_positions = std::move(next_possible_positions);
    }

    // 输出结果
    std::cout << possible_positions.size() << "\n";
    bool first = true;
    for (int pos : possible_positions) {
        if (!first) {
            std::cout << " ";
        }
        std::cout << pos;
        first = false;
    }
    std::cout << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码的逻辑和我们刚才分析的完全一样！possible_positions 就是我们说的那个集合，每一轮循环都根据 r_i 和 c_i 的规则，从旧的 possible_positions 计算出 next_possible_positions，然后更新它。m 轮之后，possible_positions 就是最终答案啦！

知识点介绍

这次解题之旅，我们还顺便复习了几个有用的知识点呢，喵！

递推 / 动态规划思想 这个问题的解法本质上是一种简单的递推，也可以看作是动态规划（DP）的入门思想。我们定义“状态”为每一轮传球后球可能在的位置集合。第 i 轮的状态，完全由第 i-1 轮的状态和第 i 次传球的规则决定。我们一步一步地从初始状态推导出最终状态，这就是递推的核心啦。
集合 (Set) 数据结构 C++ 的 std::set 在这里简直是神器！它主要有两个特性：
- 元素唯一性：set 中不会存储重复的元素。当我们计算新位置时，可能会有多种方式到达同一个小伙伴那里（比如从位置2顺时针走3步和从位置4顺时针走1步都到5），set 会自动帮我们处理掉重复，只保留一个5。
- 自动排序：set 内部的元素总是保持有序的。这完美契合了题目要求按升序输出最终结果的需求，省去了我们自己排序的麻烦。
模运算 (Modulo Arithmetic) 处理环形问题（比如时钟、圆桌、本题的玩家圈）的必备工具！通过取模运算，我们可以把一个无限延伸的数轴“卷起来”变成一个环。记住这个小技巧：为了防止负数在取模时出现意外（在不同语言中行为可能不同），对于 (a - b) % n 这种运算，最好写成 (a - b + n) % n，这样就能确保结果落在 [0, n-1] 的区间内，非常安全可靠的说！

好啦，这次的解说就到这里啦！希望本喵的讲解对指挥官有帮助哦！如果还有什么问题，随时可以再来找我，喵~

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍