P8166 [eJOI2021] Kpart 题解
Fgighkcgrfox
·
·
题解
P8166 [eJOI2021] Kpart 题解
模拟赛爆零的一道题。挺不错的一道题。
思路
暴力做法
先枚举 k ,然后枚举每个区间，用背包判断能不能取到。
正解
先枚举右端点 r，然后用 f_i 表示当前想要从 a_1\dots a_r 中选取若干个数和为 i 时，左端点的最大值。这样就意味着你无法从 a_{f_i+1}\dots a_r 中找出和为 i 的部分。（这部分可能比较难以理解，建议多读几遍体会一下。）
然后暴力枚举左端点 l，令 s=\sum _{i=l} ^r a_i（可以用前缀和方快速求出 s），判断是否满足以下条件：
时间复杂度 O(Tn\sum a_i)。
代码
$ans_i=0$ 表示区间长度为 $i$ 符合题意，反之亦然。
$f$ 与上文意思相同。
码风较丑勿喷。
```cpp
int T,n,a[1005],f[100005],qzh[1005];bool ans[1005];vector<int>v;
int main(){
scanf("%d",&T);
while(T--){
v.clear();
for(int i=1;i<=n;i++)ans[i]=0;
for(int i=0;i<=(qzh[n]>>1);i++)f[i]=0;//初始化,也可用memset。
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),qzh[i]=qzh[i-1]+a[i];
for(int i=1;i<=n;i++){
for(int j=min(qzh[i],qzh[n]>>1);j>a[i];j--)f[j]=max(f[j],f[j-a[i]]);
f[a[i]]=i;//求 f 数组，过程类似于背包。
for(int j=1;j<=i;j++)if(((qzh[i]-qzh[j-1])&1)||f[(qzh[i]-qzh[j-1])>>1]<j)ans[i-j+1]=1;//暴力枚举左端点。
}
for(int i=1;i<=n;i++)
if(!ans[i])v.push_back(i);
printf("%llu ",v.size());//注意 v.size() 类型是 unsigned long long。
for(auto i:v)printf("%d ",i);
puts("");
}
return 0;
}
```