4.27

选拔赛补题

太菜了

前1.5h写了6个模板，然后挂机2.5h什么也不会。

C

题意

$S$的非空前缀和$T$的非空后缀拼接组成的本质不同字符串数量。

如果一个$S[1...i]$所组成的字符串与$S[1...j](j<i)$所组成的字符串是重复的， 那么这个字符串一定也可以由$S[1...i-1]$所组成， 因此可以使用类似SA中Height数组求本质不同字符串数量的算法， 考虑所有$S[1...i]$所组成的字符串与$S[1...i+1]$所组成的字符串有多少是重复的， 注意到只有当$S[i+1]=T[j]$时，$S[1...i]T[j...m]=S[1...i+1]T[j+1...m]$， 因此重复的数量是满足$S[i+1]=T[j]$的$j$的个数， 总体来看，就是$S[i]=T[j](i>1,j<m)$的对数， 设$len(S)=n,len(T)=m$，用$nm$减掉上述重复的数量即可。

F

题意

$n$个宝可梦，每个都有$p$的概率中病毒，每次可以检测多个宝可梦，如果其中有一个中病毒就会显示为阳性，直到全部确认这些宝可梦是否中病毒，才能去检测别的宝可梦，问期望检测次数。

$f[i]$表示$i$只宝可梦总体结果为阳性的期望次数，$g[i]$表示$i$只宝可梦总体结果未知的期望次数。

$P_1=\frac{1−(1−p)^j}{1−(1−p)^i}$

$P_2=1−(1−p)^j$

$f[i]=min_{1≤j<i}\{1+ (1−P_1)f[i−j]+P_1(f[j]+g[i−j])\}$

$g[i]=min_{1≤j≤i}\{1+P_2f[j]+g[i−j]\}$

答案是$g[n]$。

G

题意

每个节点向另一点连$0/1$条红边和$0/1$条蓝边，问给每个点换位置使得每个点的连边状态和连边对象都不变的排列方案数。

显然只有节点个数和类型都相同的连通块才能互相交换，不然肯定会出现不匹配的情况。 设同一类型和同一点数的连通块，个数为$a$，节点个数为$b$，则答案先乘上$a!$，表示先排列好，然后后面再对每一个顺次讨论方案数。

1.红蓝边交错的环，边数$=$点数，每个环有$b$种旋转方式，总方案为$b^a$。

2.两边都为红边的链，边数$=$点数$-1$，红边$-$蓝边$=1$，每个链可以头尾交换，总方案为$2^a$。

3.两边都为蓝边的链，边数$=$点数$-1$，红边$-$蓝边$=-1$，每个链可以头尾交换，总方案为$2^a$。

4.一边为红另一边为蓝的链，边数$=$点数$-1$，红边$=$蓝边，每个链方案唯一。

5.孤立点，点数$=1$，方案唯一。

CF1342E

题意

$n×n$的棋盘放$n$个棋子，要每个位置对应的行或列至少有一个棋子，且能互相攻击到（位于同一行或同一列且中间没有其它棋子）的棋子对数为$k$，问方案数。

orz

比赛和赛后都没看到只用放$n$个棋子，无限懵逼。

首先容易得到$n<k$才有合法方案。

不妨设每一行都放了一个棋子，这样一共放了$n$个，那么互相攻击的棋子一定是在同一列的。 容易得到$n-k$列有棋子，因此答案为

$$\binom{n}{n-k}(n-k)!\begin{Bmatrix}n\\n-k\end{Bmatrix}$$

如果$k\not=0$，答案需要乘$2$，因为还有对称的每一列都放了一个棋子。如果$k=0$，每一行都放了一个棋子等价于每一列都放了一个棋子，不需要乘$2$。

CF149D

题意

对一个匹配括号序列进行染色，每个括号可以不染或染成红色或蓝色，要求相邻括号颜色不同，一对匹配的括号必须有且只有一个被染色，求染色方案数。

记录一下每个左括号对应的右括号是哪个，然后通过记忆化搜索实现区间dp。如果区间端点是一对括号，施加一对匹配括号的限制并拆掉这两个dp里面的，里面的两个括号不要施加一对括号的限制因为不一定是一对的； 否则根据左括号对应右括号的位置拆成两个，此时只施加两个相邻括号的限制，因为右边的两个括号不一定是一对。