专栏文章

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

lliujiaxi123456
P14364题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mind632l
此快照首次捕获于
2025/12/02 00:28
3 个月前
此快照最后确认于
2025/12/02 00:28
3 个月前
查看原文

大体思路：

显然是 DP，把 cic_i 排序后，状态大概就是 ss 一维，cc 一维，录用了多少人一维。
贡献延迟计算。

具体思路：

先设 fi,jf_{i, j} 表示前 ii 个人，录用了 jj 个人，我们令 d=i−jd = i-j（即耐心的阈值）。
显然转移不了，原因是不知道还剩哪些 cc 可以用，哪些不能用。
考虑怎么记：
  • 影响的显然是 ≤d\le d 和 >d> d 的数量。
  • 由于 dd 不减，所以显然记录 ≤d\le d 的数量。
分析一下转移时的限制：
  • 若 si=0s_i=0：必然无法录用。
  • 若 si=1s_i=1：
    • 若 ci≤dc_i\le d：无法录用。
    • 否则可以。
发现直接转移的主要问题在于当 d←d+1d\leftarrow d+1 时，c=d+1c = d+1 的部分的数量不好计算。
因此，如果每次都把 ii 的贡献直接钦定好在上述情况下显然是不行的。
考虑贡献延迟计算：
  • 最直接的思路就是在 d←d+1d\leftarrow d+1 时，枚举 c=d+1c=d+1 的数量转移。
  • 由于对于同样的 i,ki,k，这样是 ∑cntj\sum cnt_j 的，所以是 O(n3)O(n^3) 的。
但这样转移非常复杂，考虑有没有简洁一点的做法：
  • 发现主要是录用不好转移，考虑容斥，用 cc 没有限制的情况减去 ci≤dc_i\le d 的。
  • 这样 si=1s_i=1 的情况就分为三种：
    • 使用 ci≤dc_i\le d，且不录用，这个贡献可以直接算。
    • 使用 ci≤dc_i\le d，但录用，这个贡献也可以直接算（注意贡献是负的）。
    • 使用 ci>dc_i> d，录用，贡献没法直接算，记到后效性里面，贡献延迟计算。
  • 于是设 fi,j,kf_{i, j, k} 表示前 ii 个人，录用了 jj 个人，前 ii 个中有 kk 个贡献已经算好了。
考虑转移：
  • 考虑从前向后转移。
  • si=0s_i = 0：
    • 直接 fi,j,k→fi+1,j,kf_{i, j, k} \rightarrow f_{i+1, j, k}。
  • si=1s_i = 1：
    • 不录用：
      • fi,j,k⋅(all(i−j)−k)→fi+1,j,k+1f_{i, j, k}\cdot (all(i-j)-k)\rightarrow f_{i+1, j, k+1}
    • 录用，且合法：
      • fi,j,k→fi+1,j+1,kf_{i, j, k}\rightarrow f_{i+1, j+1, k}
    • 录用，但不合法：
      • fi,j,k⋅−(all(i−j)−k)→fi+1,j+1,k+1f_{i, j, k}\cdot -(all(i-j)-k)\rightarrow f_{i+1, j+1, k+1}
统计答案：
  • ans=∑j=mn∑k=0nfn,i,k⋅(n−k)!ans = \sum_{j=m}^n\sum_{k=0}^nf_{n, i, k}\cdot (n-k)!
  • 比较显然吧，就是还有 n−kn-k 个贡献没有钦定，剩下的直接排列即可。

Code：

CPP
#include<bits/stdc++.h>
using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t;
#define ll long long
using namespace std;


const int Maxn = 505;
const ll MOD = 998244353;

namespace Josh_zmf {
	
	int N, M, all[Maxn], f[Maxn][Maxn][Maxn]; string s; ll fac[Maxn];

	inline int main() {
		cin>> N>> M>> s, s = ' ' + s;
		for(int i=1, x; i<=N; i++)	cin>> x, all[x]++;
		for(int i=1; i<=N; i++)	all[i] += all[i-1];
		f[0][0][0] = 1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<=i; j++) {
				for(int k=0; k<=i; k++) {
					if(s[i+1] == '0') {
						f[i+1][j][k] = f[i][j][k];
					} else {
						f[i+1][j+1][k] = (f[i+1][j+1][k] + f[i][j][k]) %MOD;
						if(all[i-j]-k > 0) {
							f[i+1][j+1][k+1] = (f[i+1][j+1][k+1] + -1ll*f[i][j][k]*(all[i-j]-k)) %MOD;
							f[i+1][j][k+1] = (f[i+1][j][k+1] + 1ll*f[i][j][k]*(all[i-j]-k)) %MOD;
						}
					}
				}
			}
		}
		fac[0] = 1;
		for(int i=1; i<=N; i++)	fac[i] = fac[i-1]*i %MOD;
		ll ans = 0;
		for(int j=M; j<=N; j++) {
			for(int k=0; k<=N; k++)	ans += f[N][j][k]*fac[N-k] %MOD;
		}
		cout<< (ans%MOD+MOD)%MOD<< '\n';
		return 0;
	}

} bool ED;


signed main() {
#if defined(ONLINE_JUDGE) && ONLINE_JUDGE == 1

#elif defined(Debugging)
	freopen("../__IO__/NAME.in", "r", stdin);
#elif !defined(LOCAL)
	freopen("NAME.in", "r", stdin);
	freopen("NAME.out", "w", stdout);
#else
	// freopen("../__IO__/NAME.in", "r", stdin);
	// freopen("../__IO__/NAME.out", "w", stdout);
#endif
	int st = clock(); Josh_zmf::main();
#ifndef Debugging
	cerr<< "time:: "<< clock()-st<< "ms\n";
	cerr<< "Static Memory:: "<< (int)(abs(&ST-&ED)/1024./1024)<< "MB\n";
#endif
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...