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
2
4

输入输出样例 #2

输入 #2

输出 #2

2
2
4

输入输出样例 #3

输入 #3

输出 #3

6
6
12

输入输出样例 #4

输入 #4

输出 #4

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)$ 。只使用了常数个额外变量。

示例代码

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年12月1日

luogu-B3951 [GESP样题五级] 小杨的队列 luogu-P1115 最大子段和