省202505

# STEMA考试 C++试卷（5月）- STEMA省考
## 一、选择题
### 第一题
下列选项中，能够正确定义并初始化浮点型变量的是（B ）。
A、int a = 10;
B、float a = 2.0;
C、char a = 'A';
D、int a = 1.2;

### 第二题
执行语句 cout << "1 + 2 = " << 1 + 2; 的结果是（ D）。
A、1 + 2 = 1 + 2
B、3 = 1 + 2
C、3 = 3
D、1 + 2 = 3

### 第三题
运行以下程序，输出的结果是（ D ）。
```cpp
int x = 5;
if(x > 0)
{
	int x = 10;
	cout << x << " ";
}
cout << x;
```
A、5 10
B、5 5
C、10 10
D、10 5

### 第四题
下列选项中，等式不成立的是（ C ）。
A、(1011)2 = 11
B、(1203)4 = 99
C、(356)8 = 237
D、(2DF)16 = 735

### 第五题
运行以下程序，输出的结果是（ D）。
```cpp
int arr[5] = {11, 31, 19, 125, 37};
int *p = arr + 2;
cout << p[1] << " " << (&arr[1] + 3 - p);
```
A、11 3
B、31 2
C、19 3
D、125 2

## 二、编程题
### 第一题
**编程实现：**水龙头
**题目描述：**小明在 0 时刻（初始时刻）将一个空桶放置在漏水的水龙头下。已知桶的容量为 H 升，并且每小时桶内的水量增加 x 升。小明每经过一个小时就会观察一次桶的水位。请计算小明第一次观察到桶内的水溢出时，距离初始时刻经过了多少小时？
**输入描述：**一行输入两个整数 H 和 x（10≤H≤100，1≤x≤20），分别表示桶的容量以及每小时桶内增加的水量，整数之间以一个空格隔开。
**输出描述：**输出一个整数，表示小明第一次看到桶中的水溢出来时，距离初始时刻经过的小时数。
**样例输入：**10 3
**样例输出：**4
```cpp
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int h,x;
    cin>>h>>x;
    cout<<ceil(h*1.0/x)<<endl;
    return 0;
}
```

### 第二题
**编程实现：**购物活动
**题目描述：**某在线购物平台推出了两种优惠活动。每位顾客在同一订单中只能享受其中一种优惠。
具体优惠规则如下：
1）五折优惠：顾客可以享受商品总价格的五折（即原价 × 0.5）；
2）满减优惠：如果顾客购买的商品总价格达到或超过 300 元，则可以在付款时直接减免 200 元。
给定顾客一笔订单的实际支付金额，请计算该顾客可能购买的商品总价格的最大值是多少？
例如：顾客实际支付 120 元。如果他最初选择的是优惠 1），则商品的总价格为 240 元；如果他最初选择的是优惠 2），则商品的总价格为 320 元；显然，该顾客购买的商品总价格的最大值为 320 元。
**输入描述：**输入一个整数（1≤整数≤1000），表示顾客实际支付的金额。
**输出描述：**输出一个整数，表示该顾客可能购买的商品总价格的最大值。
**样例输入：**120
**样例输出：**320
```cpp
#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int x1 = n*2;
    int x2 = n+200;
    cout<< (x1>x2?x1:x2)<<endl;
    return 0;
}
```

### 第三题
**编程实现：**吃粽子
**题目描述：**端午节到了，部落联盟准备了 k 个粽子。n 个部落首领按编号 1 到 n 轮流吃粽子。每轮每人吃的粽子数等于轮次数（第 1 轮每人吃 1 个，第 2 轮每人吃 2 个，依此类推），直到吃掉最后一个粽子。吃掉最后一个粽子的首领即为获胜者。给定 n 和 k，请计算获胜的首领编号。

例如，n = 3，k = 13，吃粽子过程如下：第一轮，1 号首领吃 1 个粽子（第 1 个），2 号首领吃 1 个粽子（第 2 个），3 号首领吃 1 个粽子（第 3 个）；第二轮，1 号首领吃 2 个粽子（第 4、5 个），2 号首领吃 2 个粽子（第 6、7 个），3 号首领吃 2 个粽子（第 8、9 个）；第三轮，1 号首领吃 3 个粽子（第 10、11、12 个），2 号首领吃掉最后一个粽子；显然，2 号首领是获胜者。

