首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#12991

作品选拔 题目描述 创新大赛组委会收到了 n 件学生参赛作品,每件作品都有对应的综合评审得分,其中第 i 件作品的得分为 a i 。 根据赛事章程,组委会需从所…

作品选拔

题目描述

创新大赛组委会收到了 n 件学生参赛作品,每件作品都有对应的综合评审得分,其中第 i 件作品的得分为 ai。

根据赛事章程,组委会需从所有备选作品中选出 m 件作品晋级市级终评。为保障终评作品的整体质量,要求选出的 m 件作品中,至少有 k 件作品的综合得分不低于赛事划定的基准线 x。

请你帮助组委会计算,一共有多少种符合要求的作品遴选方案?由于答案数值可能过大,请输出方案数对998244353取模后的结果。

输入格式

第一行,两个正整数n、m;

第二行,n 个正整数,分别表示 a1、a2、……、an;

第三行,两个正整数 k、x。

输出格式

输出满足条件的方案数对 998244353 取模后的结果。

输入样例#1

3 2

10 20 30

1 20

输出样例#1

3

输入样例#2

4 2

5 10 15 20

1 12

输出样例#2

5

说明提示:

对于50%的数据,1≤n≤20;

对于100%的数据,1≤n≤1000,1≤k≤m≤n,1≤ai、x≤10^9。

限制:

时间限制:1000ms,内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; using namespace std; const int MOD = 998244353; const int MAX = 1005; long long C[MAX][MAX]; // 预处理组合数 C(n, k) void init() { C[0][0] = 1; for (int i = 1; i &lt; MAX; i++) { C[i][0] = 1; for (int j = 1; j &lt;= i; j++) { C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } } int main() { init(); // 第一步:读 n, m int n, m; cin &gt;&gt; n &gt;&gt; m; // 第二步:读 n 个分数 int a[MAX]; for (int i = 0; i &lt; n; i++) { cin &gt;&gt; a[i]; } // 第三步:读 k, x int k, x; cin &gt;&gt; k &gt;&gt; x; // 统计高分、低分数量 int high = 0, low = 0; for (int i = 0; i &lt; n; i++) { if (a[i] &gt;= x) high++; else low++; } // 计算答案 long long ans = 0; int max_t = min(high, m); for (int t = k; t &lt;= max_t; t++) { int need = m - t; if (need &lt; 0 || need &gt; low) continue; ans = (ans + C[high][t] * C[low][need]) % MOD; } cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。