$MoTeam$莫队是一种暴力算法，用于求解一类区间计数问题。 普通莫队给你一个有 $n$ 个元素的序列， $m$ 个询问，每个询问有 $l,\ r$ ，询问 $l - r$ 这段区间不同数字的出现个数。 先考虑暴力，每次 $l - r$ 循环一次统计答案，复杂度 $\Theta (nm)$ 。 然 ...

七星剑$Description$ $Solution$设 $f_i$ 表示镶 $i$ 颗魔法石的期望。$$f_i = C_j + f_{i - 1} + (f_i - f_{i - 1 - Lose[i][j]}) \times (1 - Prod_{i, j})$$ $$f_i \times Pr ...

战忽局的手段$Description$ $Solution$套路题。 根据期望的线性，我们可以设 $f_i$ 表示 $m$ 次演讲忽悠成了 $i$ 次的概率。$$Ans = \sum f_i$$ $$f_i = f_{i - 1} + (1 - \frac{ f_{i - 1} }{n})$$ 忽悠 ...

第 K 大区间$Description$ $Solution$挺妙的一道想法题。 只想到了要离散化去重、桶，二分真的没想到，看了题解发觉十分精妙，便记录一下。 观察数据范围，可以发现要离散化，然后求区间众数，可以考虑用桶。 关键在于如何优化求解第 $k$ 大区间的过程。 可以二分区间众数的值，判断是 ...

$51nod$ 最后的机会$Description$ $Solution$首先可以套路的将把元音字母变成 $-1$ ，辅音字母变成 $2$ ，然后做一遍前缀和，这样只要 $sum_j - sum_{i - 1} >= 0$ 即可判断该字符串满足条件。 然后考虑如何优化这个枚举找最大的 $j - ...

$Gauss$——浅谈高斯消元方程组的构造 我们以一道题为例： 本题要求求解路径上 $xor$ 的期望值，那么根据期望是线性的套路性质，我们可以考虑求出每一位上为 $1$ 的期望，乘上使用次数就是答案。 所以我们根据这个性质，设 $f_i$ 表示从 $i$ 这一位为 $1$ 的概率。 那么从其他转移 ...

$4.10$ 比赛部分题解$t1$ 暮色苍然$Descroition$ $Solution$由题意可以列出一点东西：$$\begin{cases}gcd(x, y) = a_1\\gcd(x, y + 1) = a_2\\gcd (x, y + 2) = a_3\\\ldots\\gcd(x, y ...

$Matrix$ $Tree$ $theorem$参考资料 定理对于一个无向图 G, 他的生成树个数等于其基尔霍夫矩阵的任意一个 N - 1 阶主子式的行列式的绝对值。N - 1 阶主子式就是对于一个任意的一个 r ，将矩阵的第 r 行和第 r 列同时删去得到的新矩阵。基尔霍夫矩阵的一种求法：K = ...

$freeway$$ps:$ 有点毒的线段树加概率期望，感觉大致有点理解了概率期望的含义，跟平均数有点像？计数就是把所有答案的和除以方案个数。 还有一个小套路？下面讲。 $Description$ $Solution$区间求和，区间查询，显然是线段树题。 然后我们考虑如何进行区间查询。 先考虑求 $ ...

$Rabbit$ $Exercise$$Description$ $Solution$又是一道经典套路题。 首先考虑 $50pts$ 的做法。 可以发现跳到左边的贡献是 $2\times c_{j - 1} - c_j$ ，右边的贡献 $2\times c_{j + 1} - c_j$ ，所以期望就 ...