目錄

一、提問詞

二、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;
}

?代碼說明

1. 狀態初始化：
   dp[0][0] = 1?表示初始球在 0 號位置（對應題目中的 1 號同學，簡化環狀運算）。
2. 狀態轉移：
   每個?dp[i][j]?由?i-1?次左側同學?(j-1+n) % n?和右側同學?(j+1) % n?的方案數之和。
3. 環狀處理：
   通過?%n?運算處理環的邊界，確保?j-1?和?j+1?在有效范圍內。
4. 時間復雜度：O(m·n)，滿足題目數據規模。

樣例驗證：
輸入?3 3?時，計算過程如下：

• dp[1][0] = dp[0][2] + dp[0][1] = 0
• dp[1][1] = dp[0][0] + dp[0][2] = 1
• dp[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】評測通過。