**输入描述：**一行输入两个整数 n 和 k（2≤n≤105，1≤k≤109），分别表示部落首领的数量以及粽子的数量，整数间以一个空格隔开。
**输出描述：**输出一个整数，表示获胜的首领编号。
**样例输入：**3 13
**样例输出：**2
```cpp
#include <iostream>
using namespace std;
int main() {
    int n,k;
    cin>>n>>k;
    bool r = false;
    while(true)
    {
        for(int i = 1;i<=k;i++)
        {
            n-=i;
            if(n<=0)
            {
                r=true;
                cout<<i<<endl;
                break;
            }
        }
        if(r)break;
    }
    return 0;
}
```

### 第四题
**编程实现：**弹球游戏
**题目描述：**有一个弹球游戏，游戏由 n 行 m 列的网格组成，除最后一行的网格外，其余每个网格中都有一个元素（仙人掌、旋风或地洞）。将弹球投向第一行的网格，弹球到达不同的元素网格会有不同的效果

![](/media/202512/2025-12-05_143435_5572320.9395243642439959.png)

![](/media/202512/2025-12-05_143451_1037940.14555059341506194.png)

![](/media/202512/2025-12-05_143503_3161690.9210036134093744.png)

![](/media/202512/2025-12-05_143519_6783080.6520697269065647.png)
**输入描述：**第一行输入两个整数 n、m（3≤n，m≤100），表示弹球游戏中网格的行数和列数，整数之间以一个空格隔开；接下来输入 n - 1 行，表示第 1 行到第 n - 1 行的网格情况，每行 m 个整数，整数只能为 1、2、3；1 表示该网格元素是仙人掌、2 表示该网格元素是旋风，3 表示该网格元素是地洞，同一行的整数之间以一个空格隔开；最后一行输入 m 个 0，0 表示该网格是第 n 行（最后一行）的网格，整数之间以一个空格隔开。
**输出描述：**输出一个整数，表示弹球从第一行到达最后一行的网格有多少条路线。
**样例输入：**
3 3
1 2 3
3 1 2
0 0 0
**样例输出：**
4
```cpp
#include <iostream>
#include <cstring> // 用于memset初始化数组
using namespace std;

const int MAX_SIZE = 100;
int memo[MAX_SIZE][MAX_SIZE]; // 记忆化数组，缓存(row, col)的计算结果

int dfs(int row, int col, int grid[MAX_SIZE][MAX_SIZE], int n, int m) {
    if (col < 0 || col >= m) return 0;
    if (row == n - 1) return 1;
    
    // 已计算过该位置，直接返回缓存结果
    if (memo[row][col] != -1) return memo[row][col];
    
    int res = 0;
    if (grid[row][col] == 3) {
        res = 0;
    } else if (grid[row][col] == 2) {
        res = dfs(row + 1, col, grid, n, m);
    } else if (grid[row][col] == 1) {
        res = dfs(row + 1, col - 1, grid, n, m) + dfs(row + 1, col + 1, grid, n, m);
    }
    
    // 缓存当前结果
    memo[row][col] = res;
    return res;
}

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

int grid[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

// 读取最后一行的0
    int temp;
    for (int j = 0; j < m; ++j) {
        cin >> temp;
    }

// 初始化记忆化数组为-1（表示未计算）
    memset(memo, -1, sizeof(memo));

int total = 0;
    for (int col = 0; col < m; ++col) {
        total += dfs(0, col, grid, n, m);
    }

cout << total << endl;
    return 0;
}
```

### 第五题
**编程实现：**零食好友
**题目描述：**
有 n 个小朋友去参加户外野餐活动，他们被分成了 m 个小组，保证每个小组至少有一个小朋友。在野餐过程中，同一小组内的任意两个小朋友都会互相分享零食，成为一对“零食好友”。你的任务是编写一个程序，请计算对于不同的分组方案，每种方案中的所有小组的“零食好友”的对数之和，并输出其中最小值和最大值分别是多少。

例如：n = 4，m = 2；4 个小朋友被分为 2 个小组。共有两种分组方案：
1）第一组 1 人，第二组 3 人，则第一组有 0 对“零食好友”，第二组有 3 对“零食好友”，共有 3对“零食好友”；
2）第一组 2 人，第二组 2 人，则第一组有 1 对“零食好友”，第二组有 1 对“零食好友”，共有 2对“零食好友”。则所有分组方案中，“零食好友”的对数之和的最小值是 2，最大值是 3。

