洛谷3511 [POI2010]MOS-Bridges
Luogu LOJ 分析 考虑二分答案，则我们需要判定是否存在混合图欧拉回路。 首先混合图不连通的话一定不存在。 然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。 那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。 因此可以考虑网络流。对于 $in_ out_i$...
标签 二分 下的文章
- 首页
- 二分
洛谷6558 [APIO2017]考拉的游戏
Luogu LOJ 分析 Subtask1 在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。 这样子只需要调用一次 playRound，可以得到 $4$ 分。 Subtask2 先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $50$ 大的物品。 那么可以...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
CF464E The Classic Problem
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
ARC103F Distance Sums
AtCoder Luogu 分析 不难发现 $d_i$ 最大的节点一定是叶子节点，$d_i$ 最小的节点一定是重心。 考虑某个叶子节点 $u$ 的父节点 $f$ 应该满足什么。显然有 $d_v=d_f+(n-sz_u)-sz_u$ 即 $d_f=d_v+2sz_u-n$。于是我们只要随便找一个这样的 $f$ 连上去即可，如果找不到则无解。这个 $f$ 可以通过二分来找。 这样子我们就可以按照...
CF1354G Find a Gift
Codeforces Luogu 分析 蓝题都不会做了 /kk 因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。 那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。 如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。 代码 // ==...
洛谷4654 [CEOI2017]Mousetrap
Luogu LOJ 分析 为了方便，将陷阱作为根节点。那么冷静分析一下可以得到一些结论（没有证明） 当老鼠走到一个叶节点时，它将被困住。 当老鼠被困住时，将其它岔路口堵住，然后将到根的路径擦干净是最优的。 设 $f_u$ 表示老鼠进入 $u$ 子树后回到 $u$ 的最小操作次数。显然老鼠会找一个 $f$ 最大的子树进去，所以堵住 $f$ 最大的子树最优，此时老鼠会进入 $f$ 次大的子树...
洛谷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...
CF639E Bear and Paradox
Codeforces Luogu 分析 首先考虑怎么放最优。考虑邻项交换法 于是按照 $\frac{a_i}{t_i}$ 从大到小排序即可。 一个想法是二分答案，check 时按 $a_i$ 排序然后看 $a_i\left(1-\frac{cx}{T}\right)$ 是否满足条件。但很容易发现这个是假的，因为 $\frac{a_i}{t_i}$ 相同的题目无法确定顺序，从而无法确定完成时...
AGC033D Complexity
AtCoder Luogu 分析 首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度，然而显然是过不去的。 注意到答案在 $\log nm$ 级别，因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时，上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移 如果暴...