搜索结果
查询Tags标签: YBT2022,共有 4条记录-
【YBT2022寒假Day2 A】期望旅行(Dij)(期望DP)
期望旅行 题目链接:YBT2022寒假Day2 A 题目大意 给你一个无向图,然后每个边有出现的概率,自环必定出现。 然后问你在最优策略下你从 \(1\) 点走到 \(n\) 点的期望步数。 思路 考虑每次要怎么转移。 会发现是这样的,我们可以按 \(E(x)\)(设为 \(x\) 走到 \(n\) 的概率…
2022/2/7 6:12:34 人评论 次浏览 -
【YBT2022寒假Day2 B】【luogu CF809D】模糊序列 / Hitchhiking in the Baltic States(平衡树优化DP)(fhq-Treap)
模糊序列 / Hitchhiking in the Baltic States 题目链接:YBT2022寒假Day2 B / luogu CF809D 题目大意 给你一个序列,然后每个位置有可以选的数的范围。 然后要你找到对于所有可能的序列它严格上升子序列的最大长度。 思路 很明显的 DP。 考虑列方程,发现数的范围很大,…
2022/2/7 6:12:33 人评论 次浏览 -
【YBT2022寒假Day1 B】方格填写(插头DP)
方格填写 题目链接:YBT2022寒假Day1 B 题目大意 有一个二维网格,然后里面每个位置要放一个 0~4 的数有一些已经填好的,也有要你填的。 然后一个位置可以跟相邻的四个点连边,然后要求一个点的边数量等于填的数字。 然后问你所有填写方案边的匹配方案数的平方的和。 思路…
2022/2/6 6:13:52 人评论 次浏览 -
【YBT2022寒假Day1 A】变量观测(模拟)(分治)
变量观测 题目链接: YBT2022寒假Day1 A 题目大意 给你 n 个数,要你在线维护两种操作: 给一个数加一个值,或者设立一个观察者观察一些数,从当时开始观察,当观察的数的变化值的和大于一个设定值是结束观察。 然后对于每个加数的操作你要输出有多少个观察者结束观察。 …
2022/2/6 6:13:52 人评论 次浏览