2024“钉耙编程”中国大学生算法设计超级联赛（7）

创作乐曲

正常的 DP 思路很容易想到。

只需要使用权值线段树动态开点 + DP 即可。

思路是更新某个坐标需要查找能和该坐标权值不冲突的贡献最优的那个贡献转移过来即可。

时间复杂度为 \(qn\log n\) ，显然会 TLE 。

考虑优化。

我们发现，能够更新当前坐标状态的位置其实只需要两个就够了。

这两个位置就是小于等于当前位置权值且差的绝对值小于 k 的那个最近位置的答案和大于等于当前位置权值且差的绝对值小于 k 的那个最近位置的答案。

可以保证，能够更新当前位置状态的位置一定会先更新这两个最近位置中的 1 个或者 2 个。

因此只需要这两个位置就能够转移出正确答案。

具体实现也是使用权值线段树动态开点 + DP 。

不过权值线段树动态开点是用来求出每个位置满足上方条件的前方坐标的。

只需要用权值线段树维护某个值下的最大坐标即可，访问时就直接查询区间最大值就能找到最近的合法点。

时间复杂度为 \(qn+n\log n\) 。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5;
constexpr i64 MAX = 1e18;

struct Node {
    int l, r, val;
} tr[N * 60];

int root, idx;

void push_up(int u) { tr[u].val = std::max(tr[tr[u].l].val, tr[tr[u].r].val); }

void modify(int &u, i64 L, i64 R, i64 x, int val) {
    if (!u) {
        u = ++idx;
    }
    if (L == R) {
        tr[u].val = val;
        return;
    }

    i64 mid = (L + R) >> 1;
    if (x <= mid) {
        modify(tr[u].l, L, mid, x, val);
    } else {
        modify(tr[u].r, mid + 1, R, x, val);
    }
    push_up(u);
}

int query(int u, i64 L, i64 R, i64 l, i64 r) {
    if (!u) {
        return 0;
    }
    if (l <= L && r >= R) {
        return tr[u].val;
    }

    int res = 0;
    i64 mid = (L + R) >> 1;

    if (l <= mid) res = std::max(res, query(tr[u].l, L, mid, l, r));
    if (r > mid) res = std::max(res, query(tr[u].r, mid + 1, R, l, r));
    return res;
}

void solve() {
    int n;
    std::cin >> n;

    i64 m, k;
    std::cin >> m >> k;

    std::vector<i64> a(n + 1), lo(n + 1), hi(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        lo[i] = query(root, 1, MAX, std::max(a[i] - k, 0LL), a[i]);
        hi[i] = query(root, 1, MAX, a[i], std::min(a[i] + k, MAX));
        modify(root, 1, MAX, a[i], i);
    }

    int q;
    std::cin >> q;

    while (q--) {
        int l, r;
        std::cin >> l >> r;

        int ans = 0;
        std::vector<int> dp(n + 1, 0);

        for (int i = l; i <= r; i++) {
            dp[i] = 1;
            if (lo[i] >= l) {
                dp[i] = std::max(dp[i], dp[lo[i]] + 1);
            }
            if (hi[i] >= l) {
                dp[i] = std::max(dp[i], dp[hi[i]] + 1);
            }
            ans = std::max(ans, dp[i]);
        }

        std::cout << (r - l + 1) - ans << '\n';
    }

    for (int i = 0; i <= idx; i++) {
        tr[i] = {};
    }

    root = idx = 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

蛋糕上的草莓是蛋糕的灵魂

显然不需要切分蛋糕，由于蛋糕是作为分母，切分它不如不动它。

那么草莓作为分子应该变为两者的 LCM ，不过当草莓扩增的倍数是奇数时是非法操作，此时应该接着扩增一倍。

注意原本就能切分的情况。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 x, y;
    std::cin >> x >> y;

    __int128 lcm = (__int128)x * y / std::gcd(x, y);

    if (x % y == 0 || (lcm / x) % 2 == 0) {
        std::cout << y << ' ' << (i64)(lcm / y) << '\n';
        return;
    }

    std::cout << y << ' ' << 2LL * (i64)(lcm / y) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}