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

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

发表评论

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

你是机器人吗? =。= *