「BalticOI 2023」Tycho 题解

题目分析

探测车需要从位置 $0$ 移动到位置 $b$，每秒移动 $1$ 单位距离。每秒受到 $1$ 点环境伤害，每 $p$ 秒还会受到额外的 $d$ 点辐射伤害（除非在藏身点、起点或终点）。车辆可以在任意位置停留任意整数秒。

目标：最小化总伤害 = 环境伤害 + 辐射伤害。

解题思路

关键观察

1. 模周期性：辐射伤害只与时间模 $p$ 有关
2. 等待策略：在藏身点等待可以调整到达后续位置的时间模 $p$
3. 最优子结构：到达每个藏身点的最小伤害可以通过前面藏身点的信息计算

算法核心

使用动态规划结合线段树来高效计算最优解。

代码详解

数据结构定义

struct SegmentTree {
    int n;
    vector<long long> st;
    // 线段树用于维护每个余数对应的最小代价
};

线段树用于维护每个余数 $r$（位置模 $p$）对应的最小代价，支持：

• 单点更新：用更小的代价更新某个余数
• 区间查询：查询某个余数区间的最小代价

主算法流程

1. 输入与初始化

long long b, p, d, n;
cin >> b >> p >> d >> n;
vector<pair<long long, int>> a(n + 1);
vector<long long> c(1, 0);  // 存储所有不同的余数

2. 预处理余数信息

for (int i = 1; i <= n; i++) {
    cin >> a[i].first;
    c.push_back(a[i].first % p);  // 计算每个藏身点位置模 p 的余数
}

// 去重并排序余数
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());

// 为每个藏身点分配余数编号
for (int i = 1; i <= n; i++) {
    a[i].second = upper_bound(c.begin(), c.end(), a[i].first % p) - c.begin();
}

3. 初始化答案

long long result = b + ((b + p - 1) / p - 1) * d;

这是不在任何藏身点停留的代价：

• $b$：环境伤害（移动 $b$ 秒）
• $\lceil \frac{b}{p} \rceil - 1$：辐射伤害次数（起点不受伤害）

4. 动态规划计算

for (int i = 1; i <= n; i++) {
    // 计算到达当前藏身点的最小代价
    long long f = min(tree.Query(1, a[i].second - 1) + p, 
                     tree.Query(a[i].second, c.size()) - d);
    
    // 计算到达当前藏身点的总代价
    long long g = f + (a[i].first / p) * (p + d);
    
    // 更新最终答案：从当前藏身点到终点的代价
    result = min(result, g + (b - a[i].first) + 
                        ((b - a[i].first + p - 1) / p - 1) * d);
    
    // 更新线段树
    tree.Update(a[i].second, f);
}

关键公式解释

状态转移公式

f = min(
    tree.Query(1, a[i].second - 1) + p,      // 情况1：等待到下一个周期
    tree.Query(a[i].second, c.size()) - d    // 情况2：直接到达，节省d点伤害
)

• 情况1：在之前某个藏身点等待，使得到达当前藏身点时余数更小
• 情况2：直接到达，利用当前余数关系节省伤害

代价计算

g = f + (a[i].first / p) * (p + d)

• $f$：调整后的基础代价
• $\frac{a[i].first}{p} \times (p + d)$：完整周期内的伤害（每个周期 $p$ 点环境伤害 + $d$ 点辐射伤害）

最终代价

result = min(result, g + (b - a[i].first) + 
                    ((b - a[i].first + p - 1) / p - 1) * d)

• $g$：到达当前藏身点的代价
• $b - a[i].first$：剩余环境伤害
• $\lceil \frac{b - a[i].first}{p} \rceil - 1$：剩余辐射伤害次数

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 排序余数：$O(n \log n)$
  • 线段树操作：$O(\log n)$ 每次，共 $O(n \log n)$
• 空间复杂度：$O(n)$

总结

本题通过将问题转化为模 $p$ 意义下的优化问题，利用线段树高效维护不同余数对应的最小代价，实现了在大数据范围（$b \leq 10^{12}$）下的高效求解。算法巧妙利用了周期性性质和动态规划的最优子结构特性。