RainAir
My OI Blog
RainAir


文章归档

月下毛景树

题目链接 题目描述 给定一棵 $ N $ 个节点的树,需要维持以下个操作: 改变第 $ k $ 条边的边权; 改变点 $ u $ 到点 $ v $ 的边权为 $ w $; 将点 $ u $ 和点 $ v $ 路径上的边的边权都增加 $ w $; 询问点 $ u $ 和点 $ v $ 路径上的边权最大值。 其中 $ 1 \l…

   194   2018-08-22 去围观

杜教筛学习笔记

预备知识 杜教筛是一种能在比线性复杂度还优秀的复杂度中处理处积性函数的前缀和。 主要运用 Dircichlet 卷积来完成复杂度的化简。 定义 设 $ f(n) $ 为一个数论函数,$ S(n) = \Sigma_{i=1}^nf(i)$。 我们考虑再找到一个合适的数论函数 $g(i)$,使得 $$ \Sigm…

   258   2018-08-17 去围观

「NOIP2016」换教室

这道题甚至不如 T2 难...放在 T3 真的合适吗... 题目链接 题目描述 一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i $ 的概率选择点 $ c_i $ ,每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现…

   277   2018-08-17 去围观

「NOIP2017」逛公园

题意描述 给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。 题目链接 推荐大家去 uoj 多交一些题目,上面有很多 hack 数据。(像我之前认为 dij 就是 spfa+priority_queue)。 解题报…

   221   2018-08-03 去围观
文章归档