Loading...
NOI2021 加油！
题目链接其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。题目描述你可以连续的输出一些单词，定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。其中 $ N \leq 500000,M \leq 1000 $
写一些简单的 1D/1D 的决策单调性优化...这种决策单调性优化的过程：列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分我们以一些例题为例：
题目链接题目描述给定一棵 $ N $ 个节点的树，需要维持以下个操作： 改变第 $ k $ 条边的边权； 改变点 $ u $ 到点 $ v $ 的边权为 $ w $； 将点 $ u $ 和点 $ v $ 路径上的边的边权都增加 $ w $； 询问点 $ u $ 和点 $ v $ 路径上的边权最大值。 其中 $ 1 \leq N \leq 10^5 $，操作+询问数目不超过 $ 10^5 $。
这道题甚至不如 T2 难...放在 T3 真的合适吗...题目链接题目描述一张无向带权图，需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中，有 $ p_i $ 的概率选择点 $ d_i $，有 $ 1-p_i $ 的概率选择点 $ c_i $ ，每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。
题意描述给定一张无向图，定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路，求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。题目链接推荐大家去 uoj 多交一些题目，上面有很多 hack 数据。（像我之前认为 dij 就是 spfa+priority_queue）。