2019.9.13 高中部集训

???


考试

上午考试鸭~~

$nlp$

十分讨厌 ”数学“ 题 qwq

$O(3^n)$

直接暴力搜索,枚举每一种情况来计算概率。

$O(len^3 \times n + n^3)$

用到搜索,就应该想到 $dp$ 。设计状态 $f[i][a][b][c]$ 表示一个句子有 $i$ 个单词的时候,有 $a$ 个正面,$b$ 个负面,$c$ 个中性时的答案。算句子时类似。

初始状态为:$f[0][0][0][0] = 1$ 。

$O(n \times len^2 + n^2)$

很容易 发现一点,可以简化状态,把状态简化成 $f[i][j]$ ,表示前 $i$ 个位置里,正面比反面多 $j$ 个的概率。所以说 $j \in [-len, len]$ ,转移为 $O(1)$ 。

$O(n \times len + n^2)$

其实有一个很容易发现的性质,猜也可以觉得是对的。那就是:

因为负面和正面的概率是一样的,所以说算出中性的概率就可以了。

最后如上面的 $O(n \times len^2 + n^2)$ 一样统计文章即可。

$kset$

这道题,用贪心是错的。班上似乎都用了贪心 qwq,被样例骗了,最后也只得了样例的 10 分。

30 分

暴力 qwq

早知道劳资去打这个暴力也比错误的贪心强 QAQ

60 分

从思考错误贪心的心里历程中,一定可以发现,第一个取最小的,然后从原来的变一些,变成次小解输出,一次类推。

但是贪心错误就在于,不知道要怎么变才能产生真正的次小解。

懒得打了,直接引用老师发的 solution

“ k 扩展” ,即从最优答案开始每次使某一小部分变劣,直到得到前 k 个
最优答案。

类似于 $Dijkstra$ ,从最优答案开始,每次将其在每一序列中元素往后推,
得到新状态(需要判重)放入最大 $size$ 为 $k$ 的堆中,若 $size$ 超过了 $k$ 则弹
出最差的答案,同时将新状态放入堆中用于扩展新状态。

最后最坏复杂度为 $O(k^2 \log k) + O(Hash) = O(k^2 \log k + k^2)$

100 分

懒得写了 (其实我太菜了,不会 qwq)

按序列次序扩展,前 $i$ 个序列的前 $k$ 大方案,可由前 $i - 1$ 个序列的前
$k$ 大方案得到。

此时对于一个状态的扩展:将该方案在新序列上对应元素往后推一个位
置,即扩展复杂度 $O(1)$ ,初始时在新序列上对应元素为第一个(最小的)。

用类似 60% 的方法进行维护,此时无需 $hash$。

复杂度$O(k ^ 2 \log k)$。

$lca$

$O(n \times q \times \log n)$

暴力。

$O()$


笔记

再谈 $LCA$

使用 欧拉序 求 $LCA$

欧拉序有点类似 $dfs$ 序,欧拉序和 $dfs$ 序的区别是,只要到一个点就输出节点号。

那么就可以用这个东西求出 $LCA$ ,把要求的两点第一次出现位置记录下来,易得最近公共祖先一定会在这段欧拉序中,且该祖先结点在其中的深度最小。然后就可以用 $ST$ 表来求区间最小值了。也是 $O(\log n)$ 。

其实倍增的 $f$ 数组也有 $ST$ 表的思想。

CF147B

使用 $f[i][j][k]$ 表示从 $i$ 到 $j$ 经过不超过 $2^k$ 条边的最大边权和。

那么则有:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×