题解：P12033 [USACO25OPEN] Package Pickup P

· · 题解

题意

数轴上的一些整点上放了牛和草。你每秒可以选择一头牛，令其向左或向右移动一个单位长度。每当一头牛和一捆草位于同一个位置时，牛就会吃掉这捆草。求吃完所有草的最短时间。

牛和草的初始位置以特殊方式给出：给定一个常量 m。对于牛，给出 n 个区间 [l, r]，表示 l, l + m, l + 2m, \dots, r 这些位置放了牛，保证 m \mid (r - l)。对于草同理。

分析

先考虑 Subtask 1，即牛和草的总数不超过 2 \times 10^5 时怎么做。

考虑分析一头牛的行为。一头牛可以吃光它经过的所有位置上放的草，而它经过的所有位置是一段区间。并且，牛经过了整个区间，当且仅当它经过了区间的左右端点，因此固定区间时一头牛的代价很容易计算出来。

考虑分析所有牛的行为。通过调整法可以发现，可以认为任意两头牛的区间都是不交的。

考虑一个很暴力的转化：把数轴按照牛和草初始所在的位置分段，则最优解中每一段中所有边经过的次数相等，且均为 0, 1, 2。因此直接枚举的状态量非常少。

考虑判定一个 0, 1, 2 的方案是否合法。考虑找充要条件。列几个条件可以发现，合法当且仅当：

用这个充要条件容易写出 DP。设 f_{i, j}（j \in [0, 4]）表示：考虑了与前 i 个牛和草相邻的边，

转移是容易的。注意特判同一个位置有两头牛的情况，此时两头牛可以分别移动。

然后一般情况是容易的。观察到 m 为定值，考虑每次跳过一个周期。本质不同的周期个数是 O(n) 的。转移可以用 (\min, +) 矩阵乘法描述。线段树 + 快速幂即可，复杂度 O(n \log m)，带 5^3 的常数。

实现

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

struct Mat {
    ll a[5][5];

    Mat operator*(const Mat &b) const {
        Mat ans;
        memset(ans.a, 0x3f, sizeof ans.a);
        rep (i, 0, 4)
            rep (j, 0, 4)
                rep (k, 0, 4)
                    ans.a[i][k] = min(ans.a[i][k], a[i][j] + b.a[j][k]);
        return ans;
    }

    static Mat Make(int b, ll d) {
        Mat ans;
        memset(ans.a, 0x3f, sizeof ans.a);
        if (b == 0) {
            fill(all(ans.a[2]), d);
            fill(all(ans.a[3]), 2 * d);
            memset(ans.a[4], 0, sizeof ans.a[4]);
        } else if (b == 1) {
            ans.a[2][1] = ans.a[2][2] = ans.a[2][4] = d;
            ans.a[3][0] = ans.a[3][3] = ans.a[3][4] = 2 * d;
            memset(ans.a[4], 0, sizeof ans.a[4]);
        } else {
            ans.a[0][0] = ans.a[0][4] = d;
            ans.a[1][1] = ans.a[1][4] = 2 * d;
            ans.a[2][2] = d;
            ans.a[3][3] = 2 * d;
            ans.a[4][2] = ans.a[4][3] = 0;
        }
        return ans;
    }
};

struct I {
    ll c, g;
    ll bg, ed;
    int b;
    Mat mul;

    I operator+(const I &x) const {
        if (c == 0 && g == 0 && x.c == 0 && x.g == 0)
            return {.ed = ed + x.ed};
        if (c == 0 && g == 0) {
            I ans = x;
            ans.bg += ed;
            return ans;
        }
        if (x.c == 0 && x.g == 0) {
            I ans = *this;
            ans.ed += x.ed;
            return ans;
        }
        return {c + x.c, g + x.g, bg,
                x.ed,    x.b,     x.mul * Mat::Make(b, ed + x.bg) * mul};
    }

    I operator*(ll n) const {
        assert(n >= 0);
        I ans = {}, add = *this;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1)
                ans = ans + add;
            add = add + add;
        }
        return ans;
    }
};

vector<ll> raw;

struct SegT {
    static constexpr int N = (1 << 16) + 10;

    int n;
    I t[2 * N];

    void Build() {
        n = sz(raw) == 2 ? 1 : 2 << (31 ^ __builtin_clz(sz(raw) - 2));
        rep (i, 0, n - 1) {
            t[i + n] = {.ed = i <= sz(raw) - 2 ? raw[i + 1] - raw[i] : 0};
            memset(t[i + n].mul.a, 0x3f, sizeof t[i + n].mul.a);
            rep (j, 0, 4)
                t[i + n].mul.a[j][j] = 0;
        }
        for (int i = n - 1; i >= 1; --i)
            t[i] = t[2 * i] + t[2 * i + 1];
    }

    void Upd(int x, ll c, ll g) {
        x += n;
        t[x].c += c, t[x].g += g;
        if (t[x].c > 1) {
            t[x].b = 0;
        } else if (t[x].c > 0) {
            t[x].b = 1;
        } else if (t[x].g > 0) {
            t[x].b = 2;
        }
        while (x > 1) {
            x >>= 1;
            t[x] = t[2 * x] + t[2 * x + 1];
        }
    }

    I Qry() {
        return t[1];
    }
} sgt;

ll m;
int n, p;

struct E {
    ll t, c, g;

    bool operator<(E x) const {
        return t < x.t;
    }
};

vector<E> e;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);

    cin >> m >> n >> p;
    raw = {0, m};

    rep (i, 1, n) {
        ll l, r;
        cin >> l >> r;
        raw.push_back(l % m);
        e.push_back({l, 1, 0}), e.push_back({r + m, -1, 0});
    }

    rep (i, 1, p) {
        ll l, r;
        cin >> l >> r;
        raw.push_back(l % m);
        e.push_back({l, 0, 1}), e.push_back({r + m, 0, -1});
    }

    sort(all(raw));
    raw.erase(unique(all(raw)), end(raw));
    sort(all(e));
    sgt.Build();
    I ans = {};
    ll lst = -1;
    for (auto [t, c, g] : e) {
        if (lst != -1)
            ans = ans + sgt.Qry() * (t / m - lst);
        lst = t / m;
        sgt.Upd(lower_bound(all(raw), t % m) - begin(raw), c, g);
    }

    ll f[5];
    rep (i, 0, 4)
        f[i] = ans.mul.a[i][4];
    if (ans.b <= 1)
        cout << *min_element(all(f)) << '\n';
    else
        cout << min(f[2], f[3]) << '\n';
}