题解 - Cupboards Jumps

Macesuted QWQ LV 8 SU @ 2022-3-13 16:37:38

题意

给出长度为 $n - 2$ 的数组 $w_i$ ，请你构造一个长度为 $n$ 的数组 $a$ 满足 $\forall i \in [1,~n - 2],~\max(a_i,~a_{i + 1},~a_{i + 2}) - \min(a_i,~a_{i + 1},~a_{i + 2}) = w_i$。若不能构造输出 NO。

$n \le 10^6,~0 \le w_i \le 10^{12},~0 \le a_i \le 10^{18}$

分析

考虑令 $c_i = a_{i + 1} - a_i$ ，则 $w_i = \max(|c_i|,~|c_{i + 1}|,~|c_i + c_{i + 1}|)$ 。

在确定 $c_i$ 考虑 $w_i$ 对 $c_{i + 1}$ 的限制时我们发现，我们可以通过将 $a_1 \sim a_{i + 1}$ 全部乘上 $-1$ 以使得 $c_1 \sim c_i$ 全都乘上 $-1$ ，容易发现这并不会影响 $w_1 \sim w_{i - 1}$ 带来的所有限制。因此我们发现我们在研究该限制时并不关心 $c_i$ 的符号，我们令 $d_i = |c_i|$ ，则 $w_i = \max(d_i,~d_{i + 1},~d_i + d_{i + 1})$ 。

考虑对该限制分别考虑最大值在哪一项上取到。设状态 $f_{i,~j}$ 表示考虑了 $d_1 \sim d_i$ ，且 $d_i = j$ 的方案是否合法。则对于所有合法情况 $f_{i,~j}$ ，有：

若 $j = w_i$ ，则 $\forall k \in [0,~w_i],~f_{i + 1,~k} = \text{True}$ 。
若 $0 < j \le w_i$ ，则 $f_{i + 1,~w_i} = \text{True}$ 。
若 $0 < j \le w_i$ ， $f_{i + 1,~w_i - j} = \text{True}$ 。

仔细观察，我们发现若 $f_{i,~w_i} = \text{True}$ ， $f_{i + 1}$ 数组中全部能取到的部分都为 $\text{True}$ ，不需要考虑其他两个情况；若 $f_{i}$ 数组中存在一项为 $\text{True}$ 那么 $f_{i + 1,~w_i}$ 为 $\text{True}$ 。这两种情况均可快速判断，而情况 3 则需要将所有合法状态 $j$ 转换为 $w_i - j$ 。

考虑维护 $f_i$ 数组中连续的 $\text{True}$ 段，则对于一个段 $[l,~r]$ ，其转移后为 $[w_i - r,~w_i - l]$ 。容易发现其由一个翻转操作和一个平移操作构成。因此每次从 $i$ 转移到 $i + 1$ 时，只需判断情况 1 和 2，然后再全局修改连续段的翻转和平移情况即可。若在转移到 $n - 1$ 前连续段集合为空，则无解，否则有解。

考虑如何构造 $d$ 数组。我们可以在最终的连续段集合中任取一个点的值作为 $d_{n - 1}$ ，考虑从后往前构造出整个 $d$ 数组，发现只有三种情况：

若 $d_i$ 可以等于 $w_i$ ，则令 $d_i = w_i$ 。因为若 $d_i = w_i$ ，则 $d_{i + 1}$ 可以取任意可以取到的值，所以这么做并不会影响正确性。
若 $d_{i + 1} = w_i$ ，则令 $d_i$ 为任意可以取到的小于 $w_i$ 的值。
若不满足上面的两个条件，则令 $d_i = w_i - d_{i + 1}$ 。

需要注意的是这里需要用到“任意可以取到的小于 $w_i$ 的值”，这需要实现中在转移 $f$ 时提前记录该项和 $d_i$ 能否取到 $w_i$ 值。

构造完 $d$ 数组后，考虑如何构造 $c$ 。这则相对简单，判断 $d_i + d_{i + 1}$ 是否等于 $w_i$ 。若不等于，则 $c_i$ 与 $c_{i + 1}$ 需异号，否则需同号。

最后根据 $c$ 数组随意构造出满足每个元素均为非负整数的 $a$ 数组即可。

代码

View On GitHub

Code

/**
 * @file 1500F.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-03-03
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf1500f
 *
 */

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

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    string s = "";
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
T read() {
    T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
void write(const T& t) {
    T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

bool mem1;

#define maxn 1000005

typedef pair<long long, long long> pll;

long long a[maxn], d[maxn], w[maxn], v[maxn], limd[maxn];
set<pll> S;

void solve(void) {
    int n = read<int>();
    long long C = read<long long>();
    for (int i = 1; i < n; i++) limd[i] = numeric_limits<long long>::max();
    for (int i = 1; i <= n - 2; i++)
        w[i] = read<long long>(), limd[i] = min(limd[i], w[i]), limd[i + 1] = min(limd[i + 1], w[i]);
    S.emplace(0, limd[1]);
    long long A = +1, B = 0;
    for (int i = 1; i <= n - 1; i++) {
        if (A == +1) {
            while (!S.empty() && S.rbegin()->first + B > limd[i]) S.erase(--S.end());
            if (!S.empty() && S.rbegin()->second + B > limd[i]) {
                int l = S.rbegin()->first;
                S.erase(--S.end()), S.emplace(l, limd[i] - B);
            }
        } else {
            while (!S.empty() && -S.begin()->second + B > limd[i]) S.erase(S.begin());
            if (!S.empty() && -S.begin()->second + B > limd[i]) {
                int r = S.begin()->second;
                S.erase(S.begin()), S.emplace(B - limd[i], r);
            }
        }
        long long tw = (w[i] - B) / A;
        auto p = S.lower_bound({tw + 1, tw + 1});
        if (p != S.begin() && (--p)->second >= tw) {
            v[i] = w[i];
            S.clear(), S.emplace(0, limd[i + 1]), A = +1, B = 0;
            continue;
        }
        if (S.empty()) return putstr("NO\n");
        v[i] = S.begin()->first * A + B;
        if (i == n - 1) break;
        A = -A, B = w[i] - B;
        tw = (w[i] - B) / A;
        p = S.lower_bound({tw + 1, tw + 1});
        if (p == S.begin() || (--p)->second < tw) S.emplace(tw, tw);
    }
    d[n - 1] = v[n - 1];
    putstr("YES\n");
    for (int i = n - 2; i; i--)
        if (v[i] == w[i])
            d[i] = w[i];
        else if (d[i + 1] == w[i])
            d[i] = v[i];
        else
            d[i] = abs(w[i] - d[i + 1]);
    long long minVal = 0, pre = 0;
    for (int i = 2, id = +1; i <= n - 1; i++) {
        if (abs(d[i - 1]) + abs(d[i]) != w[i - 1]) id = -id;
        d[i] *= id;
        minVal = min(minVal, pre += d[i]);
    }
    a[1] = -minVal;
    for (int i = 2; i <= n; i++) a[i] = a[i - 1] + d[i - 1];
    for (int i = 1; i <= n; i++) write(a[i]), putch(" \n"[i == n]);
    return;
}

bool mem2;

int main() {
#ifdef MACESUTED
    cerr << "Memory: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time: " << clock() * 1000. / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}

ID

253

时间

6000ms

内存

512MiB

难度

标签

dp
*3500

递交数

已通过

上传者

Hydro

1 条题解

题意

分析

代码

Cupboards Jumps

信息

状态

开发

支持

1 条题解

题意

分析

代码

Cupboards Jumps

信息

状态

开发

支持

还没有账户？

登录