2025信奥赛C++提高组csp-s复赛真题及题解：员工招聘
题目描述
小 Z 和小 H 想要合伙开一家公司，共有n nn人前来应聘，编号为1 ∼ n 1 \sim n1∼n。小 Z 和小 H 希望录用至少m mm人。
小 H 是面试官，将在接下来n nn天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个1 ∼ n 1 \sim n1∼n的排列p pp，然后在第i ii(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 天通知编号为p i p_ipi的人前来面试。
小 H 准备了n nn套难度不一的面试题。由于n nn个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第i ii(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 天的面试题的难度为s i ∈ { 0 , 1 } s_i \in \{0,1\}si∈{0,1}，其中s i = 0 s_i = 0si=0表示这套题的难度较高，没有人能够做出；s i = 1 s_i = 1si=1表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。
然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为i ii(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 的人的耐心上限可以用非负整数c i c_ici描述，若在他之前已经有不少于c i c_ici人被拒绝或放弃参加面试，则他也将放弃参加面试。
小 Z 想知道一共有多少种面试的顺序p pp能够让他们录用至少m mm人。你需要帮助小 Z 求出，能够录用至少m mm人的排列p pp的数量。由于答案可能较大，你只需要求出答案对998 244 353 998\,244\,353998244353取模后的结果。
输入格式
输入的第一行包含两个正整数n , m n, mn,m，分别表示前来应聘的人数和希望录用的人数。
输入的第二行包含一个长度为n nn的字符串s 1 … s n s_1 \dots s_ns1…sn，表示每一天的面试题的难度。
输入的第三行包含n nn个非负整数c 1 , c 2 , … , c n c_1, c_2, \dots, c_nc1,c2,…,cn，表示每个人的耐心上限。
输出格式
输出一行一个非负整数，表示能够录用至少m mm人的排列p pp的数量对998 244 353 998\,244\,353998244353取模后的结果。
输入输出样例 1
输入 1
3 2 101 1 1 2输出 1
2输入输出样例 2
输入 2
10 5 1101111011 6 0 4 2 1 2 5 4 3 3输出 2
2204128说明/提示
【样例 1 解释】
共有以下 2 种面试的顺序p pp能够让小 Z 和小 H 录用至少 2 人:
- p = [ 1 , 2 , 3 ] p = [1,2,3]p=[1,2,3], 依次录用编号为 1 的人和编号为 3 的人;
- p = [ 2 , 1 , 3 ] p = [2,1,3]p=[2,1,3], 依次录用编号为 2 的人和编号为 3 的人。
【数据范围】
对于所有测试数据，保证:
- 1 ≤ m ≤ n ≤ 500 1 \leq m \leq n \leq 5001≤m≤n≤500;
- 对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，均有s i ∈ { 0 , 1 } s_i \in \{0,1\}si∈{0,1};
- 对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，均有0 ≤ c i ≤ n 0 \leq c_i \leq n0≤ci≤n。
| 测试点编号 | n ≤ n \leqn≤ | m mm | 特殊性质 |
|---|---|---|---|
| 1 , 2 1,21,2 | 10 1010 | ≤ n \leq n≤n | 无 |
| 3 ∼ 5 3 \sim 53∼5 | 18 1818 | ^ | ^ |
| 6 ∼ 8 6 \sim 86∼8 | 10 2 10^2102 | ^ | A |
| 9 ∼ 11 9 \sim 119∼11 | ^ | ^ | 无 |
| 12 ∼ 14 12 \sim 1412∼14 | 500 500500 | = 1 =1=1 | ^ |
| 15 1515 | ^ | = n =n=n | ^ |
| 16 , 17 16,1716,17 | ^ | ≤ n \leq n≤n | A |
| 18 ∼ 21 18 \sim 2118∼21 | ^ | ^ | B |
| 22 ∼ 25 22 \sim 2522∼25 | ^ | ^ | 无 |
特殊性质 A: 对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，均有s i = 1 s_i = 1si=1。
特殊性质 B: 在s 1 , s 2 , … , s n s_1, s_2, \dots, s_ns1,s2,…,sn中最多只有 18 个取值为 1，即∑ i = 1 n s i ≤ 18 \sum_{i=1}^{n} s_i \leq 18∑i=1nsi≤18。
思路分析
动态规划：状态f[i][j][k]表示处理了前i天，当前阈值（被拒绝或放弃的人数）为j，且预留了k个空位（对应c值大于j的人）的方案数。通过滚动数组优化空间。
核心步骤：
- 预处理：统计每个
c值的人数a[]和前缀和t[]，计算阶乘和组合数。 - DP 转移：
- 根据第
i+1天的面试题难度s[i+1]分两种情况。 - 每种情况又根据是否放置
c<=j的人、处理预留空位等细分。 - 转移时通过组合数计算选择方案，并乘以阶乘考虑顺序。
- 根据第
- 统计答案：对于最终阈值
j（满足录用人数n-j >= m），取预留空位数k = n - t[j]，将f[n][j][k]乘以k!（剩余c>j的人任意排列）累加到答案。
复杂度：
- 时间：
O(n^3)，但常数较小，n=500可过。 - 空间：
O(n^2)，使用滚动数组。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=510;constintMOD=998244353;intn,m;chars[N];intc[N];inta[N],t[N];// a[i]: c值为i的人数，t[i]: c值<=i的人数longlongf[N][N];// 滚动数组，f[j][k] 表示当前处理了前i天，阈值为j，预留空位klonglongg[N][N];// 下一层状态longlongC[N][N];// 组合数longlongfact[N];// 阶乘intmain(){scanf("%d%d",&n,&m);scanf("%s",s+1);// s[1..n]for(inti=1;i<=n;++i){scanf("%d",&c[i]);++a[c[i]];}// 预处理 t[]t[0]=a[0];for(inti=1;i<=n;++i){t[i]=t[i-1]+a[i];}// 预处理阶乘和组合数fact[0]=1;for(inti=1;i<=n;++i){fact[i]=fact[i-1]*i%MOD;}for(inti=0;i<=n;++i){C[i][0]=C[i][i]=1;for(intj=1;j<i;++j){C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;}}// 初始化f[0][0]=1;for(inti=0;i<n;++i){// 清空 gfor(intj=0;j<=n;++j){for(intk=0;k<=n;++k){g[j][k]=0;}}// 枚举当前状态 f[j][k]for(intj=0;j<=i;++j){for(intk=0;k<=n;++k){longlongcur=f[j][k];if(cur==0)continue;if(s[i+1]=='1'){// 转移1：预留一个空位（放一个 c>j 的人，延后处理）g[j][k+1]=(g[j][k+1]+cur)%MOD;// 转移2：放一个 c<=j 的人，同时处理 l 个 c=j+1 的空位intA=a[j+1];intt_j=t[j];for(intl=0;l<=min(k,A);++l){longlongcomb=C[k][l]*C[A][l]%MOD*fact[l]%MOD;longlongval=cur*(t_j-i+k)%MOD*comb%MOD;g[j+1][k-l]=(g[j+1][k-l]+val)%MOD;}}else{// s[i+1] == '0'intA=a[j+1];intt_j1=t[j+1];for(intl=0;l<=min(k,A);++l){longlongcomb=C[k][l]*C[A][l]%MOD*fact[l]%MOD;// 转移A：放一个 c<=j+1 的人，同时处理 l 个空位longlongval1=cur*(t_j1-i+k-l)%MOD*comb%MOD;g[j+1][k-l]=(g[j+1][k-l]+val1)%MOD;// 转移B：钦定一个新的空位longlongval2=cur*comb%MOD;g[j+1][k-l+1]=(g[j+1][k-l+1]+val2)%MOD;}}}}// 滚动数组swap(f,g);}longlongans=0;for(intj=0;j<=n-m;++j){intk=n-t[j];if(k>=0&&k<=n){ans=(ans+f[j][k]*fact[k])%MOD;}}printf("%lld\n",ans);return0;}各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
