(真的是动态动态规划,我没有口吃!!!)

1. 题目

传送门= ̄ω ̄=

(当然 BZOJ 传题真是十分不负责任的,可以去看洛谷传送门= ̄ω ̄=

2. 题解

题面看了半天才看懂。。。真不知道写题面的大爷语文谁教的。。。

大概就是给你一个长度为 $n$的环,你任选环上一点作为起点,每次可以顺时针走一步,或者是呆在原地不动,每次花费 1 个单位时间。环上每个点都有一个权值 $T _ i$,如果你当前所在的点的权值小于等于你的当前所用时间,那么当前这个点就会被标记。要求最小化标记所有点的时间。

emmmm… 根据 benoble_大佬的启示,我们可以把题目转换成如下形式:

首先选定一个最终时间 $t$,每个物品会在 $T _ i$的时刻消失,你可以任选一个起点,每个单位时间可以逆时针走一步或者是呆着不动,要求访问到所有物品(消失了的物品无法访问),最小化这个 $t$

好的我们能二分答案了(逃

其实就是把问题反过来了

题目转化成这个形式以后显然就很棒棒了,因为这种情况下显然你会一直逆时针移动(停在原地不动一定不会更优)。

所以反过来,你在原问题里也肯定是选定某个起点,然后一直顺时针移动而不会停下(因为每个逆过来走的方案都有一个对应的顺着走的方案)

然后对于一直走转两圈,不如选择某一个起点等,然后等完了直接转一圈(也就是通过等待使得每个点的出现时间都大于等于到达该点时间)

这样就比较好办了。

设起点为 $s$,然后拆环为链(复制两遍,链的长度为 $2n$)‘

这样有以下式子:

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, s + n – 1]} [T _ i – (i – s)] \} + n – 1$$

其中 $i – s$表示从 $s$出发到达 $i$所用的时间,$T _ i – (i – s)$自然就是该点需要你在 $s$点至少等待的时间,取 $max$就是从 $s$出发需要等待的时间。

最后一个 $n – 1$表示转一圈所需要的时间。

为了简化式子我们设 $A _ i = T _ i – i$

则式子可以转化为:

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, s + n – 1]} (A _ i) + s \} + n – 1$$

然后因为 $A _ i = T _ i – i$,所以 $A _ i > A _ {i + n}$,所以可以放宽 $i$取值的范围:

$$Ans = min _ {s \in [1,n]} \{ max _ {i \in [s, 2n]} (A _ i) + s \} + n – 1$$

设满足 $A _ x \ge A _ i(x < i)$的最大的 $x$为 $pre _ i$

对于某个 $A _ i$,如果对于任意的 $j \in [i + 1, 2n]$,都有 $A _ i > A _ j$(也就是 $A _ i$为后缀最大值),那么区间 $[pre _ i + 1, i]$这个区间内最小的 $max _ {i \in [s, s + n – 1]} (A _ i) + s$就等于 $A _ i + i$

那么就用线段树维护序列 $A$,对于一个区间 $[l, r]$,我们维护其最大值 $mx$,再维护一个 $min _ {s \in [l, mid]} \{ max _ i \in [s, r](A _ i) + s \}$(其中 $mid=\frac {l + r} 2$)

第一个 $mx$很好维护,第二个东西怎么维护呢?

其实这里的思想有点类似于单调栈,我们等于用线段树维护了一个单调递减的单调栈,我们要做的是合并当前区间的左右子区间的单调栈。

那就用右子区间的队首元素 $A _ x$(也就是最大元素),到左子区间里查找到大于等于 $A _ x$且最靠右(下标最大,最靠近 $x$的)的元素 $A _ y$,那么 $s \in [y, mid]$的时候,后缀最大值就是 $A _ x$,能取到的最小答案就是 $A _ x + s$。

然后对于 $A _ y$左边的那些 $s \in [1, y – 1]$,则可以在查找 $A _ y$的时候由查找时所在的区间的左子区间的答案取 $min$得到。

这一段比较复杂,可以看下这段代码:

struct N {int l, r, mx, d;} e[NS << 2];

int cal(int mx, int a) // mx 是用来查找的 Ax,a 是当前节点
{
    //如果已经确定了 y,这里取 max(e[a].mx, mx) 是防止 Ay 不存在
    if (e[a].l == e[a].r) return e[a].l + max(e[a].mx, mx);
    //如果右子区间的最大值是大于 Ax,那么 Ay 在右子区间,然后顺手获取一波 Ay 左边的答案
    if (e[RS(a)].mx >= mx) return min(e[a].d, cal(mx, RS(a)));
    //否则 Ay 在左子区间,这里取 min 是因为左子区间可能没有数字比 Ax 小了
    return min(cal(mx, LS(a)), e[RS(a)].l + mx);
}

emmmmm… 好吧就讲到这里。。。赶紧放代码跑路啦 23333~

#include <bits/stdc++.h>

#define NS (200005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {int l, r, mx, d;} e[NS << 2];

int n, m, p, N, arr[NS];

int cal(int mx, int a)
{
    if (e[a].l == e[a].r) return e[a].l + max(e[a].mx, mx);
    if (e[RS(a)].mx >= mx) return min(e[a].d, cal(mx, RS(a)));
    return min(cal(mx, LS(a)), e[RS(a)].l + mx);
}

void pup(int a)
{
    e[a].mx = max(e[LS(a)].mx, e[RS(a)].mx);
    e[a].d = cal(e[RS(a)].mx, LS(a));
}

void Build(int l, int r, int a)
{
    e[a].l = l, e[a].r = r;
    if (l == r)
    {
        e[a].mx = arr[l], e[a].d = arr[l] + l;
        return;
    }
    int mid = ((l + r) >> 1);
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Update(int x)
{
    int a = 1;
    while (e[a].l < e[a].r)
        if (e[LS(a)].r >= x) a = LS(a);
        else a = RS(a);
    e[a].mx = arr[x], e[a].d = arr[x] + x;
    while (a >>= 1, a) pup(a);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(p), N = (n << 1);
    for (int i = 1; i <= n; i += 1) IN(arr[i]), arr[i + n] = arr[i];
    for (int i = 1; i <= N; i += 1) arr[i] -= i;
    Build(1, N, 1); int lst = e[1].d + n - 1, x, y; printf("%d\n", lst);
    while (m--)
    {
        IN(x), IN(y);
        if (p) x ^= lst, y ^= lst;
        arr[x] = y - x, arr[x + n] = y - x - n;
        Update(x), Update(x + n), printf("%d\n", lst = e[1].d + n - 1);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

Qiuly · 2019年3月20日 3:52 下午

QwQ 您貌似有个柿子推错了:

这里貌似是 $+s$ ……

    Remmina · 2019年3月20日 5:23 下午

    虽然已经完全不记得题目了,但是还是修复了

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注