P9509 『STA - R3』Aulvwc题目背景统计学是一门古老而迷人的学科。传说早在若干年前一位名为惠普的神灵来到地球发现了人类——另一种有智慧的物种……已加入 Hack 数据位于 Subtask 5不计分。题目描述定义一个序列{an}\{a_n\}{an​}是分部平均的当且仅当存在一个{1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n}的划分S1,S2,⋯ ,SkS_1,S_2,\cdots,S_kS1​,S2​,⋯,Sk​其中k1k1k1满足对于每个整数1≤i≤k1\le i\le k1≤i≤k序列{a}\{a\}{a}中以SiS_iSi​为下标的元素之平均数都是相等的整数。现在给定序列{an}\{a_n\}{an​}问它是否是分部平均的。如果你对于一些定义不很清楚可以查阅最后的「提示」部分。输入格式第一行一个正整数qqq表示询问组数。对于每组询问第一行一个正整数nnn描述序列长度。第二行nnn个整数表示序列{an}\{a_n\}{an​}。输出格式qqq行对于每组询问如果序列是分部平均的则输出Yes否则输出No。输入输出样例 #1输入 #14 5 1 1 1 1 1 5 1 2 3 4 5 5 1 1 1 1 6 5 -1 0 1 0 1输出 #1Yes Yes No No说明/提示提示一个集合SSS的划分定义为一组集合U1,U2,⋯ ,UkU_1,U_2,\cdots,U_kU1​,U2​,⋯,Uk​满足对于所有i≠ji\neq jij有Ui∩Uj∅U_i\cap U_j\varnothingUi​∩Uj​∅。U1∪U2∪⋯∪UkSU_1\cup U_2\cup\cdots\cup U_kSU1​∪U2​∪⋯∪Uk​S。一个序列{xn}\{x_n\}{xn​}的平均数定义为xˉx1x2⋯xnn1n∑i1nxi\bar x\dfrac{x_1x_2\cdotsx_n}{n}\dfrac 1n\sum_{i1}^nx_ixˉnx1​x2​⋯xn​​n1​i1∑n​xi​样例解释第一组数据的一种划分方案{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}。注意划分方案所提供的集合是下标集合。数据范围本题采用捆绑测试及子任务依赖。Subtaskn≤分值特殊性质依赖子任务1105210320∑ai031002514103501, 3 \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c|c}\hline\hline \textbf{Subtask} \bm{n}\le \textbf{分值} \textbf{特殊性质}\textbf{依赖子任务}\\\hline \textsf{1} 10 5 \\\hline \textsf{2} 10^3 20 \sum a_i0 \\\hline \textsf{3} 100 25 \sf1\\\hline \textsf{4} 10^3 50 \sf1\texttt{,}\ 3\\\hline \end{array}Subtask1234​n≤10103100103​分值5202550​特殊性质∑ai​0​依赖子任务11,3​​对于全部数据1≤q≤101\le q\le 101≤q≤102≤n≤1032\le n\le 10^32≤n≤103∣ai∣≤5×103|a_i|\le 5\times10^3∣ai​∣≤5×103。C实现#includecstdio#includecstringusingnamespacestd;intt,n,a[1007];shortf1[7][1007][2007],g1[7][1007][2007];ints,p[]{0,1799,1857,1927,1924,1981,1999};//判断的模数signedmain(){scanf(%d,t);while(t--){scanf(%d,n);s0;for(inti1;in;i)scanf(%d,a[i]),ssa[i];if(s%n!0){printf(No\n);//没有平均数continue;}ss/n;memset(f1,0,sizeoff1);memset(g1,0,sizeofg1);for(inti1;in;i)a[i]a[i]-s;//问题转化for(intk1;k6;k){g1[k][0][0]f1[k][0][0]1;for(inti1;in;i){for(intj0;jp[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;//这里显然可以剪去情况}}}intans1;for(intk1;k6;k){ansans(g1[k][n][0]3);//所有模数都要过}if(ans)printf(Yes\n);elseprintf(No\n);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容