CF1500F Cupboards Jumps 题解

题目链接

点击打开链接

题目解法

感觉是一个融合了许多技巧的题，很巧妙

题目要求 \(\max(h_i,h_{i+1},h_{i+2})-\min(h_i,h_{i+1},h_{i+2})=w_i\)，这可以转化成另一个只和两项有关的形式为：\(\max(|h_i-h_{i+1}|,|h_i-h_{i+2}|,|h_{i+1}-h_{i+2}|)=w_i\)
令 \(d_i=h_{i+1}-h_i\)，所以限制为 \(\max(|d_i|,|d_{i+1}|,|d_i+d_{i+1}|)=w_i\)
这是这道题的第一个巧妙之处：转成差分序列

考虑一个朴素的 \(dp\) 做法，令 \(f_{i,j}\) 为 \(|d_i|=j\)，且满足前 \(i-1\) 个限制是否可行（注意，这里是 \(|b_i|\)）
转移比较简单：

1. \(f_{i,j}\to f_{i+1,w_i}(0\le j\le w_i)\)
2. \(f_{i,w_i}\to f_{i+1,j}(0\le j\le w_i)\)
3. \(f_{i,j}\to f_{i+1,w_i-j}(0\le j\le w_i)\)

为什么前 2 种情况不需要考虑 \(|d_i+d_{i+1}|\) 会不会 \(>w_i\)，因为 \(d_i\le w_i,\;d_{i+1}\le w_i\)，那么一定可以通过后面的调整符号从而使 \(d_i+d_{i+1}\le w_i\)

接下来是这道题的第二个巧妙之处：在 1 的形态上进行考虑
考虑 \(f\) 值为 1 的连续段的变化，可以发现，2 操作会使所有区间合并成 \([0,w_i]\)，操作 1 会增加一个单点，操作 3 只是按照 \(\frac{w_i}{2}\) 翻转，不会改变单点和区间个数
所以，可以得到一个局面下，1 的连续段为至多一个区间和 \(O(n)\) 个单点

考虑维护区间和单点的变化
操作 1 和 2 是好维护的
操作 3 需要按照 \(\frac{w_i}{2}\) 翻转，手玩一下发现一个神奇的结论是：按照 \(\frac{w_i}{2}\) 翻转 等价于 按照 \(0\) 翻转，然后再往右平移 \(w_i\)，这里是第三个巧妙之处
这样就好维护了，只需要记录当前是正的还是反的，以及平移的距离
这样可判断 YES OR NO

考虑构造方案
可以得到一个贪心的想法是，\(d_{n-1}\) 随便一个 1 位置，从后往前构造 \(d_i\)
如果 \(d_{i+1}=w_i\)，则 \(d_i\) 为随便一个可行的位置，如果 \(d_i\) 可以为 \(w_i\)，则 \(d_i=w_i\)，否则 \(d_i=w_i-d_{i+1}\)
但这样只确定了 \(|d_i|\)，我们需要定正负性，这个从后往前，如果我们不需要 \(|d_i+d_{i+1}|=w_i\)，那么就使 \(d_i\) 和 \(d_{i+1}\) 异号

时间复杂度 \(O(n\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=1000100;
const LL inf=1e18;
int n;
LL C,w[N],d[N],ps[N],ans[N];
set<LL> single;
int main(){
    read(n),read(C);
    F(i,1,n-2) read(w[i]);
    //按w_i/2翻转 等价于  按原点翻转，在往右平移a_i
    LL l=0,r=C,tag2=0;//翻转之后需要平移的距离
    bool tag1=0;//是否需要以原点为中心翻转
    F(i,1,n-2){
        LL le,ri,ed;
        if(tag1) le=-w[i]+tag2,ri=tag2,ed=-w[i]+tag2;
        else le=-tag2,ri=w[i]-tag2,ed=w[i]-tag2;
        chkmax(l,le),chkmin(r,ri);
        while(!single.empty()&&(*single.begin())<le) single.erase(*single.begin());
        while(!single.empty()&&(*single.rbegin())>ri) single.erase(*single.rbegin());
        if(l>r&&single.empty()){ puts("NO");exit(0);}
        if((l<=ed&&ed<=r)||single.find(ed)!=single.end()){//f[i-1][w_i]=1
            single.clear(),tag1=0,tag2=0;
            l=0,r=w[i],ps[i]=w[i];continue;
        }
        //find one possible sol
        if(l<=r){
            if(tag1) ps[i]=-l+tag2;
            else ps[i]=l+tag2;
        }
        else{
            if(tag1) ps[i]=-(*single.begin())+tag2;
            else ps[i]=(*single.begin())+tag2;
        }
        tag1^=1,tag2=w[i]-tag2;
        if(tag1) single.insert(tag2-w[i]);
        else single.insert(w[i]-tag2);
    }
    puts("YES");
    if(l<=r) d[n-1]=tag1*(-1)*l+tag2;
    else d[n-1]=tag1*(-1)*(*single.begin())+tag2;
    // F(i,1,n-2) cout<<ps[i]<<' ';cout<<'\n';
    DF(i,n-2,1){
        if(w[i]==d[i+1]) d[i]=ps[i];
        else if(w[i]==ps[i]) d[i]=w[i];
        else d[i]=w[i]-d[i+1];
    }
    // F(i,1,n-1) cout<<d[i]<<' ';cout<<'\n';
    int neg=1;
    DF(i,n-2,1){
        if(abs(d[i])+abs(d[i+1])!=w[i]) neg*=-1;
        d[i]*=neg;
    }
    // F(i,1,n-1) cout<<d[i]<<' ';cout<<'\n';
    // F(i,1,n-2) assert(max(abs(d[i]),max(abs(d[i+1]),abs(d[i]+d[i+1])))==w[i]);
    ans[1]=0;
    F(i,1,n-1) ans[i+1]=ans[i]+d[i];
    LL mn=inf;
    F(i,1,n) chkmin(mn,ans[i]);
    F(i,1,n) ans[i]-=mn;
    F(i,1,n) printf("%lld ",ans[i]);puts("");
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}