洛谷4587 [FJOI2016]神秘数
Luogu 分析 先考虑暴力怎么做。把 $[l, r]$ 中的数排序，然后维护 $lim$ 表示 $[1, lim]$ 中的数都能被表示出。假设当前加入了 $w$，那么 如果 $w > lim + 1$，则 $lim + 1$ 不能被表示出，答案即为 $lim + 1$； 否则更新 $lim$ 为 $lim + w$。 考虑优化。设上一次的 $lim$ 为 $pre$，那么只有 $...
标签 主席树 下的文章
- 首页
- 主席树
洛谷5331 [SNOI2019]通信
Luogu LOJ 分析 容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。 然而这样...
JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
LOJ2865 「IOI2018」狼人
LOJ UOJ Luogu 分析 以端点的 $\min$ 为边权建一棵 Kruskal 重构树，以端点的 $\max$ 为边权建一棵 Kruskal 重构树。 那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点，其子树就是人类状态下从起点出发能走到的点；在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点，其子树就是狼人状态下能走到终点的点。 那么我们只需要求这...
CF464E The Classic Problem
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
CF757G Can Bash Save the Day?
Codeforces Luogu 分析 考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。 我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$，这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t...
洛谷3293 [SCOI2016]美味
Luogu LOJ 分析 考虑沿用 $x=0$ 时的贪心，则我们需要判断是否存在 $a_i+x$ 在某个区间内。 具体地，假设当前位是 $1$，则我们需要判断是否有一个 $a_i+x$ 的这一位为 $0$。假设前面已经确定的位加上当前位的最优解是 $t$，则 $a_i+x\in[t,t+2^i-1]$ 都满足条件，我们只需要判断是否存在 $a_i\in[t-x,t+2^i-1-x]$，主席树...
洛谷4094 [HEOI2016/TJOI2016]字符串
Luogu LOJ 分析 考虑二分答案 $mid$，则我们需要判定是否存在一个 $p\in[a,b-mid+1]$，满足 $\operatorname{lcp}(suf(p),suf(c))\geq mid$。 既然有 LCP，可以考虑后缀数组，则 $\operatorname{lcp}(suf(p),suf(c))\geq mid$ 相当于 $\min_{i=rk_p+1}^{rk_c}h...
BZOJ3218 a + b Problem
BZOJ 分析 容易看出最小割。考虑连边： 对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。 对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。 考虑正确性...
洛谷4559 [JSOI2018]列队
Luogu LOJ 分析 显然，所有学生跑到指定位置后，相对位置不改变会最优。 那么最终会有一部分学生向左跑，一部分学生向右跑，而且两部分一定是分开的。 考虑建立一棵以位置为下标的主席树。 设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。若当前递归的区间是 $[l,r]$ ，分四种情况： 没有学生，直接返回 $0$ 。 全部向左跑，直接返回 $\sum a_...