专栏文章

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

CCleverSea
P13095题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioygp8z
此快照首次捕获于
2025/12/03 03:12
3 个月前
此快照最后确认于
2025/12/03 03:12
3 个月前
查看原文
没学过对数怎么办？

思路

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

步骤

  • 将股票价格序列 aia_i 转化为相邻日价格差的正值序列 bi=max⁡(0,ai+1−ai)b_i = \max(0, a_{i+1} - a_i)，其中 bib_i 表示第 ii 天到第 i+1i+1 天的对数收益。
  • 构建前缀和数组 prefpref，快速计算任意区间 [s,t][s, t] 的收益和。
  • 对每笔借款 (si,ti)(s_i, t_i)：
    • 若 si=tis_i = t_i，区间无交易，收益为 00，输出 kk。
    • 否则，区间收益和为 pref[ti−1]−pref[si−1]pref[t_i-1] - pref[s_i-1]，最终资产对数 w=k+收益和w = k + \text{收益和}。

CodeCode

CPP
#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(n)，查询为 O(m)O(m)，总复杂度 O(n+m)O(n + m)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...