目录
一、提问词
二、DeepSeekR1回复
题目描述
解题思路
实现代码
代码说明
三、说明
【IMA+DeepSeekR1+本地知识库】撰写NOIP2008普及组复赛题解系列
1、IMA+DeepSeekR1+本地知识库撰写NOIP2008普及组T1【ISBN 号码】题解-CSDN博客
2、IMA+DeepSeekR1+本地知识库撰写NOIP2008普及组T2【排座椅】题解-CSDN博客
3、IMA+DeepSeekR1+本地知识库撰写NOIP2008普及组T3【传球游戏】题解-CSDN博客
4、
5、NOIP2008普及组所有测试数据及DeepSeek例程
一、提问词
请撰写NOIP2008普及组T3【传球游戏】题解，要求：
一、从文件“ball.in”读数据，答案写入文件“ball.out”。
二、题解至少包括以下几个部分：
1、题目描述
2、解题思路及推理过程
3、实现代码
4、代码说明二、DeepSeekR1回复
题目描述
n 个同学围成一圈传球，初始球在 1 号同学手中。每次传球可将球传给左侧或右侧的同学。求经过 m 次传球后，球回到 1 号同学手中的不同传球方法总数（两种方法不同当且仅当传球顺序不同）。
输入格式
从文件 ball.in 读取两个整数 n, m（3 ≤ n ≤ 30，1 ≤ m ≤ 30）。
输出格式
写入文件 ball.out：一个整数，表示符合条件的方法数。
解题思路
动态规划：
- 状态定义：
dp[i][j]表示传球i次后到达第j号同学的方案数。 - 转移方程：
每次传球由左侧或右侧传来，故：
dp[i][j] = dp[i-1][(j-1+n) % n] + dp[i-1][(j+1) % n] - 初始状态：
dp[0][0] = 1（初始在 1 号，但编号处理为0方便取模）。 - 最终状态：
dp[m][0]（经过m次传回初始位置）。
实现代码
#include <cstdio>
using namespace std;int main() {freopen("ball.in", "r", stdin);freopen("ball.out", "w", stdout);int n, m;scanf("%d%d", &n, &m);int dp[35][35] = {0};dp[0][0] = 1; // 初始在0号位置（原题中为1号，此处做环状处理）for (int i = 1; i <= m; ++i) { // 传球次数for (int j = 0; j < n; ++j) { // 当前在j号位置// 从左侧和右侧转移而来dp[i][j] = dp[i-1][(j-1+n) % n] + dp[i-1][(j+1) % n];}}printf("%d\n", dp[m][0]); // 传m次后回到初始点0号位的方案数return 0;
}
代码说明
- 状态初始化：
dp[0][0] = 1表示初始球在 0 号位置（对应题目中的 1 号同学，简化环状运算）。 - 状态转移：
每个dp[i][j]由i-1次左侧同学(j-1+n) % n和右侧同学(j+1) % n的方案数之和。 - 环状处理：
通过%n运算处理环的边界，确保j-1和j+1在有效范围内。 - 时间复杂度：O(m·n)，满足题目数据规模。
样例验证：
输入 3 3 时，计算过程如下：
dp[1][0] = dp[0][2] + dp[0][1] = 0dp[1][1] = dp[0][0] + dp[0][2] = 1dp[1][2] = dp[0][1] + dp[0][0] = 1
... 最终dp[3][0] = 2，与题目样例一致。
三、说明
1、提供的代码直接评测不能编译，原因是倒数第三代码
printf("%d\n", dp[m][0](@ref); // 传m次后回到初始点0号位的方案数多了【(@ref】，去掉后使用【Cena】评测通过。
