专栏文章

P12558 [UOI 2024] Heroes and Monsters 题解

CCoffee_zzz/xin
P12558题解参与者 6已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@mip5hzca
此快照首次捕获于
2025/12/03 06:29
3 个月前
此快照最后确认于
2025/12/03 06:29
3 个月前
查看原文
我们把 aa 和 bb 按照从小到大的顺序排列，考虑刻画判定大小为 mm 的集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件。为了满足条件，我们可以贪心，让 SS 中的元素与 b1∼bmb_1 \sim b_m 配对，同时让不在 SS 中的元素与 bm+1∼bnb_{m+1} \sim b_n 配对。
更具体地，集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法，当且仅当：
  • 设在 SS 中的第 ii 小的元素为 axa_x，则有 ax>bia_x \gt b_i；
  • 设不在 SS 中的第 ii 小的元素为 aya_y，则有 ay<bm+ia_y \lt b_{m+i}。
于是，当 mm 确定时，我们可以设 dpi,jdp_{i,j} 表示考虑完 a1∼aia_1\sim a_i 且此时有 jj 个元素被选入 SS 中的方案数，枚举下一个元素是否选入 SS 即可得到转移方程为：
dpi,j=dpi−1,j−1×[ai>bj]+dpi−1,j×[ai<bm+j]dp_{i,j}=dp_{i-1,j-1} \times [a_i \gt b_j]+dp_{i-1,j} \times [a_i \lt b_{m+j}]
dpn,mdp_{n,m} 即为 l=ml=m 且 r=mr=m 的询问的答案。我们对每一个 0≤m≤n0 \le m \le n 都求出 dpn,mdp_{n,m} 的值，再预处理一下前缀和即可做到 O(1)\mathcal O(1) 回答单次询问。这样做的时间复杂度为 O(n3+q)\mathcal O(n^3+q)，考虑优化。
我们需要对每一个 mm 都做一次 dp 是复杂度很大的原因之一，但是 mm 是判定条件中的一个参数，有没有什么办法把判定条件中的 mm 消掉呢？
我们可以做一个变形，把判定集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件修改为：
  • 设在 SS 中的第 ii 小的元素为 axa_x，则有 ax>bia_x \gt b_i；
  • 设不在 SS 中的第 ii 大的元素为 aya_y，则有 ay<bn−i+1a_y \lt b_{n-i+1}。
显然改之后的条件和改之前的条件是等价的，我们只是把不在 SS 中的元素的枚举顺序改变了，但这样做消去了判定条件中的 mm。同时，看到这个 dp 形式，我们容易联想到分别对 aa 的前缀和后缀做一个 dp，最后把它们拼起来。
具体地，我们设 fi,jf_{i,j} 表示在只受第一个条件的限制下考虑完 a1∼aia_1 \sim a_i 且此时有 jj 个元素被选入 SS 中的方案数，gi,jg_{i,j} 表示在只受第二个条件的限制下考虑完 an∼aia_n \sim a_i 且此时有 jj 个元素没有被选入 SS 中的方案数，枚举下一个元素的状态即可得到转移方程为：
fi,j=fi−1,j+fi−1,j−1×[ai>bj]gi,j=gi+1,j−1+gi+1,j×[ai<bn−j+1]f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times[a_i \gt b_j]\\ g_{i,j}=g_{i+1,j-1}+g_{i+1,j}\times[a_i \lt b_{n-j+1}]
接下来我们考虑怎么把数组 ff 和数组 gg 拼起来。如果我们随便找一个位置 ww 将序列 aa 拆成 a1∼awa_1\sim a_w 的前缀与 aw+1∼ana_{w+1}\sim a_n 的后缀显然是有问题的——可能在 aa 的前缀中存在一个不在 SS 中的 aya_y 不满足 ay<bn−i+1a_y \lt b_{n-i+1} 的条件，也可能在 aa 的后缀中存在一个在 SS 中的 axa_x 不满足 ax>bia_x \gt b_i 的条件。
于是，我们希望对每一个集合大小 mm 找到一个位置 kk，使得 a1∼aka_1 \sim a_k 中的元素如果不在 SS 中则一定满足 ay<bn−i+1a_y \lt b_{n-i+1} 的条件，且 ak+1∼ama_{k+1} \sim a_m 中的元素如果在 SS 中则一定满足 ax>bia_x \gt b_i 的条件。
因为现在集合大小 mm 是已知的，所以我们是希望判定集合 SS 合法的条件中出现 mm 的，于是我们可以再对判定集合 S={as1,as2,…,asm}S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\} 合法的充要条件做一个变形：
  • 设在 SS 中的第 ii 大的元素为 axa_x，则有 ax>bm−i+1a_x \gt b_{m-i+1}；
  • 设不在 SS 中的第 ii 小的元素为 aya_y，则有 ay<bm+ia_y \lt b_{m+i}。
我们还是只改变了元素的枚举顺序，但这样的判定条件非常有利于我们找到满足要求的位置 kk。现在，位置 kk 的要求变为了：
  • 对于 a1∼aka_1 \sim a_k 中每一个不在 SS 中的元素 aya_y，都满足 ay<bm+ia_y \lt b_{m+i}；
  • 对于 ak+1∼ana_{k+1} \sim a_n 中每一个在 SS 中的元素 axa_x，都满足 ax>bm−i+1a_x \gt b_{m-i+1}。
分析一下，如果我们有 ay<bma_y \lt b_{m} 则我们一定有 ay<bm+ia_y \lt b_{m+i}，而如果我们有 ax>bma_x \gt b_m 则我们一定有 ax>bm−i+1a_x\gt b_{m-i+1}，所以我们只需要满足 aa 的前缀都小于 bmb_m 且 aa 的后缀都大于 bmb_m 就可以满足条件了！于是我们所求的 kk 就是最大的满足 ak<bma_k \lt b_m 的位置 kk。
接下来我们只需要对于每一个 mm 找到划分位置 kk，枚举前缀中在 SS 中的元素的个数 cc，并将 l=ml=m 且 r=mr=m 的询问的答案加上 fk,c×gk+1,n−k−m+cf_{k,c} \times g_{k+1,n-k-m+c} 即可。
同样做一个前缀和即可做到 O(1)\mathcal O(1) 回答单次询问，总时间复杂度 O(n2+q)\mathcal O(n^2+q)，可以通过。
C
const int N=5e3+5,mod=998244353;
int n,a[N],b[N],f[N][N],g[N][N],q,sum[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	f[0][0]=1,g[n+1][0]=1;
	for(int i=1;i<=n;i++){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=i;j++){
			f[i][j]=f[i-1][j];
			if(a[i]>b[j]) add(f[i][j],f[i-1][j-1]);
		}
	}
	for(int i=n;i>=1;i--){
		g[i][0]=g[i+1][0];
		for(int j=1;j<=n-i+1;j++){
			g[i][j]=g[i+1][j];
			if(a[i]<b[n-j+1]) add(g[i][j],g[i+1][j-1]);
		}
	}
	for(int m=0;m<=n;m++){
		int k=0;
		while(k<n&&a[k+1]<b[m]) k++;
		for(int c=0;c<=m;c++) if(k>=c&&n-k-m+c>=0) add(sum[m],1ll*f[k][c]*g[k+1][n-k-m+c]%mod);
		if(m) add(sum[m],sum[m-1]);
	}
	cin>>q;
	for(int i=1,l,r;i<=q;i++){
		cin>>l>>r;
		if(l==0) cout<<sum[r]<<endl;
		else cout<<(sum[r]-sum[l-1]+mod)%mod<<endl;
	}
}

评论

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

正在加载评论...