接下来是所有的题解…

好的，这是完整的6道题目及详细题解，包含C++代码实现。

—

## **题目1：小明的糖果分配**

### **题目分析**
这是一个简单的模运算问题。只需要计算 `n % m`：
– 如果余数为0，说明可以平分，输出 `n / m`
– 如果余数不为0，小明需要吃掉余数颗糖果，输出余数

### **C++代码**
“`cpp
#include <iostream>
using namespace std;

int main() {
int n, m;
cin >> n >> m;

if (n % m == 0) {
cout << n / m << endl;
} else {
cout << n % m << endl;
}

return 0;
}
“`

### **代码说明**
– 时间复杂度：O(1)
– 空间复杂度：O(1)
– 关键点：使用取模运算判断是否能够整除

—

## **题目2：小明的数字反转**

### **题目分析**
将数字反转可以通过数学运算实现：
1. 不断取原数字的个位数（`n % 10`）
2. 将个位数加到结果中（`result = result * 10 + digit`）
3. 原数字除以10（`n /= 10`）
4. 重复直到原数字为0

### **C++代码**
“`cpp
#include <iostream>
using namespace std;

int main() {
int n;
cin >> n;

// 处理特殊情况：n为0
if (n == 0) {
cout << 0 << endl;
return 0;
}

int result = 0;
while (n > 0) {
result = result * 10 + n % 10;
n /= 10;
}

cout << result << endl;
return 0;
}
“`

### **代码说明**
– 时间复杂度：O(d)，d为数字的位数
– 空间复杂度：O(1)
– 注意：这种方法自动处理了前导零的问题

—

## **题目3：小明的购物计划**

### **题目分析**
这是一个经典的贪心问题。要买到最多的玩具，应该优先购买价格便宜的玩具：
1. 将玩具价格排序
2. 从最便宜的开始买，直到钱不够为止

### **C++代码**
“`cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
int n, k;
cin >> n >> k;

vector<int> prices(n);
for (int i = 0; i < n; i++) {
cin >> prices[i];
}

// 按价格从小到大排序
sort(prices.begin(), prices.end());

int count = 0;
int total_cost = 0;

for (int i = 0; i < n; i++) {
if (total_cost + prices[i] <= k) {
total_cost += prices[i];
count++;
} else {
break;
}
}

cout << count << endl;
return 0;
}
“`

### **代码说明**
– 时间复杂度：O(n log n)，主要是排序的复杂度
– 空间复杂度：O(n)
– 贪心策略证明：优先买便宜的玩具可以得到最大数量

—

## **题目4：小明的迷宫探险**

### **题目分析**
使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历迷宫：
1. 从起点开始搜索
2. 标记访问过的位置，避免重复计数
3. 向四个方向扩展（上、下、左、右）
4. 统计所有能到达的格子数量

### **C++代码**
“`cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 四个方向：上、右、下、左
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m;
vector<string> maze;
vector<vector<bool>> visited;

// DFS搜索
int dfs(int x, int y) {
// 越界检查
if (x < 0 || x >= n || y < 0 || y >= m) return 0;
// 墙壁或已访问检查
if (maze[x][y] == ‘#’ || visited[x][y]) return 0;

visited[x][y] = true;
int count = 1; // 当前格子

// 向四个方向搜索
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
count += dfs(nx, ny);
}

return count;
}

int main() {
cin >> n >> m;
maze.resize(n);
visited.resize(n, vector<bool>(m, false));

for (int i = 0; i < n; i++) {
cin >> maze[i];
}

int start_x, start_y;
cin >> start_x >> start_y;
// 题目中行列从1开始，程序中从0开始
start_x–;
start_y–;

int result = dfs(start_x, start_y);
cout << result << endl;

return 0;
}
“`

### **代码说明**
– 时间复杂度：O(n × m)，每个格子最多访问一次
– 空间复杂度：O(n × m)，用于存储访问标记
– 注意：起点坐标需要从1-based转换为0-based

—

## **题目5：小明的数列问题**

### **题目分析**
这是一个动态规划问题：
– 状态定义：dp[i] 表示数列第i项的值
– 递推关系：dp[i] = dp[i-1] + dp[i-3]
– 初始条件：dp[1] = dp[2] = dp[3] = 1
– 由于结果很大，需要取模

### **C++代码**
“`cpp
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 10007;

int main() {
int n;
cin >> n;

if (n <= 3) {
cout << 1 << endl;
return 0;
}

vector<int> dp(n + 1);
dp[1] = dp[2] = dp[3] = 1;

for (int i = 4; i <= n; i++) {
dp[i] = (dp[i-1] + dp[i-3]) % MOD;
}

cout << dp[n] << endl;
return 0;
}
“`

### **优化版本（节省空间）**
“`cpp
#include <iostream>
using namespace std;

const int MOD = 10007;

int main() {
int n;
cin >> n;

if (n <= 3) {
cout << 1 << endl;
return 0;
}

int a = 1, b = 1, c = 1, d;
for (int i = 4; i <= n; i++) {
d = (c + a) % MOD;
a = b;
b = c;
c = d;
}

cout << c << endl;
return 0;
}
“`

### **代码说明**
– 时间复杂度：O(n)
– 空间复杂度：O(1)（优化版本）
– 关键点：理解递推关系，注意取模运算

—

## **题目6：小明的素数对**

### **题目分析**
需要解决两个问题：
1. 判断一个数是否为素数
2. 枚举所有可能的数对(i, j)，检查i, j和i+j是否都是素数

优化：预先计算1到2n范围内的所有素数（因为i+j最大为2n）

### **C++代码**
“`cpp
#include <iostream>
#include <vector>
using namespace std;

// 埃拉托斯特尼筛法求素数
vector<bool> getPrimes(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}

int main() {
int n;
cin >> n;

// 预计算素数，最大需要判断2n
vector<bool> isPrime = getPrimes(2 * n);

int count = 0;
// 枚举所有素数对
for (int i = 2; i <= n; i++) {
if (!isPrime[i]) continue; // i必须是素数
for (int j = i + 1; j <= n; j++) {
if (!isPrime[j]) continue; // j必须是素数
if (isPrime[i + j]) { // i+j也必须是素数
count++;
}
}
}

cout << count << endl;
return 0;
}
“`

### **代码说明**
– 时间复杂度：O(n²)，但实际运行很快，因为素数比较稀疏
– 空间复杂度：O(n)
– 优化：使用筛法预处理素数，使得判断素数的时间复杂度为O(1)

—

## **总结**

这6道题目涵盖了竞赛编程的基础知识点：

1. **基础语法**：输入输出、条件判断、循环
2. **数学运算**：取模、数字反转
3. **贪心算法**：排序后选择最优解
4. **搜索算法**：DFS遍历图或网格
5. **动态规划**：状态转移和递推关系
6. **数论基础**：素数判断和筛法

建议按照题目顺序练习，逐步提升编程能力和算法思维。每道题目都提供了清晰的解题思路和代码实现，适合团队学习和讨论。