专栏文章

题解：CF2053I1 Affectionate Arrays (Easy Version)

IIvanZhang2009
CF2053I1题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqmi6e9
此快照首次捕获于
2025/12/04 07:13
3 个月前
此快照最后确认于
2025/12/04 07:13
3 个月前
查看原文
注意到 max⁡(∣ai∣)≤∑ai\max(|a_i|)\le \sum a_i 的限制。经过合理猜测可以发现 bb 最大子段和最小就是 ∑ai\sum a_i，取整个序列即可得到。考虑一个深刻的充要条件：设 s=∑ais=\sum a_i，则 bib_i 的任意前缀和值域都在 [0,s][0,s]。
  • 考虑一个前缀 a1…ka_{1\dots k} 的和 <0<0，则取后面的部分的和超过了 ss。
  • 考虑一个前缀 a1…ka_{1\dots k} 的和 >s>s，则取这段前缀的和超过了 ss。
  • 满足值域限制的条件下，一个子段和可以描述成两个前缀和相减的形式，显然这个差也在 [−s,s][-s,s] 中。
所以这是充要的。我们考虑直接对前缀和设计 dp：fi,jf_{i,j} 表示长度为 ii 的前缀加若干个数得到和为 jj 的前缀，最少需要添加多少个数。考虑转移，需要观察题目的特殊性质：考虑每两个数之间以及头尾的总共 n+1n+1 个空挡，只会在每个空挡里填恰好一个数。我们不妨把开头的空用来初始化状态，令 f0,i=[i>0]f_{0,i}=[i>0]。之后转移的时候首先要求 ai+j′∈[0,s]a_{i}+j'\in[0,s]，然后才能找到 kk 令 fi−1,j→fi,j+ai+kf_{i-1,j}\rightarrow f_{i,j+a_i+k}。时间复杂度 O(ns2)O(ns^2)，不可接受。也可以注意到这个转移是一个区间和、区间 min 的形式，可以做到 O(ns)O(ns)。
考虑把 ff 数组打个表看看，可以发现对于 ii 固定时，同一个 fi,jf_{i,j} 在 j∈[0,s] j\in[0,s] 时只有不超过两个不同的值，且更小的那个形成一段区间。考虑归纳证明，初始时只有 0,10,1 的不同值，且值为 00 的构成区间 [0,0][0,0]。转移时先 ban 掉一段区间（要求 j′+ai∈[0,s]j'+a_i\in[0,s]），此时值更小的仍然是区间（但是可能使全局相等，需要特殊处理），然后转移后值仍然等于更小值的点相当于把原区间沿着 aia_i 方向平移（不加更多数，保留 ff 值），于是仍然是区间，可以发现剩下的部分答案都是更小值加一。我们直接 O(1)O(1) 维护这些区间可以维护出 ff 数组最后的值，求出 fsf_s 即是最小长度 −n-n。于是在 O(n)O(n) 时间内解决了最小长度。
下面是代码。很短吧！
CPP
#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
int n,s;
int a[3000005];
void Main() {
	cin>>n;s=0;
	REP(i,0,n)cin>>a[i],s+=a[i];
	int cur=0,l=0,r=0;
	REP(i,0,n){
		int L=max(0ll,-a[i]),R=min(s,s-a[i]);
		if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
		else l=L,r=R,++cur;
		l+=a[i];r+=a[i];
		l=max(l,0ll);r=min(r,s);
		if(l>r)l=0,r=s,++cur;
	}
	over(cur+n+(r!=s))
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
当然这篇题解到这里还没有结束。原题是一个计数，但是因为各种原因被删掉了。这里也一起分享出来。
原 std 的做法是假的。注意到在 I1 的做法中，我们在原序列的空隙中插入新的数，但是如果我们钦定方案不同当且仅当其插入的方式不同，即把一个 xx 插在原序列中一个 xx 的左边和右边，在原定义中算同一种序列，但是在新版题意中认为这不算同一种。如何解决这个改变题意后的问题呢？
扩展 I1 的做法，考虑方案数的转移，设 gi,jg_{i,j} 为同定义下的方案数。区间平移的部分，gg 的转移仍然是区间平移，并在下文称之为【特殊区间】。不妨考虑 ai>0a_i>0 的情况，一开始 ban 掉的是 [0,ai−1][0,a_i-1] 的部分，而后面补进来这部分的时候，这些的 gg 值都相等，等于原本 gg 中 ff 更大的所有值的 gg 和。而对于既不是这一块又不是特殊区间的部分，将会在原值的基础上加上上面对应的 gg 和。
总结一下就是前后缀删点，前后缀加值为 00 的连续段，对非特殊区间做区间加。我们不进行区间平移，而是维护 tagtag 表示区间的平移量即可把问题静态化，做到 O(slog⁡s)O(s\log s)，但是仍然不可接受。
我们观察转移的过程，发现少有单点操作，都是对着整段的区间做操作，例如前后缀塞一个连续段，前后缀删连续段，这启发我们不仅是 ff，gg 的值也可以形成若干段连续段。经过打表验证，可以发现 gg 的值确实形成 O(n)O(n) 个连续段。由于要支持前后缀操作，我们直接开一个 deque 维护所有连续段的所有信息，包括左右端点和每个点的 gg 值。为了维护信息，我们需要维护：tpostpos 表示当前区间整体平移的偏移量；l,rl,r 表示特殊区间为 [l+tpos,r+tpos][l+tpos,r+tpos]；tv1,tv2tv_1,tv_2 表示特殊和非特殊区间的全局加的标记（需要支持这些全局加）；s1,s2s_1,s_2 表示特殊和非特殊区间的权值和（需要支持整体加，而加的值就是非特殊区间的答案和）。注意到这些都可以在维护 push，pop 操作的同时维护出来。一个大细节是 pop 区间后可能会出现全局 ff 相等的情况，即 [l,r][l,r] 变成整区间，此时会用到维护的非特殊区间的全局加标记和全局和，所以才两个都要维护。每个连续段被插入一次删除一次，push 次数为 nn，于是时间复杂度均摊 O(n)O(n)。可以讨论 aia_i 的正负性转移。
给出我的实现：
CPP
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
struct interval{
	int l,r,g;
	int calc(int tg=0){return ((r-l+1)*(tg+g))%MOD;}
};
int n,s;
int a[3000005];
#define inside(x) (x.l>=l&&x.r<=r)
void Main() {
	cin>>n;s=0;
	REP(i,0,n)cin>>a[i],s+=a[i];
	if(s<*max_element(a,a+n))assert(0)
	if(s<-*min_element(a,a+n))assert(0);
	if(!s)over(1)
	deque<interval>dq;
	dq.pb({0,0,1});dq.pb({1,s,1});
	int tpos=0,tval=0,l=0,r=0,sum1=1,sum2=s,tv2=0;
	REP(i,0,n){
		if(a[i]>=0){
			while(dq.size()&&dq.back().l+tpos>s-a[i]){
				if(inside(dq.back()))sum1-=dq.back().calc(tv2);
				else sum2-=dq.back().calc(tval);
				dq.pop_back();
			}
			if(dq.back().r+tpos>s-a[i]){
				if(inside(dq.back()))sum1-=(dq.back().g+tv2)*(dq.back().r+tpos-(s-a[i]))%MOD;
				else sum2-=(dq.back().r+tpos-(s-a[i]))*(tval+dq.back().g)%MOD;
				dq.back().r=s-a[i]-tpos;
			}
			sum1=(MOD+sum1%MOD)%MOD;
			sum2=(MOD+sum2%MOD)%MOD;
			r=min(r,s-a[i]-tpos);
			if(l>r){
				l=dq.front().l;r=dq.back().r;
				sum1=sum2;sum2=0;tv2=tval;tval=0;
			}
			if(a[i])dq.push_front({dq[0].l-a[i],dq[0].l-1,(MOD-tval)%MOD});
			tpos+=a[i];(tval+=sum1)%=MOD;(sum2+=sum1*(s+1-(r-l+1)))%=MOD;
		}else{
			a[i]*=-1;
			while(dq.size()&&dq.front().r+tpos<a[i]){
				if(inside(dq.front()))sum1-=dq.front().calc(tv2);
				else sum2-=dq.front().calc(tval);
				dq.pop_front();
			}
			if(dq.front().l+tpos<a[i]){
				if(inside(dq.front()))sum1-=(dq.front().g+tv2)*(a[i]-dq.front().l-tpos)%MOD;
				else sum2-=(a[i]-dq.front().l-tpos)*(dq.front().g+tval)%MOD;
				dq.front().l=a[i]-tpos;
			}
			sum1=(MOD+sum1%MOD)%MOD;
			sum2=(MOD+sum2%MOD)%MOD;
			l=max(l,a[i]-tpos);
			if(l>r){
				l=dq.front().l;r=dq.back().r;
				sum1=sum2;sum2=0;tv2=tval;tval=0;
			}
			dq.push_back({dq.back().r+1,dq.back().r+a[i],(MOD-tval)%MOD});
			tpos-=a[i];(tval+=sum1)%=MOD;(sum2+=sum1*(s+1-(r-l+1)))%=MOD;
		}
	}
    cout<<(dq.back().g+(inside(dq.back())?tv2:tval))%MOD<<endl;
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
其实这篇题解到这里还是没有结束。作为名义上的 writer，出锅之后我还得修，于是考虑原版题意的计数。能否改进 std 的做法呢？尝试对于同一个数的连续段 dp，发现似乎很困难。irris 和我都放弃了。
我们从问题的本质上入手。不妨直接对着序列 bb 做 dp，并把子序列的限制放到状态中。设 f(i,j,k)f(i,j,k) 表示填了 bb 序列的前 ii 项，匹配序列 aa 最多能匹配 jj 项，当前前缀和为 kk 的方案数。我们不妨先套用 I1 的 dp 求出这个最小长度 mm，这样状态数是 O(mns)=O(n2s)O(mns)=O(n^2s)。转移时可以枚举下一个数填什么，是 O(s)O(s) 的。提供一个代码主要部分。
CPP
int n;
int a[3000005];
int dp[105][105][1005];
int s;
int qlen(){
	int cur=0,l=0,r=0;
	REP(i,0,n){
		int L=max(0ll,-a[i]),R=min(s,s-a[i]);
		if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
		else l=L,r=R,++cur;
		l+=a[i];r+=a[i];
		l=max(l,0ll);r=min(r,s);
		if(l>r)l=0,r=s,++cur;
	}
	return cur+(r<s)+n;
}
void Main() {
	cin>>n;
	REP(i,0,n)cin>>a[i];
	s=accumulate(a,a+n,0ll);
	int m=qlen();
	REP(i,0,m+1){
		REP(j,0,n+1){
			REP(l,0,s+1)dp[i][j][l]=0;
		}
	}
	dp[0][0][0]=1;
	REP(i,0,m){
		REP(j,0,n+1){
			REP(l,0,s+1)if(dp[i][j][l]){
				REP(p,-l,s-l+1){
					int j2=j+(j<n&&a[j]==p);
					(dp[i+1][j2][l+p]+=dp[i][j][l])%=MOD;
				}
			}
		}
	}
	cout<<dp[m][n][s]<<endl;
}
可以发现这个 O(s)O(s) 转移容易做到 O(1)O(1)。具体地，我们转移 f(i,j,k)f(i,j,k)，先接收所有 f(i−1,j,l)f(i-1,j,l) 的值（毕竟都可以加一个数得到），然后再考虑其它特殊的。如果加入一个数之后可以匹配，就减掉 f(i−1,j,l−aj)f(i-1,j,l-a_j)。如果是加入一个数之后匹配了，就加上 f(i−1,j−1,l−aj−1)f(i-1,j-1,l-a_{j-1})。时间复杂度 O(n2s)O(n^2s)。
CPP
int n;
int a[3000005];
int dp[105][105][1005];
int s;
int qlen();//和上面相同，省略
void Main() {
	cin>>n;
	REP(i,0,n)cin>>a[i];
	s=accumulate(a,a+n,0ll);
	int m=qlen();
	REP(i,0,m+1){
		REP(j,0,n+1){
			REP(l,0,s+1)dp[i][j][l]=0;
		}
	}
	dp[0][0][0]=1;
	REP(i,0,m){
		REP(j,0,n+1){
			int sum=0;
			REP(l,0,s+1){
				sum+=dp[i][j][l];
			}
			REP(l,0,s+1){
				dp[i+1][j][l]=sum;
				if(j<n&&l>=a[j]&&l-a[j]<=s)dp[i+1][j][l]-=dp[i][j][l-a[j]];
				if(j>0&&l>=a[j-1]&&l-a[j-1]<=s)dp[i+1][j][l]+=dp[i][j-1][l-a[j-1]];
				(dp[i+1][j][l]+=MOD)%=MOD;
			}
		}
	}
	cout<<dp[m][n][s]<<endl;
}
考虑原做法的连续段想法。我们把 ss 那一维用连续段刻画，即将其划分成 poly(n)\rm{poly}(n) 个方案数相同的连续段，然后利用归并的方式合并即可。细节相当于把 f(i,j−1)f(i,j-1) 和 f(i,j)f(i,j) 分别平移对应距离后相减，然后做全局加。时间复杂度 O(nk+2)O(n^{k+2})，其中长度为 ss 的数组可以划分成 O(nk)O(n^k) 段。kk 具体是多少我也不太懂，反正至少是 22。
CPP
int n;
int a[3000005];
int s;
struct structures{
    int l,r,val;
};
#define vs vector<structures>
vs f[30005],g[30005];
int qlen();//和上面相同，省略
vs mover(vs a,int x){
    if(!x)return a;
    vs b;
    if(x>0)b.pb({0,x-1,0});
    for(auto [l,r,val]:a){
        int L=l+x,R=r+x;
        L=max(L,0ll);R=min(R,s);
        if(L<=R)b.pb({L,R,val});
    }
    if(x<0)b.pb({s+x+1,s,0});
    return b;
}
vs operator -(vs a,vs b){
    vector<int>t;
    int x=0,y=0,n=a.size(),m=b.size();
    while(x<n&&y<m){
        if(a[x].l==b[y].l)t.pb(a[x].l),++x,++y;
        else if(a[x].l<b[y].l)t.pb(a[x++].l);
        else t.pb(b[y++].l);
    }
    while(x<n)t.pb(a[x++].l);
    while(y<m)t.pb(b[y++].l);
    n=t.size();t.pb(s+1);
    vs c(n,{0,0,0});
    REP(i,0,n)c[i].l=t[i],c[i].r=t[i+1]-1;
    x=0;
    for(auto [l,r,val]:a){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=val,++x;
    }
    x=0;
    for(auto [l,r,val]:b){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=MOD-val,++x;
    }
    REP(i,0,n)c[i].val%=MOD;
    a.clear();
    int lstval=-1;
    for(auto [l,r,val]:c){
		if(val==lstval)a[a.size()-1].r=r;
		else a.pb({l,r,lstval=val});
	}
    return a;
}
void Main() {
	cin>>n;
	REP(i,0,n)cin>>a[i];
	s=accumulate(a,a+n,0ll);
	int m=qlen();
    REP(i,0,n+1){
        f[i].clear();
        g[i].clear();
        if(i)g[i]=vs(1,{0,s,0});
        else{
            g[i].pb({0,0,1});g[i].pb({1,s,0});
        }
    }
    REP(i,0,m){
        for(int j=n;j>=0;--j){
            int sum=0;
            for(auto [l,r,val]:g[j])(sum+=(r-l+1)%MOD*val)%=MOD;
            vs s1=j<n? mover(g[j],a[j]):vs(1,{0,s,0}),s2=j? mover(g[j-1],a[j-1]):vs(1,{0,s,0});
            g[j]=s2-s1;
            for(auto &l:g[j])(l.val+=sum)%=MOD;
        }
    }
    int x=g[n].size()-1;
	cout<<g[n][x].val<<endl;
}
然后再加入最优性。注意到对于一个 ii，使 ff 有值的 jj 一定是一个前缀 j≤Rij\le R_i。这可以理解为，给定你 ii 个可以加入的数，最多能匹配 aa 中的几位。这个翻转之后可以变成：对于 aa 的每个前缀，它最少添加几位。
同理，jj 也应该有下界 j≥Lij\ge L_i。这可以理解为，对于这个后缀，你只有若干个数可以加，最长能匹配的后缀，也就是最短需要能匹配的前缀。可以通过倒着做一样的 dp 解决。根据“两个数之间只能插一个”的理论，可以发现 Ri−Li+1≤2R_i-L_i+1\le 2，也就是对于一个 ii 只有最多 22 个 jj 是有用的。只转移这些，可以证明 ss 那一维只有 O(n2)O(n^2) 且跑不满个连续段，于是时间复杂度 O(n3)O(n^3)。
CPP
int n;
int a[3000005];
int s;
int mnm[3000005],mxm[3000005];
struct structures{
    int l,r,val;
};
#define vs vector<structures>
vs f[3000005],g[3000005];
int m;
int qlen(){
	int cur=0,l=0,r=0;
    mnm[0]=0;
	REP(i,0,n){
		int L=max(0ll,-a[i]),R=min(s,s-a[i]);
		if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
		else l=L,r=R,++cur;
		l+=a[i];r+=a[i];
		l=max(l,0ll);r=min(r,s);
		if(l>r)l=0,r=s,++cur;
        mnm[i+1]=cur+i+1;
	}
	return cur+(r<s)+n;
}
void getdp_back(){
	int cur=0,l=0,r=0;
    mxm[n]=m;
	for(int i=n-1;i>=0;--i){
		int L=max(0ll,-a[i]),R=min(s,s-a[i]);
		if(max(L,l)<=min(r,R))l=max(l,L),r=min(r,R);
		else l=L,r=R,++cur;
		l+=a[i];r+=a[i];
		l=max(l,0ll);r=min(r,s);
		if(l>r)l=0,r=s,++cur;
        mxm[i]=m-n-cur+i;
	}
}
vs mover(vs a,int x){
    if(!x)return a;
    vs b;
    if(x>0)b.pb({0,x-1,0});
    for(auto [l,r,val]:a){
        int L=l+x,R=r+x;
        L=max(L,0ll);R=min(R,s);
        if(L<=R)b.pb({L,R,val});
    }
    if(x<0)b.pb({s+x+1,s,0});
    return b;
}
vs operator -(vs a,vs b){
    vector<int>t;
    int x=0,y=0,n=a.size(),m=b.size();
    while(x<n&&y<m){
        if(a[x].l==b[y].l)t.pb(a[x].l),++x,++y;
        else if(a[x].l<b[y].l)t.pb(a[x++].l);
        else t.pb(b[y++].l);
    }
    while(x<n)t.pb(a[x++].l);
    while(y<m)t.pb(b[y++].l);
    n=t.size();t.pb(s+1);
    vs c(n,{0,0,0});
    REP(i,0,n)c[i].l=t[i],c[i].r=t[i+1]-1;
    x=0;
    for(auto [l,r,val]:a){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=val,++x;
    }
    x=0;
    for(auto [l,r,val]:b){
        while(c[x].r<l)++x;
        while(x<n&&c[x].l>=l&&c[x].r<=r)c[x].val+=MOD-val,++x;
    }
    REP(i,0,n)c[i].val%=MOD;
    a.clear();
    int lstval=-1;
    for(auto [l,r,val]:c){
		if(val==lstval)a[a.size()-1].r=r;
		else a.pb({l,r,lstval=val});
	}
    return a;
}
void Main() {
	cin>>n;
	REP(i,0,n)cin>>a[i];
	s=accumulate(a,a+n,0ll);
	m=qlen();getdp_back();
    REP(i,0,n+1){
        g[i].clear();
        if(i)g[i]=vs(1,{0,s,0});
        else{
            g[i].pb({0,0,1});g[i].pb({1,s,0});
        }
    }
	int xl=0,xr=0;
    REP(i,0,m){
    	int lxl=xl,lxr=xr;
    	while(xl<=n&&mxm[xl]<i+1)++xl;
    	while(xr+1<=n&&mnm[xr+1]<=i+1)++xr;
        for(int j=xr;j>=xl;--j){
            ++cnt;
            int sum=0;
            for(auto [l,r,val]:g[j])(sum+=(r-l+1)%MOD*val)%=MOD;
            vs s1=j<n? mover(g[j],a[j]):vs(1,{0,s,0}),s2=j? mover(g[j-1],a[j-1]):vs(1,{0,s,0});
            g[j]=s2-s1;
            for(auto &l:g[j])(l.val+=sum)%=MOD;
        }
        REP(i,lxl,xl)g[i]=vs(1,{0,s,0});
    }
    int x=g[n].size()-1;
	cout<<g[n][x].val<<endl;
}
很抱歉实力有限，当天的补救中我只能做到这了。当时是赶工到凌晨五点才写完的这个东西，第二天发现没人会更优的，做不到 3×1063\times 10^6 的范围，于是只能删掉这个题了。
如果大家有更好的想法欢迎沟通。

评论

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

正在加载评论...