P11491 [BalticOI 2023] Tycho-题解

skyx · 2026-03-20 20:26:13 · 题解

P11491 [BalticOI 2023] Tycho-题解

怎么题解区都觉得简单？畏惧了。

简要题意

你从数轴上的 0 点出发，要到 b 点。

每秒你可以：

• 前进一步（坐标 +1）
• 原地等待（坐标不变）

对于每个非负整数 k，在第 k \times p 秒末（即 0, p, 2p, 3p, \dots 秒末），如果你的坐标不是 0、b、以及给定的 a_1,a_2,\dots,a_n 中的任何一个，那么就会产生 d 的代价。每秒会产生 1 的代价。

最小化总代价。

题目分析

转化题意

考虑转移，注意到疯狂的数据范围，肯定不能设计与距离或时间有关的状态，考虑为什么要给你数组 a？

不妨设计与安全点有关的状态。定义 dp_i 为走到第 i 个安全点的最小代价，但你发现后面的转移也要扯到走到这里的时间，也就是要枚举，显然不可接受。

如何减少分子上第二项代价，考虑我们要在一些安全坐标上停留到 k \times p 秒，其中 k 是非负整数，然后再往后走，这样能尽可能减少代价。

在这个基础上，我们可以对这个状态作补充：第 i 个安全点等到 k \times p 秒的最小代价是多少。

这样有什么好处？发现大代价是周期来的，这样做就只用考虑两点之间的距离，这中间的大代价次数也是可计算的，避免了对时间的胡乱考虑。

转移方程

考虑从 j 号安全点到 i 号安全点，那么：

其中第二项是补全到 p 的倍数，保持状态的一致；第三项是计算两点间的大代价次数。

考虑这个转移的意义：

• 选出一部分安全点，在这些点上，时间被对齐到 k \times p。
• 而两个选出来的点之间的那些时刻，如果落在不安全位置，大代价直接算入这段转移代价里。

到这里可以设计一个平方的算法，可以通过子任务 4。

进一步优化

你发现这式子很不可做，上下取整怎么搞？

我们考虑对安全点的坐标按模 p 分类，把坐标写成 a_i=q_i p+r_i 的形式，那么对于原始转移中的 a_i-a_j 项，就可以写成 (q_i-q_j)p+(r_i-r_j) 的形式。

对于 (q_i-q_j)p+(r_i-r_j) 这个东西除 p 的取整就要考虑 (r_i-r_j) 的正负：

当 r_j<r_i 时

这时 \dfrac{r_i-r_j}{p} 是一个在 (0,1) 之间的小数，所以：

而：

代回去：

也就是：

当 r_j\ge r_i 时

这时不用多补一个 p，所以：

第二项也就是：

代回去：

化一下：

和 i 相关的东西是不一样的，动不了。我们考虑把和 j 相关的东西提出来：

于是转移就变成了非常自然的两类：

• 若 r_j<r_i：

• 若 r_j\ge r_i：

数据结构

现在只剩一个问题：怎么快速求出 \min_{r_j<r_i}G(j) 和 \min_{r_j\ge r_i}G(j)。

你发现这个东西类似单点修，区间查问题。

注意 r_j 只和 a_j\bmod p 有关，因此我们可以对余数建一棵线段树，在余数 r 的位置维护，所有已经处理过的点中，满足 a_j\bmod p=r 的最小 G(j)。

于是：

• 对前面的第一种转移，查询区间 [0,r_i-1]，得到 r_j<r_i 的最优前驱。
• 对前面的第二种转移，查询区间 [r_i,p-1]，得到 r_j\ge r_i 的最优前驱。
• 算出 dp_i 后，再用 G(i) 更新余数 r_i 的位置。

由于余数的范围很大，要使用动态开点线段树。

答案计算

上面的 dp_i 定义要求，到达 a_i 后，还要把时间补到某个 p 的倍数。

但最后到达终点 b 时，不需要再补到 p 的倍数。所以最后从某个安全点 a_i 直接走到终点 b 的代价是：

• 时间代价：b-a_i。
• 中间额外代价次数：\left\lfloor \dfrac{b-a_i-1}{p}\right\rfloor。

答案就是下面这个式子：

值得注意的是，起点，也就是 i=0 也是安全点，要注意循环的起点。

代码实现

记得开 long long。

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

#define int long long
#define ll long long
#define db double
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
const int MX = 9e18;
const int N = 1e5 + 5;
int a[N];
int val[N];
int dp[N];
int root;
struct node 
{
    int mn;
    int ls,rs;
} tr[N*80];

int cnt = 0;

void update(int &c, int x, int k, int l, int r) {
    if (!c) 
    {
        c = ++cnt; 
        auto &t = tr[c];
        t.mn = MX;
    } 
    auto &t = tr[c];
    t.mn = min(t.mn, k);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x <= mid) update(t.ls, x, k, l, mid);
    else update(t.rs, x, k, mid + 1, r);
}

ll query(int c, int L, int R, int l, int r) 
{
    if (!c) return MX;
    auto &t = tr[c];
    if (l > R || r < L) return MX;
    if (L <= l && r <= R) return t.mn;
    int mid = (l + r) / 2;
    return min(query(t.ls, L, R, l, mid), query(t.rs, L, R, mid + 1, r));
}

int b, p, d, n;

int G(int x)
{
    return dp[x] - val[x] - (a[x] / p) * d;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> b >> p >> d >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        val[i] = a[i] - a[i] % p;
    }

    root = 0;
    dp[0] = 0;
    a[0] = 0;
    val[0] = 0;

    update(root, 0, G(0), 0, p - 1);

    for (int i = 1; i <= n; i++)
    {
        dp[i] = MX;
        int h = val[i] + (a[i] / p) * d;
        int r = a[i] % p;

        // r_j < r_i
        dp[i] = min(dp[i], h + query(root, 0, r - 1, 0, p - 1) + p);

        // r_j >= r_i
        dp[i] = min(dp[i], h + query(root, r, p - 1, 0, p - 1) - d);

        update(root, r, G(i), 0, p - 1);
    }

    int ans = MX;
    for (int i = 0; i <= n; i++)
    {
        ans = min(ans, dp[i] + b - a[i] + (b - a[i] - 1) / p * d);
    }
    cout << ans << endl;

    return 0;
}