P9509 『STA - R3』Aulvwc

题目背景

统计学是一门古老而迷人的学科。

传说早在若干年前，一位名为惠普的神灵来到地球，发现了人类——另一种有智慧的物种……

已加入 Hack 数据，位于 Subtask 5，不计分。

题目描述

定义一个序列 {an}\{a_n\}{an​} 是分部平均的，当且仅当存在一个 {1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n} 的划分 $S_1,S_2,\cdots ,S_k$（其中 $k>1$），满足对于每个整数 $1\le i\le k$，序列 {a}\{a\}{a} 中以 $S_i$ 为下标的元素之平均数都是相等的整数。

现在，给定序列 {an}\{a_n\}{an​}，问它是否是分部平均的。

如果你对于一些定义不很清楚，可以查阅最后的「提示」部分。

输入格式

第一行，一个正整数 $q$，表示询问组数。

对于每组询问，第一行一个正整数 $n$，描述序列长度。第二行 $n$ 个整数，表示序列 {an}\{a_n\}{an​}。

输出格式

$q$ 行，对于每组询问，如果序列是分部平均的，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

4
5
1 1 1 1 1
5
1 2 3 4 5
5
1 1 1 1 6
5
-1 0 1 0 1

输出 #1

Yes
Yes
No
No

说明/提示

提示

一个集合 $S$ 的划分定义为一组集合 $U_1,U_2,\cdots ,U_k$，满足：

• 对于所有 $i\ne j$，有 $U_i\cap U_j=\varnothing$。
• $U_1\cup U_2\cup \cdots \cup U_k=S$。

一个序列 {xn}\{x_n\}{xn​} 的平均数定义为：
$$\bar{x}=\frac{x_1+x_2+\cdots +x_n}{n}=\frac{1}{n}\sum _{i=1}^n{x}_i$$

样例解释

第一组数据的一种划分方案：{1},{2},{3},{4},{5}\{1\},\{2\},\{3\},\{4\},\{5\}{1},{2},{3},{4},{5}。

第二组数据的一种划分方案：{1,5},{2,4},{3}\{1,5\},\{2,4\},\{3\}{1,5},{2,4},{3}。

注意：划分方案所提供的集合是下标集合。

数据范围

本题采用捆绑测试及子任务依赖。
$$\begin{array}{ccccc}\text{Subtask}& \mathbf{n}\le & \text{分值}& \text{特殊性质}& \text{依赖子任务}\\ \text{1}& 10& 5& & \\ \text{2}& 10^3& 20& \sum a_i=0& \\ \text{3}& 100& 25& & 1\\ \text{4}& 10^3& 50& & 1\text{,}3\end{array}$$

对于全部数据，$1\le q\le 10$，$2\le n\le 10^3$，$|a_i|\le 5\times 10^3$。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容