专栏文章

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

TTyih
P12088题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipo9iaa
此快照首次捕获于
2025/12/03 15:15
3 个月前
此快照最后确认于
2025/12/03 15:15
3 个月前
查看原文

前言

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

Solution

前置知识：差分约束
首先本题限制了区间 ll 到 rr 的第 kk 小的元素为 val\mathrm{val}（val∈{0,1}\mathrm{val} \in \{0,1\}）。 我们可以将其进行分类讨论：
  1. 若 val=0\mathrm{val}=0，则有区间 ll 到 rr 中 00 的个数 ≥k\ge k，即 11 的个数 ≤r−l+1−k\le r-l+1-k。（r−l+1r-l+1 为区间长度。）
  2. 若 val=1\mathrm{val}=1，则有区间 ll 到 rr 中 00 的个数 <k<k，即 11 的个数 >r−l+1−k> r-l+1-k，可以推出 11 的个数 ≥r−l+1−k+1\ge r-l+1-k+1。
我们可以设一个 SumiSum_i 表示前 ii 个数的前缀和。则 Sumr−Suml−1Sum_r-Sum_{l-1} 可以表示为区间 ll 到 rr 中 11 的个数。
我们就可以将上述的讨论进行转化：
{Sumr−Suml−1≤r−l+1−k, val=0Sumr−Suml−1≤−(r−l+1−k+1),val=1\begin{cases} Sum_r-Sum_{l-1} \le r-l+1-k,\quad\quad\quad\quad \ \mathrm{val}=0 \\ Sum_r-Sum_{l-1} \le -(r-l+1-k+1),\quad\mathrm{val}=1 \end{cases}
因为 SumiSum_i 表示的是前缀和且数只有 00 或 11，所以同时还要满足以下条件：
∀i∈[1,n],都有{Sumi−Sumi−1≤1Sumi−1−Sumi≤0\forall i \in [1,n],\text{都有} \begin{cases} Sum_i-Sum_{i-1} \le 1\\ Sum_{i-1}-Sum_{i} \le0 \end{cases}
之后就可以愉快的使用差分约束 AC 本题了。
注：这里的差分约束要用 Bellman-Ford，若使用 SPFA 你将会 TLE 的很惨。

Code

CPP
#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，它又活了。
你可以使用一些玄学优化来通过本题，就像这样：
CPP
	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]<<" ";
不过不建议在考试时使用。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...