【GESP】C++五级练习（贪心思想考点） luogu-P9532 [YsOI2023] 前缀和
GESP C++ 五级练习题，虽然题目名称叫前缀和，但却是贪心考点，确实有点奇怪的误导。题目难度⭐⭐★☆☆，五级来说难度适中。洛谷难度等级普及−
luogu-P9532 [YsOI2023] 前缀和
题目要求
题目背景
Ysuperman 模板测试的试机题。
小心立秋，小心秋丽。
题目描述
立秋有一个长度为 $n$ 的数组 $a$，所有数字都是正整数，并且除了其中第一个数字以外其它数字都等于前面所有数字的和。
例如，数组 $[1,1,2,4,8,16]$ 就有可能是立秋有的一个数组，因为除了第一个数字 $1$，后面的每个数字都是前面数字的和，例如：
- 第二个数字 $1=1$。
- 第三个数字 $2=1+1$。
- 第四个数字 $4=1+1+2$。
- 第五个数字 $8=1+1+2+4$。
- 第六个数字 $16=1+1+2+4+8$。
现在立秋告诉了秋丽数字 $x$ 存在于这个数组中，秋丽希望知道 $a_n$ 最小会是多少，或者说整个数组最后一个数字最小有多少。
输入格式
本题有多组测试数据。
输入第一行一个数字 $T$ 表示测试数据组数。
接下来 $T$ 行每行两个正整数 $n,x$。
输出格式
输出共 $T$ 行，分别表示每组测试数据的答案。
对于某组数据 $n,x$，输出一行一个正整数表示可能的最小的 $a_n$。
输入输出样例 #1
输入 #1
1
2
3
4
3
2 2
3 2
4 2
输出 #1
1
2
3
2
2
4
输入输出样例 #2
输入 #2
1
2
3
4
3
3 1
3 2
3 4
输出 #2
1
2
3
2
2
4
输入输出样例 #3
输入 #3
1
2
3
4
3
2 6
3 6
4 6
输出 #3
1
2
3
6
6
12
输入输出样例 #4
输入 #4
1
2
3
4
3
3 3
3 6
3 12
输出 #4
1
2
3
6
6
12
说明/提示
样例 1 解释
- 第一组数据只有唯一可能的数组 $[2,2]$，所以答案为 $2$；
- 第二组数据有两种可能的数组，分别是 $[2,2,4]$ 和 $[1,1,2]$，所以答案为 $2$；
- 第三组数据有两种可能的数组，分别是 $[2,2,4,8]$ 和 $[1,1,2,4]$，所以答案为 $4$。
样例 2 解释
- 第一组数据只有唯一可能的数组 $[1,1,2]$，所以答案为 $2$；
- 第二组数据有两种可能的数组 $[1,1,2]$ 和 $[2,2,4]$，所以答案为 $2$；
- 第三组数据有两种可能的数组 $[2,2,4]$ 和 $[4,4,8]$，所以答案为 $4$。
数据范围
对于前 $30\%$ 的数据，满足 $x$ 不能被 $2$ 整除，或者说 $2$ 不是 $x$ 的一个因数，或者说 $x$ 是奇数。
另有 $30\%$ 的数据，满足 $x$ 可以被 $2^{n-2}$ 整除，或者说 $2^{n-2}$ 是 $x$ 的一个因数。
另有 $20\%$ 的数据，满足 $x\le 1000$，可以证明在这个数据范围下答案可以使用一个 int 类型变量存储。
对于 $100\%$ 的数据，满足 $1\le T\le 10^4$，$2\le n\le 20$，$1\le x\le 10^9$。
题目分析
这是一道数论 + 贪心的题目。关键在于理解数列 $2^{i-2}$ 的增长性质，并根据 $x$ 的二进制因子特征来确定其在数组中的极限位置。
1. 题目规律推导
首先，我们需要分析数组 $a$ 的生成规律。 题目描述：除了第一个数字 $a_1$ 以外，其它数字都等于前面所有数字的和。
设 $a_1 = k$（$k$ 为正整数），则：
- $a_2 = a_1 = k$
- $a_3 = a_1 + a_2 = k + k = 2k$
- $a_4 = a_1 + a_2 + a_3 = 2k + 2k = 4k$
- $a_5 = a_1 + a_2 + a_3 + a_4 = 4k + 4k = 8k$
- …
通项公式为： \(a_i = \begin{cases} k & i=1, 2 \\ k \times 2^{i-2} & i > 2 \end{cases}\)
可以看出，数组除了前两项相等外，从第 3 项开始，每一项都是前一项的 2 倍。这是一个以 $2$ 为公比的等比数列性质。
2. 问题分析
已知条件：
- 数组长度为 $n$。
- 数字 $x$ 存在于数组 $a$ 中（即 $x = a_i$，其中 $1 \le i \le n$）。
目标：
求 $a_n$ 的最小值。
推导：
假设 $x$ 处于数组的第 $i$ 位（即 $x = a_i$）。 根据通项公式，数组的最后一位 $a_n$ 和第 $i$ 位 $a_i$ 的关系如下（假设 $i \ge 2$）： \(a_n = a_i \times 2^{n-i} = x \times 2^{n-i}\)
为了让 $a_n$ 最小，我们需要让指数 $n-i$ 最小。 因为 $n$ 是固定的，所以我们需要让 $i$ 尽可能大。 结论：也就是要让数字 $x$ 在数组中出现的位置尽可能靠后。
3. 限制条件
虽然我们想让 $x$ 的位置 $i$ 越靠后越好，但是 $i$ 的取值受到两个限制：
- 数组长度限制：$x$ 必须在数组内，所以 $i \le n$。
- 整除性质限制：由公式 $x = a_i = k \times 2^{i-2}$ 可知，$k = \frac{x}{2^{i-2}}$。 因为题目要求所有数字都是正整数，所以 $k$ 必须是整数。这意味着 $x$ 必须能被 $2^{i-2}$ 整除。换句话说，$x$ 中包含的因子 2 的个数，决定了它最远能排在第几位。
4. 算法流程（贪心策略）
根据以上分析，解题逻辑如下：
- 计算 $x$ 的“潜力”：
计算 $x$ 能够被 2 整除多少次，记为 cnt。 那么 $x$ 最多能放在第 cnt + 2 的位置（因为 $a_{cnt+2} = k \times 2^{cnt}$，此时 $k$ 为奇数，无法再除以 2）。
- 确定 $x$ 的实际位置 $i$：
$x$ 的位置 $i$ 取决于它自身的因子 2 的个数，以及数组的总长度 $n$。 \(i_{max} = \max(n, \text{cnt} - 2)\)
- 如果 $x$ 的因子 2 很多，多到超过了数组长度，那么它最优只能放在第 $n$ 位（此时 $a_n=x$）。
- 如果 $x$ 的因子 2 很少，它就不得不放在比较靠前的位置。
- 计算最终答案 $a_n$：
确定了 $x$ 的最优位置 $i_{max}$ 后，答案即为： \(a_n = x \times 2^{n - i_{max}}\)
- 特殊情况处理
- $x=1$：只能是 $1, 1, 2, 4…$，答案直接是 $2^{n-2}$。
- $n \le 2$：无论 $n=1$ 还是 $n=2$，只要 $x$ 在数组里，最小值就是 $x$ 本身。
5. 复杂度分析
- 时间复杂度：$O(T \log x)$。每个测试用例需要 $O(\log x)$ 来计算 $x$ 的因子 2 个数。
- 空间复杂度：$O(1)$。只使用了常数个额外变量。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cmath>
#include <iostream>
int main() {
int T;
std::cin >> T;
while (T--) {
int n, x;
std::cin >> n >> x;
// 特判 x=1 的情况
// 如果 x=1，由于所有数字都是正整数，k 只能为 1。
// 序列只能是 1, 1, 2, 4...
// a[n] = 1 * 2^(n-2)
if (x == 1) {
// pow 返回 double，对于大数可能丢失精度，但在题目范围内 (2^18)
// 是安全的。 更严谨的写法是使用位运算：(1LL << (n - 2))
std::cout << (long long)std::pow(2, n - 2) << std::endl;
continue;
}
// 特判 n <= 2 的情况
// 如果 n=1，a[1]=x。
// 如果 n=2，a[2]=x (因为 a[2]=a[1]，若 x 在数组中，最小 a[2] 就是 x)。
if (n <= 2) {
std::cout << x << std::endl;
continue;
}
// 计算 x 中包含多少个因子 2，记为 cnt。
// 同时将 x 除以这些因子 2，剩下的 x 即为 k 的奇数部分 (odd_part)。
int cnt = 0;
while (x % 2 == 0) {
cnt++;
x /= 2;
}
// power 取 max(cnt, n-2)。
int power = std::max(cnt, n - 2);
// 输出结果
// 使用 long long 防止溢出
std::cout << (long long)std::pow(2, power) * x << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
