说明

这段代码模拟了一个游戏，其中同学们围成一圈，按照特定的规则传递球。每个同学有一个初始的思维方向（左或右），决定他们将球传给哪个方向的同学。传递过程中，接到球的同学会根据当前思维方向传球，并切换思维方向。游戏持续进行，直到所有同学都至少接到一次球。代码的目标是计算最后一个接到球的同学以及传球的总次数。

算法标签

• 模拟
• 循环处理

解题思路

1. 初始化：读取同学数量 n、初始传球目标 m（转换为0-based索引），以及每个同学的初始思维方向（左或右）。
2. 模拟传球过程：
   • 使用一个数组 d 记录每个同学的当前思维方向（0表示左，1表示右）。
   • 使用一个数组 vis 记录哪些同学已经接到过球。
   • 初始时，球从同学 m 开始传递，传球次数 ret 初始化为1（因为第一次传球是从同学1传给同学 m）。
   • 在每次传球中，当前持球同学 s 根据其思维方向决定传球方向，并切换思维方向。
   • 如果传球目标 t 还未接到过球，则增加已接到球的同学计数 cnt。
   • 更新传球次数 ret 和下一个传球目标 t。
3. 终止条件：当所有同学都接到过球（cnt == n）时，停止模拟并输出结果。

分析

• 传球规则：每个同学接到球后，会根据当前思维方向传球给左边或右边的同学，并切换思维方向。如果传球方向会导致传给自己，则改为传给相反方向的同学。
• 终止条件：游戏在所有同学都至少接到一次球后结束，此时最后一个接到球的同学和传球总次数即为所求。
• 时间复杂度：由于传球次数不超过100,000，且同学数量 n 最多为30，模拟过程的时间复杂度是可接受的。

实现步骤

1. 输入处理：
   • 读取同学数量 n，如果 n 为0则结束程序。
   • 读取初始传球目标 m 并转换为0-based索引（m--）。
   • 读取每个同学的初始思维方向，存储到数组 d 中（L 转换为0，R 转换为1）。
2. 初始化模拟状态：
   • 初始化 vis 数组为 false，表示初始时没有同学接到过球。
   • 设置初始持球同学 s 为 m，传球目标 t 为 unify(0 + dir[d[m]])（即根据同学 m 的初始思维方向决定传球方向）。
   • 如果传球目标 t 等于 s，则调整传球目标为 unify(t + dir[d[m]])（避免传给自己）。
   • 初始化已接到球的同学计数 cnt 为1（同学 m 已经接到球），传球次数 ret 为1。
3. 模拟传球过程：
   • 使用循环模拟传球，直到所有同学都接到球（cnt == n）。
   • 在每次传球中：
     • 标记当前持球同学 s 为已接到球（vis[s] = true）。
     • 切换同学 s 的思维方向（d[s] = 1 - d[s]）。
     • 增加传球次数 ret。
     • 如果传球目标 t 未接到过球，则增加 cnt。
     • 更新下一个传球目标 t 为 unify(s + dir[d[t]])，并根据规则避免传给自己。
     • 更新持球同学 s 为 t。
4. 输出结果：
   • 输出最后一个接到球的同学（s + 1，转换回1-based索引）和传球总次数 ret。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define maxn 35

int n, m;
int d[maxn];
int dir[2] = {-1, 1};
bool vis[maxn];

void input()
{
    char st[5];

    scanf("%d", &m);
    m--;
    for (int i = 0; i < n; i++)
    {
        scanf("%s", st);
        if (st[0] == 'R')
            d[i] = 1;
        else
            d[i] = 0;
    }
}

int unify(int a)
{
    return (a + n) % n;
}

void work()
{
    int s = m;
    int t = unify(0 + dir[d[m]]);
    if (t == m)
        t = unify(t + dir[d[m]]);
    int cnt = 1;
    int ret = 1;

    vis[m] = true;
    memset(vis, 0, sizeof(vis));
    while (cnt < n)
    {
//        printf("%d to %d\n", s + 1, t + 1);
        vis[s] = true;
        d[s] = 1 - d[s];
        ret++;
        if (!vis[t])
            cnt++;
        int temp = unify(s + dir[d[t]]);
        if (temp == t)
            temp = unify(temp + dir[d[t]]);
        s = t;
        t = temp;
    } 
    printf("Classmate %d got the ball last after %d tosses.\n", s + 1, ret);
}

int main()
{
//    freopen("t.txt", "r", stdin);
    while (scanf("%d", &n), n)
    {
        input();
        work();
    }
    return 0;
}