Codeforces 1500F - Cupboards Jumps（set）

nb tea！！！111

首先很显然的一件事是对于三个数 \(a,b,c\)，其最大值与最小值的差就是三个数之间两两绝对值的较大值，即 \(\max(|a-b|,|b-c|,|c-a|)\)，因此我们不妨从差分序列的角度解决这个问题。对于原序列 \(h\)，我们假设其差分序列 \(d_i=h_{i+1}-h_i\)，那么 \(\max(h_i,h_{i+1},h_{i+2})-\min(h_i,h_{i+1},h_{i+2})=\max(|h_{i+1}-h_{i}|,|h_{i+2}-h_{i+1}|,|h_{i+2}-h_i|)\)，又 \(h_{i+2}-h_i=d_i+d_{i+1}\)，因此我们可以得到 \(w_i=\max(|d_i|,|d_{i+1}|,|d_i+d_{i+1}|)\)

思考到这里我们就能够想出一个非常 naive 的 DP，\(dp_{i,x}\) 表示考虑到前 \(i\) 个数，\(|d_i|=x\) 是否可行，转移就枚举下一个数 \(d_{i+1}=y\)，那么 \(dp_{i,x}\) 能转移到 \(dp_{i+1,y}\) 的充要条件是 \(x=w_i\lor y=w_i\lor x+y=w_i\) 且 \(x,y\le w_i\)，这样暴力 DP 是 \(\mathcal O(nC^2)\) 的，不知道能拿多少分（大雾）。考虑进行一点点优化，注意到我们 \(dp_{i,x}=1\) 的 \(x\) 肯定是成段分布的对吧，因此我们考虑每一段在转移前后会变成什么，我们假设考虑到 \(i\) 时，满足 \(dp_{i,x}=1\) 的 \(x\) 组成的集合为 \(S\)，那么：

如果 \(w_i\in S\)，那么 \(\forall y\in[0,w_i]\) 均有 \(dp_{i+1,y}=1\)，具体方案就是令 \(d_i=w_i,d_{i+1}=-y\)。
如果到现在还没有判定出无解，也即 \(\exists x\in S,s.t.x<w_i\)（因为 \(>w_i\) 肯定不合法，并且由于该情况不同于上一种情况所以 \(w_i\notin S\)），那么有 \(dp_{i+1,w_i-x}=1\)，具体方案就是 \(d_i=x,d_{i+1}=w_i-x\)，同时也有 \(dp_{i+1,w_i}=1\)，具体方案就是 \(d_i=-x,d_{i+1}=w_i\)。也就是说如果 \(w_i\notin S\)，那么所有点都会变为 \(w_i-x\)，同时加入一个新点 \(w_i\)

因此如果我们维护这些连续段组成的集合，那么每次可以暴力 \(\mathcal O(n)\) 转移每个连续段，因此我们复杂度就降到了 \(\mathcal O(n^2)\)（虽然还是一脸过不去的亚子）

考虑进一步优化，我们注意到这个过程很特别，因为每次如果 \(w_i\notin S\)，那么新增进来的肯定是一个个单点，而区间自始至终都只有一个，也就是说我们可以不考虑一一反转这个单点，而是翻转整个数轴，也就是说我们开一个 set 维护这些单点在最一开始的数轴上的位置，然后维护两个值 \(L,R\) 表示当前区间的两个端点在最一开始的数轴上的位置，然后每次检验现在坐标为 \(w_i\) 的位置在最一开始的数轴上的位置是否属于这个集合与区间的并，如果属于则说明 \(x\in S\)，那么我们就把数轴还原成一开始的样子，把 set 清空并把区间最右端点设为 \(0\) 和 \(w_i\)，否则我们就记录一下区间是否被翻转，即 \(+x\) 方向是否已经变为 \(-x\)，记这个标记为 \(flg\)，以及数轴的偏移量 \(dlt\)，那么我们就设 \(flg:=1-flg,dlt:=w_i-dlt\)，然后把 \(w_i\) 加入集合。如果某一步 \(L\) 在现在数轴上对应的位置 \(>R\) 在现在数轴上对应的位置且 \(S=\varnothing\) 那么无解。

接下来考虑怎样找出合法的方案，我们不妨首先找出任意一个 \(c_i\in S\)，其中 \(S\) 表示扫描到第 \(i\) 步时合法的 \(x\) 组成的集合，那么我们考虑这样构造出 \(|d_i|\)，从最后一个元素开始，我们令 \(|d_{n+1}|=c_{n+1}\)，然后如果 \(|d_{n+1}|=w_n\) 那么我们直接令 \(|d_n|=c_n\) 就好了，否则如果 \(c_n=w_n\) 说明 \(|d_n|\) 设为 \(w_n\) 是合法的选择，我们干脆就令 \(|d_n|=w_n\)，否则我们就只能令 \(|d_{n}|=w_n-|d_{n+1}|\)。然后我们可以根据 \(|d_n|\) 构造出 \(d_n\)，具体方案就是从右往左扫一遍，如果 \(|d_i|+|d_{i+1}|\ne w_i\) 就将 \(d_i\) 变为其相反数。

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

const int MAXN=1e6;

int n;ll C,w[MAXN+5],can[MAXN+5],d[MAXN+5],s[MAXN+5],l,r;

set<ll> st;int flg;ll dlt;

ll gettrs(ll x){return flg?(dlt-x):(dlt+x);}

ll getori(ll x){return flg?(dlt-x):(x-dlt);}

int main(){

	scanf("%d%lld",&n,&C);l=0;r=C;

	for(int i=1;i<=n-2;i++) scanf("%lld",&w[i]);

	for(int i=1;i<=n-2;i++){

		ll L=getori(0),R=getori(w[i]);if(L>R) L^=R^=L^=R;

		chkmax(l,L);chkmin(r,R);

		while(!st.empty()&&(*st.begin())<L) st.erase(st.begin());

		while(!st.empty()&&(*st.rbegin())>R) st.erase(st.find(*st.rbegin()));

		if(l>r&&st.empty()) return puts("NO"),0;

		if(st.find(getori(w[i]))!=st.end()||(l<=getori(w[i])&&getori(w[i])<=r)){

			st.clear();l=0;r=can[i]=w[i];flg=dlt=0;continue;

		} if(l<=r) can[i]=gettrs(l);else can[i]=gettrs(*st.begin());

		flg^=1;dlt=w[i]-dlt;st.insert(getori(w[i]));

	} if(l<=r) d[n-1]=gettrs(l);else d[n-1]=gettrs(*st.begin());

	for(int i=n-2;i;i--){

		if(can[i]==w[i]) d[i]=w[i];

		else if(d[i+1]==w[i]) d[i]=can[i];

		else d[i]=w[i]-d[i+1];

	} ll t=1;

//	for(int i=1;i<=n-1;i++) printf("%lld%c",d[i]," \n"[i==n-1]);

	for(int i=n-2;i;i--){

		if(abs(d[i])+abs(d[i+1])!=w[i]) t=-t;

		d[i]=t*d[i];

	} ll mn=1e18;puts("YES");

	for(int i=1;i<=n;i++) s[i]=s[i-1]+d[i-1],chkmin(mn,s[i]);

	for(int i=1;i<=n;i++) printf("%lld%c",s[i]-mn," \n"[i==n]);

	return 0;

}

巴特西

Codeforces 1500F - Cupboards Jumps（set）

最新文章

热门文章