A10.传球游戏题解

---

题目分析

本题要求计算在n个同学站成一个圆圈的情况下，从第1个同学（小蛮）开始传球，经过m次传球后，球回到第1个同学手中的不同传球方法数。每个同学可以将球传给左右两个同学中的任意一个。

这是一个典型的动态规划问题，可以通过状态转移来求解。

核心思路

我们使用动态规划来解决这个问题：

• 定义 dp[i][j] 表示传球i次后，球在第j个同学手中的方法数
• 初始状态：dp[0][0] = 1（第0次传球，球在小蛮手中，注意题目中"小蛮为1号"，我们将其视为第0号）
• 状态转移：dp[i][j] = dp[i-1][(j-1+n) % n] + dp[i-1][(j+1) % n]
  • 球传到第j个同学，可能来自第j-1个同学（左边）或第j+1个同学（右边）
  • 由于是圆圈，需要对n取模
• 最终答案：dp[m][0]（传球m次后，球回到小蛮手中）

---

代码实现，可食用

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

int main() {
    int n, m;
    cin >> n >> m;
    
    long long dp[31][31] = {0};
    
    dp[0][0] = 1;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < n; j++) {
            // 从左边传(j-1+n) % n
            // 从右边传(j+1) % n
            dp[i][j] = dp[i-1][(j-1+n) % n] + dp[i-1][(j+1) % n];
        }
    }
    
    cout << dp[m][0] << endl;
    
    return 0;
}

代码详解

1. 初始化：

   • dp[0][0] = 1 表示初始时，0次传球，球在小蛮手中
   • 其他位置初始化为0

2. 状态转移：

   • 对于第i次传球，遍历每个同学j
   • 球传到j同学，可能来自j-1同学（左边）或j+1同学（右边）
   • 由于是圆圈，使用模运算处理边界情况：
     • 左边：(j-1+n) % n（避免负数取模）
     • 右边：(j+1) % n
   • 将两种来源的方法数相加

3. 结果：

   • 最终输出dp[m][0]，表示传球m次后，球回到小蛮手中的方法数

示例分析

以样例输入3 3为例：

• 初始状态：dp[0][0] = 1, dp[0][1] = 0, dp[0][2] = 0
• 第1次传球：
  • dp[1][0] = dp[0][2] + dp[0][1] = 0 + 0 = 0
  • dp[1][1] = dp[0][0] + dp[0][2] = 1 + 0 = 1
  • dp[1][2] = dp[0][1] + dp[0][0] = 0 + 1 = 1
• 第2次传球：
  • dp[2][0] = dp[1][2] + dp[1][1] = 1 + 1 = 2
  • dp[2][1] = dp[1][0] + dp[1][2] = 0 + 1 = 1
  • dp[2][2] = dp[1][1] + dp[1][0] = 1 + 0 = 1
• 第3次传球：
  • dp[3][0] = dp[2][2] + dp[2][1] = 1 + 1 = 2

输出2，与样例一致。

复杂度分析

• 时间复杂度：O(n*m)，需要遍历m次传球，每次遍历n个同学
• 空间复杂度：O(n*m)，使用二维数组存储状态

常见错误点

1. 边界处理错误：在圆圈中，需要正确处理模运算，避免负数取模

   • 正确做法：(j-1+n) % n，而不是(j-1) % n

2. 初始状态错误：小蛮是第1个同学，但在代码中我们将其视为第0号

   • 需要确保初始状态dp[0][0] = 1，而不是dp[0][1] = 1

3. 数组大小不够：n和m最大为30，数组大小应为31×31，不能使用30×30

4. 使用int导致溢出：方法数可能很大，应使用long long类型

---

总结

这道题是典型的动态规划问题，通过定义状态和状态转移方程，可以高效地求解。关键在于正确处理圆圈的边界情况，以及理解传球的规律。动态规划方法的时间复杂度为O(n*m)，在题目给定的约束条件下（n, m ≤ 30）完全可以接受。