【2025广东省队集训day7】序列变换 做题记录

给定一个长 $n$ 的整数序列 $a$，可以进行若干次操作：

• 选择一个区间 $[l,r]$，对于所有 $x\in \{0,1\}$ 和 $i\in \mathbb N$ 满足 $l+3i+x\le r$，将 $a_{l+3i+x}$ 加上 $(-1)^x$；

求最小的操作次数使得 $\forall 1\le i\le n,a_i=0$ 或报告无解。

多测，$1\le \sum n\le 2\times 10^7$，$|a_i|\le 10^{10}$。

设 $b_i=a_{i-2}+a_{i-1}+a_{i}$，其下标范围为 $[1,n+2]$，默认 $i$ 超出 $[1,n]$ 的 $a_i$ 均为 $0$。不难发现目标等价于让 $b$ 变成全 $0$。

那么对于一次形如 $+1,-1,0,+1,-1,0,\dots,+1,-1,0$ 的操作，即 $l\equiv r+1\pmod 3$ 时，操作相当于：

• $b_l\to b_l+1$；
• $b_{r+1}\to b_{r+1}-1$；

注意这里操作的 $l$ 取值范围是 $[1,n]$，$r$ 的范围是 $[1,n+1]$，所以这样的操作相当于选择一对满足 $x\equiv y\pmod 3$ 且 $x<y$ 的 $x,y$ 并将 $b_x$ 增加 $1$，$b_y$ 减少 $1$。不妨称其为操作一。

而对于一次形如 $+1,-1,0,+1,-1,0,\dots,+1$ 的操作，即 $l\equiv r\pmod 3$，操作相当于：

• $b_l\to b_l+1$；
• $b_{r+1}\to b_{r+1}+1$；
• $b_{r+2}\to b_{r+2}+1$；

这个操作相当于选择三个 $\text{ mod }3$ 不同且后两个相邻的位置 $x,y,y+1$，将对应的 $b$ 都增加 $1$。不妨称其为操作二。

不难发现操作二进行的次数是固定的。

考虑只有操作二怎么做，不妨从后往前贪心。假设 $b_{[i+1,n+2]}$ 已经变成全 $0$，那么对于相邻的两个位置 $b_{i-1},b_i$：

• 若 $b_i=0$ 则不管；
• 若 $b_i>0$ 则无解；
• 若 $b_i<0$，那么需要在这里进行操作。考虑先让这两个位置一起 $+1$，但是注意到第三个位置只能确定 $\text{ mod }3$ 的值。故需要开一个 $cnt_{[0,2]}$ 记录每种余数的操作有几个。如果发现 $b_i<0$ 但 $b_{i-1}=0$ 再用掉 $cnt$ 里的操作。不难发现这样一定是最优的；

考虑只有操作一怎么做，有无解考虑将 $b$ 按照下标 $\text{ mod }3$ 的值分成三个序列后相当于要求每个序列的后缀和都要 $\le 0$，而最优方案可以随便构造，操作次数是 $\frac{\sum |b_i|}{2}$。

那么现在两种操作都有，依旧是考虑从后往前贪心。假设 $b_{[i+1,n+2]}$ 已经变成全 $0$，那么对于 $b_i$：

• $b_i=0$ 则跳过这个位置；
• $b_i>0$ 则在这里进行操作一，另一个位置依旧暂时无法确定，需要开一个 $c1_{[0,2]}$ 记录每种余数的操作一有几个；
• $b_i<0$ 则看 $b_{i-1}$ 的情况：
  • 先贪心用操作二将这两个位置一起抬升，直到操作二次数用尽或者 $b_{i-1}\ge 0$；
  • 然后将之前记录的操作用在这里（$c1$ 或者 $cnt$ 中的，其实这两种操作在这里是等价的，只需要 $cnt$）；
  • 还不行就只能在 $b_{i-1}$ 处使用操作一挖坑，挖到 $b_{i-1}=b_i$ 再用操作二一起抬升回去。如果此时操作二不够则无解；

不难发现每一步都是最优的，那就做完了，时间复杂度 $O(n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=30005;

int n;
ll a[S],b[S];

inline void slove()
{
	for(int i=1;i<=n;i++) cin>>a[i];
	a[n+1]=a[n+2]=0;
	for(int i=1;i<=n+2;i++)
		b[i]=(i-2<=0?0:a[i-2])+(i-1<=0?0:a[i-1])+a[i];
	// for(int i=1;i<=n+2;i++) cout<<b[i]<<' ';
	// cout<<'\n';
	ll sm2=0;
	for(int i=1;i<=n+2;i++) sm2+=(-b[i]);
	sm2/=3;
	if(sm2<0) return cout<<"-1\n",void();
	ll c[3]={0,0,0};
	ll ans=sm2;
	for(int i=n+2;i>=1;i--)
	{
		if(b[i]==0) continue;
		if(b[i]>0) ans+=b[i],c[i%3]+=b[i];
		else
		{
			// two
			if(i>1)
			{
				ll de=max(0ll,min(min(-b[i],-b[i-1]),sm2));
				sm2-=de;
				b[i-1]+=de;
				b[i]+=de;
				c[(i-2)%3]+=de;
			}
			// pre
			ll de=min(-b[i],c[i%3]);
			b[i]+=de;
			c[i%3]-=de;
			// dig
			if(b[i]<0)
			{
				if(i==1||(-b[i])>sm2) return cout<<"-1\n",void();
				// down
				ll ned=b[i-1]+b[i];
				ans+=ned;
				b[i-1]-=ned;
				c[(i-1)%3]+=ned;
				// up
				ll de=-b[i];
				sm2-=de;
				b[i-1]+=de;
				b[i]+=de;
				c[(i-2)%3]+=de;
			}
		}
	}
	cout<<ans<<'\n';
}

int main()
{
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T>>n;
	while(T-->0) slove();
	return 0;
}