P8166 [eJOI 2021] Kpart / 背包 dp
考虑对于每一个区间判断是否为平衡的，那么设 \(f_{i,j}\) 表示前 \(i\) 个位置且选择的值为 \(j\) 的最大左端点，利用类似背包的转移即可。
然后直接判断如果 \(f_{i,x}\ge j\) 那么 \([j,i]\) 区间合法，其中 \(x\) 为区间和的一半。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){char c=getchar();int ans=0,f=1;while(c<48||c>57) (c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
const int N=1010,M=1e5+10;
int a[N],vis[M],n,s[N],f[M];
inline void solve(){n=read();for (int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];for (int i=1;i<=n;i++) vis[i]=1;for (int i=1;i<=(s[n]>>1);i++) f[i]=0;for (int i=1;i<=n;i++){for (int j=(s[n]>>1);j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]);f[a[i]]=i;for (int j=1;j<=i;j++) vis[i-j+1]&=((s[i]-s[j-1])%2==0&&f[(s[i]-s[j-1])>>1]>=j);}vector<int>anss;for (int i=1;i<=n;i++) if (vis[i]) anss.push_back(i);printf("%lld ",(int)anss.size());for (auto i:anss) printf("%lld ",i);puts("");
}
main(){int T=read();while(T--) solve();return 0;
}