CF505E Mr. Kitayuta vs. Bamboos
Codeforces Luogu 分析 二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。 由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。 考虑贪心，...
标签 二分 下的文章
- 首页
- 二分
洛谷4518 [JSOI2018]绝地反击
Luogu LOJ 分析 设 $f(\alpha)$ 为正多边形旋转角度为 $\alpha$ 时的最短时间，容易发现 $f(\alpha)$ 是单谷的，因此可以三分 $\alpha$。 考虑如何计算 $f(\alpha)$。二分 $f(\alpha)$ 的值 $t$，如果某艘飞船在 $t$ 时间内能够到某个位置则它们可以匹配，判断是否存在完美匹配即可。 这样子可能过不了，考虑一些优化。我们预...
洛谷4557 [JSOI2018]战争
Luogu LOJ 分析 设第一个部落的领地为 $A$，第二个部落的领地为 $B$。 假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。 构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点...
洛谷4324 [JSOI2016]扭动的回文串
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
洛谷6095 [JSOI2015]串分割
Luogu 分析 先考虑 $k|n$ 时的做法。显然所有串的长度应相等。枚举第一个串的起始位置，则需要比较 $k$ 个串中最大的，事先倍长然后后缀排序即可利用 $rk$ 比大小。 考虑 $k\nmid n$ 时怎么做。显然最长的串至多比最短的串长 $1$。 考虑二分答案的排名 $mid$，check() 时仍然枚举第一个串的起始位置 $i$，然后记录一个指针 $p$ 一开始等于 $i$，每次...
UOJ461 新年的Dog划分
UOJ 分析 我们先假装原图是个二分图。 我们可以先想办法求出原图的一棵生成树，那么对其黑白染色即可求出答案。 一个暴力的做法是尝试删掉所有边，如果删掉某条边后连通性发生改变则这条边在生成树上，保留这条边，否则删掉这条边。这样子询问次数是 $\frac{n(n-1)}{2}$。 事实上我们可以每次二分下一条树边的位置：如果删掉 $[L,mid]$ 中的边后图仍连通则下一条树边在 $(mid,...
洛谷2605 [ZJOI2010]基站选址
Luogu 分析 设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。 这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。 考虑转移。枚举上一个建站的位置可以得到 这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会...
CF1039D You Are Given a Tree
Codeforces 分析 首先询问只有一个的时候很简单，差不多就是 NOIP2018D1T3 ，直接贪心即可。 考虑根号分治： 对于链长 $\leq B$ 的询问，直接暴力求。时间复杂度 $O(nB)$ 。 对于链长 $>B$ 的询问，可以发现答案只有至多 $\frac{n}{B}$ 种，直接二分出相同的段即可。时间复杂度 $O(n\frac{n}{B}\log n)$ 。 可以...
CF835E The penguin's game
Codeforces 分析 为了方便，下面把为 $y$ 的数称为特殊数。 首先我们可以通过一次询问得到某个集合内的特殊数的个数的奇偶性。 如果询问的集合大小是偶数，且特殊数的个数为偶数，那么返回值为 $0$ 。 如果询问的集合大小是偶数，且特殊数的个数为奇数，那么返回值为 $y$ 。 如果询问的集合大小是奇数，且特殊数的个数为偶数，那么返回值为 $x$ 。 如果询问的集合大小是奇数，且特...