Blog

题目大意

给定无向联通图，$q$ 次询问 $s,t,l,r$，求是否存在一个点 $p$，使得 $s\rightarrow p $ 的路径上所经过点的编号 $\ge l$，且 $p \rightarrow t$ 的路径上所经过点的编号 $\le r$。

$n\le 2\times 10^5,m\le 4\times 10^5$

前言

莫比乌斯反演是数论内容的一个重要的分支，通常用于求一些不好直接求解的数论函数。

前言

题目大意

有 $n$ 次考试，第 $i$ 次的满分为 $b_i$，你的得分为 $a_i$，你可以删去 $d$ 次考试，从而你最后的分数为剩下的得分与剩下的总分之比，现存在一种方案，即删去 $\dfrac{a_i}{b_i}$ 最小的 $d$ 次考试，你可以任意删去 $d$ 个考试，求所有的 $d$，使得存在一个最后分数更高的方案。

$n\le 5\times 10^4$。

前言

在动态规划的转移时，我们时常遇到形如 $f(i)=\min\limits_{j < i}{f(j)}+w$ 的转移，这种转移可以用单调队列维护以做到线性的复杂度。斜率优化同样也是通过不断删去不合法和不优决策来优化 DP。