MoTeam莫队是一种暴力算法,用于求解一类区间计数问题。 普通莫队给你一个有 n 个元素的序列, m 个询问,每个询问有 l, r ,询问 l−r 这段区间不同数字的出现个数。 先考虑暴力,每次 l−r 循环一次统计答案,复杂度 Θ(nm) 。 然 ...
51nod 战忽局的手段
战忽局的手段Description Solution套路题。 根据期望的线性,我们可以设 fi 表示 m 次演讲忽悠成了 i 次的概率。Ans=∑fi
51nod 第K大区间
第 K 大区间Description Solution挺妙的一道想法题。 只想到了要离散化去重、桶,二分真的没想到,看了题解发觉十分精妙,便记录一下。 观察数据范围,可以发现要离散化,然后求区间众数,可以考虑用桶。 关键在于如何优化求解第 k 大区间的过程。 可以二分区间众数的值,判断是 ...
51nod 最后的机会
51nod 最后的机会Description Solution首先可以套路的将把元音字母变成 −1 ,辅音字母变成 2 ,然后做一遍前缀和,这样只要 sumj−sumi−1>=0 即可判断该字符串满足条件。 然后考虑如何优化这个枚举找最大的 $j - ...
Matrix Tree
Matrix Tree theorem参考资料 定理对于一个无向图 G, 他的生成树个数等于其基尔霍夫矩阵的任意一个 N - 1 阶主子式的行列式的绝对值。N - 1 阶主子式就是对于一个任意的一个 r ,将矩阵的第 r 行和第 r 列同时删去得到的新矩阵。基尔霍夫矩阵的一种求法:K = ...
Rabbit Exercise
Rabbit ExerciseDescription Solution又是一道经典套路题。 首先考虑 50pts 的做法。 可以发现跳到左边的贡献是 2×cj−1−cj ,右边的贡献 2×cj+1−cj ,所以期望就 ...