2024.10.14 题目

题解：2024.10.14 模拟赛

通配符

递推 枚举

有 $m$ 个不同的字符串，第 $i$ 个字符串为 $t_i$。又有长度为 $n$ 的含有 $\text{*}$ 的字符串 $S$，通配符 $\text{*}$ 可以在必要时变为任意字符串包括空串。对于 $S$ 的任意连续子串 $s\in S$，若 $s$ 能匹配任意 $t_i$ 则称 $s$ 是好的。求好的 $s$ 的数量。

树

并查集 树

有 $n$ 个点的树，第 $i$ 个点上染了 $c_i=0/1$ 的颜色。设 $S=\{i|c_i=1\},T=\{i|c_i=0\}$，则树的价值为 $\sum _{i\in S}\sum _{j\in T}d(i,j)$，其中 $d(i,j)$ 表示 $i$ 到 $j$ 的简单路径上的边权最大值。可以修改最多一个点使它的颜色反转，求最大价值。

木棍

有一根长度为 $n$ 的木棍，可以变出另外三根木棍 $a,b,c$ 满足 $n<a<b<c\le 4\times n$。如果这 $4$ 根木棍能够组成三角形，则称这次变换为成功的变换。求可能的成功的变换的数量。

群星

有一游戏分为 $k$ 个世纪，第 $i$ 个世纪会发生 $a_i$ 场最后战争。游戏里有 $n$ 个文明，第 $i$ 个文明初始排名为 $i$。每场战争会在 $\frac{n(n-1)}{2}$ 对文明中随机选取一对，交换排名。对于每个世纪，你需要求出在任意世纪选择的文明，在世纪结束后最终期望的排名的最小值。保留五位小数输出。