题解 由于给定序列，$o$的概率一定是1，$x$的概率一定是0. $?$的期望实际上是0.5 我们要求的是$E_{x^2}$,令$dp_i$代表到第i位时$E_{x^2i}$，$l_i$为到达$i$位置时的期望长度。根据上述条件，$o$时$l_i = l_{i-1} + 1$,$x$时$l_i = 0$,而$x$的时候$l_i = 0.5 \tim…

题意 略 题解 由于这是一个不用维护原有序列的操作，我们可以考虑维护一个ST表进行RMQ查询。 这个RMQ是用来干什么呢？ 根据题目数据范围，我们知道这道题不能容忍$\mathcal O(n^2)$及以上的算法 我们必须要在$\mathcal O(nlogn)$的时间复杂度下完成所有的操作。 维护一个dp数组，$dp[cur] = dp[first…

题意 给定长为$n$的数组，初始值均为0 执行m个操作，每次操作的行为 如原题面 题解 很多人用线段树弄过去了，但是这个非常考验模板的水平，如果常数比较大这个方法就GG了 官方题解的解法说的不是很清楚，而根据官方标程的实现方式，实际上就是一个标准的RMQ逆向的过程。 首先对于RMQ 我们要学习什么是ST表。附录:ST表 然后我们在m次操作中，把一个…

题目描述 Adrian 很喜欢诗歌中的韵。他认为，两个单词押韵当且仅当它们的最长公共 后缀的长度至少是其中较长单词的长度减一。也就是说，单词 A 与单词 B 押韵 当且仅当 LCS(A, B) ≥ max(|A|, |B|) – 1。（其中 LCS 是最长公共后缀 longest common suffix 的缩写） 现在，Adrian 得到了 N…

根据Floyd算法我们可以通过状态转移方程解决一个无向图或者有向图中两点之间最短路径的问题，其时间复杂度为O(n³),空间复杂度可以控制在O(n²)(一般情况)。但是在实际运用中如果对Floyd三重循环的ijk顺序有改动，会导致无法正确得出两点之间的最短路径的问题。 正确的做法是   [code lang="cpp"] for(int k…