标签: 二分

10 篇文章

CF878E Numbers on the blackboard
题目链接:CF878E 给出 $n$ 个数字,每次询问一个区间 $[l,r]$,对这个区间内部的点进行操作。 每次操作可以合并相邻两个数 $x,y$ 其中 $x$ before $y$,将它们变成 $x+2y$ 对于每次询问输出当最后只剩下一个数字时,这个数字的最大值。 询问互相独立,答案对 $10^9+7$ 取模。 $1\leq n,q\leq …
义乌中学暑假集训 2021.07.15 D
白云在白兔的城市,打算在这里住 $n$ 天,这 $n$ 天,白云计划找白兔订购水。 白云给出了接下来的 $n$​ 天,每天的需水量,第 $i$​ 天为 $D_i$ 升。 白兔给出了接下来的 $n$ 天,每天水的价格,第 $i$ 天为 $P_i$ 元每升。 白云的小区有一个共用水壶,最大容量为 $V$ 升,初始为空。 接下来每天,白云可以进行如下操作…
义乌中学暑假集训 2021.07.13 C
给定一棵 $n$ 个节点的带权有根树,保证每个节点权值均为非负整数。 定义 $f(x)$​,表示对于节点 $x$​,包含 $x$​ 的节点的平均值最大的连通块内平均值。 求 $\min_{i=1}^n f(i)$。 $n\leq 10^5$。 Sol 既有最小也有最大,想到二分。 可以二分答案,每次 check 的时候数字权值减去 mid,跑一次换…
CF GYM102759 I. Query On A Tree 17
Description 题目链接:GYM102759 I 给定一棵以 $1$​ 为根节点的拥有 $N$​ 个节点的带点权树,初始时每个点的点权均为 $0$​,有 $Q$​ 次操作,每次操作有两种类型: 1 u,以 $u$ 为根节点的子树内每个点点权均加 $1$。2 u v,将节点 $u$ 到节点 $v$ 的简单路径上的点的点权均加 $1$。 每次操…
bzoj2122 工作评估
Description 题目链接:bzoj2122 利用空闲时间,BX希望外出工作,工作开始之前,公司就会给BX一个评估值 $X_0$,之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出,即 $X_i=X_{i-1}+D_i$,但是每天的评估值有一个上限,也就是说完整的评估公式应该是 $X_i=\min{X_i-1+D_i,L_i}…
LuoguP5356 [Ynoi2017] 由乃打扑克
Description 题目链接:P5356 一个长为 $n$ 的序列 $a$,需要支持 $m$ 次操作,操作有两种: 查询区间 $[l,r]$ 的第 $k$ 小值。区间 $[l,r]$ 加上 $k$。 $1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。 …
Luogu P1084 疫情控制 题解
Link Luogu Problem view Describe 有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时…
bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解
题意 在平面直角坐标系中有$n$个点,现在给你$3$个$L\times L$的正方形,问要用这$3$个正方形盖住所有点的最小的$L$。 思路 终于开始刷$bzoj$了$QwQ$... 非常明显,这道题肯定要二分,那么怎么写$check$呢? 可以考虑如果用一个非常大的正方形盖住了所有点,那么必定会有点在这个正方形的四条边上。所以有正方形必须在边上。…