**输入描述：**本题的每个测试点都有多组测试数据，格式如下：第一行输入一个整数 T（1≤T≤100），表示数据组数；接下来 T 组数据，每组数据输入仅一行，包含两个整数 n 和 m（1≤m≤n≤109），分别表示该组数据中小朋友的数量以及分组数量，整数之间以一个空格隔开。
**输出描述：**共 T 行，每行输出两个整数，表示对应的测试数据中“零食好友”对数的最小值和最大值，整数之间以一个空格隔开。
**样例输入：**
2
4 2
8 5
**样例输出：**
2 3
3 6
```cpp
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);

int T;
    cin >> T;
    while (T--) {
        long long n, m; // 用long long避免溢出（n、m可达1e9）
        cin >> n >> m;

// 计算最小值
        long long q = n / m;
        long long r = n % m;
        long long min_val = r * q * (q + 1) / 2 + (m - r) * q * (q - 1) / 2;

// 计算最大值
        long long max_val = (n - m + 1) * (n - m) / 2;

cout << min_val << " " << max_val << endl;
    }
    return 0;
}
```

### 解题思路
要解决这个问题，核心是利用组合数学公式推导“零食好友”对数的**最小值**和**最大值**，避免遍历（因n、m可达1e9，遍历会超时）。

#### 1. 核心公式
一个小组有`k`个小朋友时，“零食好友”对数为组合数 `C(k,2) = k*(k-1)/2`（即从k人中选2人的组合数）。
总对数是所有小组的`C(k_i,2)`之和，其中`k_1 + k_2 + ... + k_m = n`且每个`k_i ≥ 1`。

#### 2. 最大值推导
`C(k,2)`是凸函数（二次函数，开口向上），**极端分布**（一个组尽可能大，其余组为1）能得到最大值：
- `m-1`个组各1人，剩余1个组有`n-(m-1)`人。
- 最大值公式：`max = (n - m + 1) * (n - m) / 2`。

#### 3. 最小值推导
`C(k,2)`的最小值出现在**各组人数尽可能平均**时：
- 设`q = n / m`（每组基础人数），`r = n % m`（剩余需分配的人数）。
- 有`r`个组人数为`q+1`，`m-r`个组人数为`q`。
- 最小值公式：`min = r*q*(q+1)/2 + (m-r)*q*(q-1)/2`。

### C++ 实现代码
```cpp
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);

int T;
    cin >> T;
    while (T--) {
        long long n, m; // 用long long避免溢出（n、m可达1e9）
        cin >> n >> m;

// 计算最小值
        long long q = n / m;
        long long r = n % m;
        long long min_val = r * q * (q + 1) / 2 + (m - r) * q * (q - 1) / 2;

// 计算最大值
        long long max_val = (n - m + 1) * (n - m) / 2;

cout << min_val << " " << max_val << endl;
    }
    return 0;
}
```

### 代码解释
1. **输入优化**：`ios::sync_with_stdio(false);` 和 `cin.tie(nullptr);` 加速输入输出（应对多组数据）。
2. **数据类型**：使用`long long`存储n、m及计算结果，避免1e9级别的乘法溢出（int最大仅约2e9）。
3. **最小值计算**：
   - `q = n/m`：每组的基础人数（整数除法）。
   - `r = n%m`：需要多分配1人的小组数量。
   - 分别计算`r`个`q+1`人小组、`m-r`个`q`人小组的对数和。
4. **最大值计算**：直接套用极端分布的公式，计算唯一大组的对数（其余组为1人，对数为0）。

### 样例验证
#### 样例输入1：`4 2`
- 最小值：`q=4/2=2`，`r=0` → `0*2*3/2 + 2*2*1/2 = 2`。
- 最大值：`(4-2+1)*(4-2)/2 = 3*2/2 = 3`。
输出：`2 3`。

#### 样例输入2：`8 5`
- 最小值：`q=8/5=1`，`r=3` → `3*1*2/2 + 2*1*0/2 = 3`。
- 最大值：`(8-5+1)*(8-5)/2 = 4*3/2 = 6`。
输出：`3 6`。

### 边界情况测试
- 测试用例`n=5, m=3`：
  - 最小值：`q=1`，`r=2` → `2*1*2/2 +1*1*0/2=2`。
  - 最大值：`(5-3+1)*(5-3)/2=3*2/2=3`。
  - 输出：`2 3`（分组为`2,2,1`时和为2，分组为`3,1,1`时和为3）。

- 测试用例`n=1, m=1`：
  - 最小值/最大值：`0`（仅1人，无好友对）。
  - 输出：`0 0`。

该代码时间复杂度为O(T)（每组数据仅常数级计算），能高效处理T≤100、n/m≤1e9的所有情况。