比赛题解

· · 题解

对于每两个平均数相同的划分方案里的子集 S,T，可以合并成一个子集。

那我们只需要把数分成两个子集即可。根据此，可知题目所知的相等的平均数即为整个数列的平均数。

显然可以将每个数减去这个平均数。此时问题转化为，\texttt{Yes} 即找到转化后的一个非全选，非全不选的和为 0 的子序列。

这里显然列出 dp：f_{i,j} 为前 i 个数中和为 j 的方案。f_{i,j}=f_{i-1,j}+f_{i-1,j-a_i}。答案即为 [f_{n,0}\geq 3]

发现肯定过不了，但我们有同余科技，如果把和为 j 改为和 \bmod p=j，就很轻松了，于是多判几次即可。

#include <cstdio>
#include <cstring>
using namespace std;

int t,n,a[1007];
short f1[7][1007][2007],g1[7][1007][2007];
int s,p[]={0,1799,1857,1927,1924,1981,1999};//判断的模数
signed main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);s=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),s=s+a[i];
        if(s%n!=0){
            printf("No\n");//没有平均数
            continue;
        }
        s=s/n;
        memset(f1,0,sizeof f1);
        memset(g1,0,sizeof g1);
        for(int i=1;i<=n;i++) a[i]=a[i]-s;//问题转化
        for(int k=1;k<=6;k++){
            g1[k][0][0]=f1[k][0][0]=1;
            for(int i=1;i<=n;i++){
                for(int j=0;j<p[k];j++){
                    f1[k][i][j]=g1[k][i-1][(j-a[i]+p[k]+p[k]+p[k])%p[k]];
                    g1[k][i][j]=g1[k][i-1][j]+f1[k][i][j];
                    if(g1[k][i][j]>10000) g1[k][i][j]=10000;//这里显然可以剪去情况
                }
            }
        }
        int ans=1;
        for(int k=1;k<=6;k++){
            ans=ans&&(g1[k][n][0]>=3);//所有模数都要过
        }
        if(ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}