题解：P12088 [RMI 2019] 还原 / Restore Arrays

Tyih · 2025-04-09 13:20:25 · 题解

前言

关于 SPFA，它死了。

如果你写的是正常的 SPFA，那么恭喜你，会喜提 20 分的高分以及获得 TLE 三到四个点。

Solution

前置知识：差分约束

首先本题限制了区间 l 到 r 的第 k 小的元素为 \mathrm{val}（\mathrm{val} \in \{0,1\}）。 我们可以将其进行分类讨论：

1. 若 \mathrm{val}=0，则有区间 l 到 r 中 0 的个数 \ge k，即 1 的个数 \le r-l+1-k。（r-l+1 为区间长度。）
2. 若 \mathrm{val}=1，则有区间 l 到 r 中 0 的个数 <k，即 1 的个数 > r-l+1-k，可以推出 1 的个数 \ge r-l+1-k+1。

我们可以设一个 Sum_i 表示前 i 个数的前缀和。则 Sum_r-Sum_{l-1} 可以表示为区间 l 到 r 中 1 的个数。

我们就可以将上述的讨论进行转化：

因为 Sum_i 表示的是前缀和且数只有 0 或 1，所以同时还要满足以下条件：

之后就可以愉快的使用差分约束 AC 本题了。

注：这里的差分约束要用 Bellman-Ford，若使用 SPFA 你将会 TLE 的很惨。

Code

#include <bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define ll long long
#define db double
#define pb push_back
using namespace std;
const int N=5e3+5;
ll n,m,s[N],cnt[N];
vector<array<int,3>> to;
int main(){
    IOS;cin>>n>>m;
    memset(s,0x7f,sizeof s);
    for(int i=1;i<=n;i++){
        to.pb({i-1,i,1});
        to.pb({i,i-1,0});
    }  
    for(int i=1,l,r,k,v;i<=m;i++){
        cin>>l>>r>>k>>v;
        l++;r++;//在这里将其转化为下标从一开始 
        if(v) to.pb({r,l-1,-(r-l+1-k+1)});
        else to.pb({l-1,r,r-l+1-k});
    }
    s[0]=0;
    bool flag=0;
    for(int i=1;i<=n;i++){//Bellman-Ford
        flag=0;
        for(auto e:to){
            int u=e[0],v=e[1],w=e[2];
            if(s[v]>s[u]+w){
                flag=1;
                s[v]=s[u]+w;
            }
        }
        if(!flag) break;
    }
    if(flag){
        cout<<"-1\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<s[i]-s[i-1]<<" ";
    }
    return 0;
}

后记

关于 SPFA，它又活了。

你可以使用一些玄学优化来通过本题，就像这样：

    memset(s,0x7f,sizeof s);
    queue<int> q;
    q.push(0);
    vis[0]=1;s[0]=0;
    int tt=0;
    while(!q.empty()){//SPFA
        int u=q.front();q.pop();
        vis[u]=0;
        for(PLL tp:to[u]){
            int v=tp.first,w=tp.second;
            tt++;
            if(tt>2e7){//玄学优化
                cout<<-1<<"\n";
                return 0;
            }
            if(s[u]+w<s[v]){
                s[v]=s[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n){
                    cout<<"-1\n";
                    return 0;
                }
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
  for(int i=1;i<=n;i++) cout<<s[i]-s[i-1]<<" ";

不过不建议在考试时使用。