[eJOI 2021] Kpart 题解
yinbe_swsgroitfh
·
·
题解
题目
求所有 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}。
我们枚举字串右端点 $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})$，常数较小，可过。
## 代码
```cpp
#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;
}
```