CF455E Function
Codeforces 分析 我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。 注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询...
标签 二分 下的文章
- 首页
- 二分
LOJ3192 「ROI 2019 Day2」课桌
LOJ 分析 对于一张课桌，如果其区间被另外的课桌包含，那么它是没用的，可以去掉。那么剩下的课桌满足左右端点都递增。 对于每个班的学生，将其按身高排序，显然每两个人坐同一张课桌更优，且一定是身高小的坐 $l$ 小的桌子。 那么每对学生选择的桌子满足决策单调性，可以分治处理。在计算代价时，把所有班当前组的 $2m$ 个人拿出来按照身高排序，然后维护一个前缀和，这样子只需要二分一下就可以计算了。...
洛谷2519 [HAOI2011]Problem A
Luogu 分析 每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。 那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。 把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。 这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。 注意把 $a_i+1>n-b_i$ 的人掉，这...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
LOJ576 「LibreOJ NOI Round #2」签到游戏
LOJ 分析 设 $s_i$ 为 $\sum_{j=1}^i b_j$，则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$，则相当于要让 $(0,n)$ 连通，也就是要求最小生成树。 根据 Kruskal 那套理论，我们一定会连边 $(0,n)$。 根据 Prim 那套理论，剩下的点要么连 $(0,i)$，要么连 $(i,n)$。更具体的，一定存在一个点 $...
洛谷2179 [NOI2012]骑行川藏
Luogu LOJ 分析 我们画出每条路线的 $t-E$ 图像，大概是这个样子的（蓝色的是原函数，红色的是它的导数）： 感性理解一下可以知道，最后每条路径在其消耗的能量处的导数相同。 于是我们可以二分这个导数，然后把每段的速度求出来，算一下总能量是否 $\leq E_U$ 来 check。 现在考虑已知导数怎么算速度。我们有 这个东西在 $[v',+\infty)$ 上是单增的，所以同样...
CF1344D Résumé Review
Codeforces Luogu 分析 对 $f_i(x)=x(a_i-x^2)$ 求二阶导可以发现它是凸的，那么每次选一个 $\Delta y$ 最大的放一定是最优的。 我们二分最小的 $\Delta y$，对每个函数二分（或者直接解一元二次方程）找到它被加的次数，判断是否 $\leq k$ 即可。 这样子最后可能并不能达到 $k$，把还没加的部分选加到 $\Delta y$ 最大的那些上...
AtCoder Grand Contest 006 简要题解
比赛地址 只会做 A，自闭了 Prefix and Suffix 枚举重叠部分的长度即可。 代码 Median Pyramid Easy 显然 $x=1$ 和 $x=2n-1$ 的情况无解。 我们在中间放上 $x$，在它左边放 $x-1$，右边放 $x+1$ 和 $x-2$，可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。 然而 $n=2$ 时只有三个数，需要特判掉。 代码 Rabb...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3517 [POI2011]WYK-Plot
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...