「CF908D」New Year and Arbitrary Arrangement
题目大意一开始序列为空。每次你有 $P_a$ 的概率往序列末尾添加一个a，有 $P_b$ 的概率往序列末尾添加一个b。当子序列ab的出现次数 $\geq K$ 时停止，问子序列ab的期望出现次数。 保证有 $P_a+P_b = 1$（显然）题解考虑 dp，设 $f_{i,j,k}$ 表示拿了 $i$ 个 a,$j$ 个 b，子序列个数为 k 的期望长度。转移平凡： 考虑如果 $i=0$ (...
题目大意一开始序列为空。每次你有 $P_a$ 的概率往序列末尾添加一个a，有 $P_b$ 的概率往序列末尾添加一个b。当子序列ab的出现次数 $\geq K$ 时停止，问子序列ab的期望出现次数。 保证有 $P_a+P_b = 1$（显然）题解考虑 dp，设 $f_{i,j,k}$ 表示拿了 $i$ 个 a,$j$ 个 b，子序列个数为 k 的期望长度。转移平凡： 考虑如果 $i=0$ (...
题意定义一个集合 $S$ 是好的，当且仅当： 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$，这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$求这样的集合的个数，模 $10 ^9+7$题解这是个好题（至少我觉得我是想不出来） 首先一个观察是这样的集合一定是由一组线性基生成出来的，我们只需要搞出一个让线性基和集合的一一...
题目2019 十一权限题解每次小 E 肯定会选择获胜概率最大的那个颜色，我们首先考虑如何算出这个概率。 首先题目里的排列形式是没有意义的，可以通过组合数来变成选取一些数。首先 如果对于颜色 $c$ ，它总共有 $a_c$ 个，这次小 E 手里这个颜色的数的的数量为 $b_c$，令 $N = \sum a_i$，那么获胜概率应该就是： 这个概率是可以用简单的 dp 计算出来的，然后乘起来就好...
题目大意有一棵基环树，现在你需要从基环树上选择一条边被删除，满足： 1. 删除后形成的是一棵树（不是森林） 2. 删除后的直径尽量小并且求出最小可能的直径题解首先基环树求直径大家都会。。。Island 岛屿（虽然由于我太菜至今还没卡常成功） 然后这个题我们考虑如何删除一条边之后快速算出直径。 我们只考虑最长路径跨过环的情况（不跨过环的可以轻松处理） 对于每个子树做直径 dp 是必须的，然后我...
题目大意给出一个由前 $k$ 个大写字母组成的字符串，每次可以花费 $t_i$ 代价删去该字符串中所有的第 $i$ 个大写字母，一个字符串的代价为该字符串每对相邻字符的代价，给出 $k\times k$ 的矩阵表示两个相邻的大写字母的代价矩阵，问有多少种删除方案使得删除的代价以及剩余字符串的代价之和不超过$T$，注意剩余字符串需非空。 其中 $n \leq 2 \times 10^5,k \...