专栏文章

CF1474D Cleaning 题解

llinjunye
CF1474D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio0c1m9
此快照首次捕获于
2025/12/02 11:17
3 个月前
此快照最后确认于
2025/12/02 11:17
3 个月前
查看原文
应该是简单一点的做法。
我们先假设一次操作是选择 ii 和 i+1i+1 并进行减一。
我们定义第 ii 个数的操作次数为选择 ii 和 i+1i+1 进行减一，注意不包含选择 i−1i-1 和 ii 的。
那么，我们发现，第一个数的操作次数为 a1a_1，第二个就是 a2−a1a_2-a_1，第三个则是 a1−a2+a3a_1-a_2+a_3，以此类推。
我们定义 sis_i 为这个式子，那么我们要满足 si≥0s_i\ge 0 才行。
这样不太优雅，我们可以将是偶数的 ii 的 sis_i 取反，这样就有了一个统一的格式：si=a1+a3+a5+⋯−a2−a4−⋯s_i=a_1+a_3+a_5+\cdots-a_2-a_4-\cdots。
那么，我们的限制要改变一下：对于 ii 是奇数，si≥0s_i\ge 0；对于 ii 是偶数，si≤0s_i\le 0。
注意有一种情况，就是第 nn 堆还没有取完。这个时候我们可以新建一个堆 n+1n+1，里面放有 00 个石子，就可以解决了。
这样你就会 O(n)O(n) 的判断了。
接下来看一次交换会改变什么。
注意，下面默认 nn 为新建完一堆石子后的堆数（即 nn 你可以理解成 n+1n+1）。
假设我们交换 ii 和 i+1i+1。
那么 sis_i 会变成 si−1+ai+1s_{i-1}+a_{i+1} 或者 si−1−ai+1s_{i-1}-a_{i+1}，这个具体看 ii 的奇偶性。
然后对于 i<j≤ni<j\le n，我们有变化量：当 ii 是奇数时，变化量为 2×ai+1−2×ai2\times a_{i+1}-2\times a_i；当 ii 是偶数时，变化量为 2×ai−2×ai+12\times a_{i}-2\times a_{i+1}。
我们可以预处理出 LjL_j 和 RjR_j，分别表示能让 sis_i 符合要求，最小能加的数和最大能加的数。
这个不难 O(n)O(n) 预处理。
我们发现，对于变化量 dd，我们是不是只需要 Lj≤d≤RjL_j\le d\le R_j 就可以了？
不难发现限制其实就是：max⁡j=i+1nLj≤d≤min⁡j=i+1nRj\max_{j=i+1}^{n}L_j\le d\le \min_{j=i+1}^{n}R_j。
这启发我们倒着做，后缀最值是不难做的。
然后有一个细节特判一下：如果存在一个 jj，满足 j<ij<i 并且 sjs_j 不符合要求，我们的交换是无意义的（因为还是不合法情况）。
这样，我们就做完了，代码量适中，细节有点多。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1000010;
const int INF=0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int s[N];
int l[N],r[N];
int flag[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	n++;//新增一堆
	a[n]=0;
	for(int i=1;i<=n;i++){
		s[i]=s[i-1];
		if(i%2==1)s[i]+=a[i];
		else s[i]-=a[i];
	}
	bool fl=1;
	for(int i=1;i<=n;i++){
		if(i%2==1)fl&=(s[i]>=0);
		else fl&=(s[i]<=0);
		if(i%2==1&&s[i]<0||i%2==0&&s[i]>0)flag[i]=0;//不合法
		else flag[i]=1;//合法
	}
	for(int i=1;i<=n;i++)flag[i]+=flag[i-1];//合法的数量
	if(fl){//都合法（也可以 if(flag[n]==n)）
		cout<<"YES\n";
		return;
	}
	for(int i=1;i<=n;i++){//INF 指无限大，-INF 指无限小
		if(i%2==1){
			if(s[i]<0)l[i]=-s[i],r[i]=INF;
			else l[i]=-s[i],r[i]=INF;
		}
		else{
			if(s[i]>0)l[i]=-INF,r[i]=-s[i];
			else l[i]=-INF,r[i]=-s[i];
		}
	}
	int L=max(l[n-1],l[n]),R=min(r[n-1],r[n]);
	for(int i=n-2;i>=1;i--){
		int val=s[i-1];
		if(i%2==0)val-=a[i+1];
		else val+=a[i+1];
		if(i%2==1&&val<0||i%2==0&&val>0){//这里就不合法
			R=min(R,r[i]);
			L=max(L,l[i]);
			continue;
		}
		if(L>R)break;//不可能存在L<=d<=R
		if(flag[i-1]!=i-1){
			R=min(R,r[i]);
			L=max(L,l[i]);
			continue;
		}
		int delta;
		if(i%2==0)delta=2*a[i]-2*a[i+1];
		else delta=2*a[i+1]-2*a[i];
		// cerr<<i<<"\n";
		// cerr<<L<<" "<<R<<"\n";
		// cout<<delta<<"\n";
		if(L<=delta&&delta<=R){//合法
			cout<<"YES\n";
			return;
		}
		R=min(R,r[i]);
		L=max(L,l[i]);
	}
	cout<<"NO\n";
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int Tc=1;
	cin>>Tc;
	while(Tc--)solve();
	return 0;
}
/*
a[1]>=0
a[1]-a[2]<=0
a[1]+a[3]-a[2]>=0
a[1]+a[3]-a[2]-a[4]<=0
a[1]+a[3]+a[5]-a[2]-a[4]<=0

相邻？
a[1]>=0
a[1]-a[3]<=0
a[1]+a[2]-a[3]>=0
a[1]+a[2]-a[3]-a[4]<=0
a[1]+a[2]+a[5]-a[3]-a[4]<=0

delta?
对于>i的下标
i%2==0:
delta=-(a[i+1]-a[i])+(a[i]-a[i+1])=-a[i+1]+a[i]+a[i]-a[i+1]=2a[i]-2a[i+1]
i%2==1:
delta=-(a[i]-a[i+1])+(a[i+1]-a[i])=-a[i]+a[i+1]+a[i+1]-a[i]=2a[i+1]-2a[i]

*/

评论

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

正在加载评论...