题解：P13095 [FJCPC 2025] 炒股高手

CleverSea · 2025-07-08 11:45:58 · 题解

没学过对数怎么办？

思路

每笔借款从第 s_i 天开始到第 t_i 天结束，初始资金为 e^k 元。由于可以购买非整数份股票且交易次数不限，所以最优策略是抓住所有价格上升的波段：只要相邻两天后一天价格高于前一天，就在前一天全仓买入并在后一天卖出，从而获得对数域上的收益累加。

步骤

• 将股票价格序列 a_i 转化为相邻日价格差的正值序列 b_i = \max(0, a_{i+1} - a_i)，其中 b_i 表示第 i 天到第 i+1 天的对数收益。

• 构建前缀和数组 pref，快速计算任意区间 [s, t] 的收益和。

• 对每笔借款 (s_i, t_i)：

  • 若 s_i = t_i，区间无交易，收益为 0，输出 k。
  • 否则，区间收益和为 pref[t_i-1] - pref[s_i-1]，最终资产对数 w = k + \text{收益和}。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];      // 存储每天的股票价格对数
int b[N];      // 存储相邻日价格差的正值序列
int pref[N];   // 前缀和数组

int main()
{
    // 其实不关同步流也可以
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int k;
    cin >> k;
    // 计算相邻日价格差的正值序列 b
    for (int i = 1; i < n; i++)
    {
        int diff = a[i + 1] - a[i];
        b[i] = (diff > 0) ? diff : 0;
    }
    // 构建前缀和数组 pref
    pref[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        pref[i] = pref[i - 1] + b[i - 1];
    }
    // 处理每笔借款
    for (int i = 0; i < m; i++)
    {
        int s, t;
        cin >> s >> t;
        // 如果借款开始日和结算日相同，无法交易，直接返回 k
        if (s == t)
        {
            cout << k << '\n';
        }
        else
        {
            int sum = pref[t] - pref[s]; // 计算区间 [s, t] 内的收益和
            cout << k + sum << '\n'; // 研究表明，'\n' 换行比 endl 要快得多
        }
    }
    return 0; // 是好习惯
}

其中预处理时间复杂度为 O(n)，查询为 O(m)，总复杂度 O(n + m)。