模拟赛5 题解

S2round赛高！

链表+线段树优化dp+数学+线段树二分

A.整数数列的解码

考试忘了加上链表了 $100\rightarrow 59$。

其实很简单，$m$ 就是 $-1$ 的个数，之后依次把每个数分配到 $m$ 里面就好了。

注意在遇到 $-1$ 时要删掉这一行，用双向链表维护就好。

B.优秀的子集

题意：求选出线段覆盖了所有线段的并的方案数。

那么我们可以设 $f[i][j]$ 表示我们考虑了前 $i$ 条线段，最远的右端点连续覆盖到 $j$ 方案数。

设当前线段的端点为 $[l,r]$ ，转移有：

不选择这条线段时，直接加上 $f[i-1][j]$。

当 $j<l$ 时，选上这条线段后对答案没有影响，还是加上 $f[i-1][j]$。

当 $l\le j<r$ 时，我们加上这条线段后右端点发生了变化，该状态不合法。

当 $j=r$ 时，加上这条线段后，所有右端点在 $[l,r]$ 的状态都可以转移过来，所以加上 $\sum_{k=l}^rf[i-1][k]$ 。

发现空间爆炸，于是我们可以考虑滚掉第一维。

但是这样子转移是 $O(n)$ 的，考虑转移的过程实质上是进行区间求和，单点加1，区间乘的操作。

所以可以使用线段树优化到 $O(\log n )$。

for(int i=1,j=0;i<=n;j=i,i++)
	{
		int nl=a[j+1].l,nr=a[j+1].r;
		while(i<n&&a[i+1].l<=nr)//找到最后一个和原段有交的点
			nr=max(nr,a[++i].r);
		change(1,1,lsh,a[j+1].r,1);//覆盖当前的段多了一种方案，初始
		for(int k=j+2;k<=i;k++)
		{	
			int ql=a[k].l,qr=a[k].r;
			int sum=query(1,1,lsh,ql,qr);
			change(1,1,lsh,qr,sum);//f[qr]+=sum[f[ql-qr]]
			if(qr+1<=nr) modify(1,1,lsh,qr+1,nr,2);//这些位置添加当前线段后最远位置不变，方案数*2
			if(ql==nl) change(1,1,lsh,qr,1); //我们忽略了只有一条线段的情况，即l=r
		}
		ans=1ll*ans*query(1,1,lsh,nr,nr)%mod;//不同段之间乘法原理，完全覆盖s
	}

C. 传统艺能

考场上打表打出来的，现在好好回顾这个题

首先我们考虑贡献：对于一个有序点对 $(a,b)$，它对答案有贡献当且仅当 $a>b$ 。

所以我们可以用树状数组轻松统计出这样的点对个数，即 $\sum_{i=1}^n\sum_{j=1}^n[a_i>a_j]$ 。

由于要算期望，我们还需要统计样本空间的大小。

我们考虑所有方案都相当于从 $n$ 个里面拿出 $2$ 个球比较，总方案 $\binom n 2$。

而一次会比较 $m$ 组球，所以一对球的总贡献是 $\frac {1}{\binom n 2}\times m=\frac{1}{2(n-1)}$ 。