自动搬运

查看原文

来自洛谷，原作者为

	yinbe 硬币被掷出，正逆的转换从未停止

搬运于2025-08-24 22:36:32，当前版本为作者最后更新于2025-07-07 15:04:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

求所有 $K$ 满足给定正整数序列的所有长度为 $K$ 的子串存在子序列使得它的数的和等于子串的数的和的一半。

数据范围

$1 \le N \le 1000$

$1 \le T \le 120$

每个数组的元素和均不超过 $10^5$。

思路

直接枚举区间时间复杂度已经达到 $O(n^2)$ 了，必须 $O(1)$ 或 $O(\log n)$ 判断才能过，这很难搞。

注意到“每个数组的元素和均不超过 $10^5$”，这提示我们对值域进行处理。

定义 $s_{i}=\sum\limits_{j=1}^{i} a_{j}$。

$dp_{i}$ 表示要满足和为 $i$ 的子序列的左端最右的下标，为什么是最右呢？因为在子串右端点确定时，越往左越容易被字串左端点包含，就能产生更多答案。

我们枚举右端点 $r$，用类似 $01$ 背包的方式更新 $dp$ 数组，然后再枚举左端点 $l$，判断子串 $\left [ l,r \right ]$ 是否满足要求：

• $2|(s_{r}-s_{l-1})$，即子串的数的必须要能整除 $2$ 才能分成相等的 $2$ 部分。
• $l \le dp_{\frac{s_{r}-s_{l-1}}{2}}$，即这个字串必须包含和为 $\frac{s_{r}-s_{l-1}}{2}$ 的子序列。

将不满足要求的字串长度 $K$ 排除，剩下的就是答案。

时间复杂度 $O(Tn\sum\limits a_{i})$，常数较小，可过。

代码

#include<iostream>
#include<vector>
using namespace std;
int T,n,a[1005],s[1005],dp[100005];
bool flag[1005];
vector<int>ans;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		for(int i=0;i<=s[n];i++)
			dp[i]=-1;
		dp[0]=0;
		ans.clear();
		scanf("%d",&n);
		s[0]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			s[i]=s[i-1]+a[i];
			flag[i]=true;
		}
		for(int r=1;r<=n;r++)
		{
			for(int sum=min(s[n]/2,s[r]);sum>=a[r];sum--)
				dp[sum]=max(dp[sum],dp[sum-a[r]]);
			dp[a[r]]=r;
			for(int l=1;l<=r;l++)
			{
				if(!((s[r]-s[l-1])%2==0&&dp[(s[r]-s[l-1])/2]>=l))
					flag[r-l+1]=false;
			}
		}
		for(int len=1;len<=n;len++)
		{
			if(flag[len])
				ans.push_back(len);
		}
		printf("%llu ",ans.size());
		for(int x:ans)
			printf("%d ",x);
		printf("\n");
	}
	return 0;
}