P8413 「SvR-1」Five of Pentacles 题解

· · 题解

UPD @ 2022-10-05 :修改了一些误导性的内容

赛时的时候在期末复习，就没做。

期末考完来看的时候我的内心 OS 如下：

这不是求个最大不下降子序列就好了吗？这么简单也能评蓝？

然后看到 n,m,k\le 2\times10^6 的时候我凝固了。

好毒瘤一题

以上是我当时不知道 BIT 常数有多小的时候的**言论，大可以忽略。

当然我这个利用在线格式的奇怪做法还是挺有意思的（？

（最终复杂度是与正解差不多的）

正文

我们来看一下题目啊(传送门)

题目要求最小的越过障碍数，那么我们很容能够想到两点：

结合这两点我们希望越过尽可能多的消失的障碍。

而越过的障碍，我们用题目中的 (t_i,x_i) 来表示我们在时间 t_i 越过了障碍 x_i。

不难发现根据 d\ge 0 有 \forall t_i<t_j,x_i\le x_j，于是题目顺利地被转化为求一个最大不下降子序列的。

但是我们就是要走不寻常的路。我们看在线输入的格式。

接下来 k 行，其中第 i 行有两个数字 t_i, p。其中 p 用于生成 x_i，即： x_i = \min(x_{i - 1} + p \oplus (lastans \bmod 15) + 1, m) 其中 lastans 表示上次变化的答案。

特别地，第一次变化之前 lastans = 0， x_0 = 0，且当 x_{i - 1} = m 时，将 x_{i - 1} 视作 0（注意这不会真的改变 x_{i - 1} 的值）。

同时我们有 p\le 15, (lastans \bmod 15) \le15， 从而 p \oplus (lastans \bmod 15) + 1 \le 16。

那么我们会发现我们得到的 \left\{ x_i\right\} 序列是若干个长度不小于 \dfrac{m}{\max\{p\}} 的严格单调增序列拼接而成的，且每一个的结尾都是 m。

利用这个“严格单调增”的性质，我们可以用数组 a[i] 来记录以 i 为开头的最大不下降子序列的后缀最大值（因为 t_i 是按照单调减的顺序给出的）从而只需要在处理完其中某一严格单调增序列 x_i,x_{i+1}\cdots,x_j 时再更新每一个 a[i] 的值，在处理该序列过程中只需要依次更新 a[x_i],a[x_{i+1}]\cdots,a[x_j] 的值，因为前面的值改变并不影响后面的值。

记最大跨过的消失的障碍数为 ans。

按照 t_i 相同为一组来处理。设 t 时的 x 值依次为 x'_1,x'_2\cdots,x'_{tot}。

那么我们发现当 x'_i 的变化出现的时候，包含 x'_i 的最大不下降子序列为 a[x'_i] 所代表的最大不下降序列前接上 x'_1,x'_2\cdots,x'_{i} ，用这个去更新 ans 即可。

处理完之后我们再用下面的 DP 柿子倒序更新 a[x'_1],a[x'_2]\cdots,a[x'_{tot}]:

a[x'_i]=\max\{a[x'_{i}],a[x'_{i+1}]\}+1

然后就做完了。主要的复杂度在更新一整个 a[i] 数组，总复杂度为 O(m\cdot \frac{m}{\frac{m}{\max\{p\}}})=O(m\cdot \max\{p\})

注意一下在线格式的细节就好了，怕 TLE 就用上快读。

代码


#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 2000000
using namespace std;

//快读
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
    r=0;bool w=0; char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
    r=w?-r:r;
}

int a[MAXN+5],tot,stk[MAXN+5],x[MAXN+5],now;
//stk是t时间下的p序列，x是解密以后的x序列

int main() {
    ios::sync_with_stdio(0);
    int n,m,k,t,ans=0,p,lst=0,lstans=0;
    read(n);read(m);read(k);
    read(t);read(p);
    stk[++tot]=p;
    now=t;
    for (int i=1;i<=k;++i) {
        if (i==k) t=p=0;
        else read(t),read(p);
        if (t==now) {
            stk[++tot]=p;
        } else {
            //依次更新并输出答案
            for (int j=1;j<=tot;++j) {
                lst=min(lst+(stk[j]^(lstans%15))+1,m);
                x[j]=lst;
                ans=max(ans,a[lst]+j);
                cout<<n+m-ans-1<<"\n";
                lstans=n+m-ans-1;
            }
            //更新a数组
            ++a[x[tot]];
            for (int j=tot-1;j>=1;--j) a[x[j]]=max(a[x[j+1]],a[x[j]])+1;
            //在处理完后把下一个p放入stk
            stk[tot=1]=p;
            now=t;
            if (lst==m) {
                for (int j=m-1;j>=1;--j) a[j]=max(a[j+1],a[j]);
                lst=0;
            }
        }
    }
    return 0;
}