洛谷3248 [HNOI2016]树
Luogu BZOJ 分析 显然大树最多会有 $10^{10}$ 个点，完全开不下。 但是发现每次操作都是复制一颗子树，所以可以把大树当做一颗树套树。 构造大树时，令每一个大节点为模板树中的一颗子树，并对大树重新编号，就像这样： 作出如下定义： 两个大节点的边权为对应的树的根节点的距离，比如上图$1$和$2$之间的边权为$2$。 $st[i]$ 表示大节点 $i$ 对应的小节点的编号区间...
分类 题解 下的文章
- 首页
- 题解
洛谷4437 [HNOI2018]排列
Luogu 分析 首先，如果 $a[j]=k$ ，那么 $k$ 一定在 $j$ 的前面。 考虑从 $a[j]$ 向 $j$ 连边，构成一个图。显然，如果有环的话是无解的， 那么现在就是，如果要选子节点，必须要先选父节点。$i$ 节点第 $T$ 个选出来的话，贡献是 $Tw[i]$ 。 考虑贪心。设当前权值最小的节点为 $i$。 如果 $i$ 没有父节点的话，显然当前会选 $i$ 。 如果 ...
洛谷3235 [HNOI2014]江南乐
Luogu 分析 首先发现这是个 Multi-SG 游戏，那么可以考虑使用 SG 函数。 先考虑怎么暴力求 $SG(x)$ 。 大力枚举分成的堆数。如果将 $x$ 分成了 $i$ 堆，那么这 $i$ 堆中有 $x\bmod i$ 堆 $\left\lceil\frac{x}{i}\right\rceil$，有 $i-x\bmod i$ 堆 $\left\lfloor\frac{x}{i}\r...
BZOJ2395 [Balkan 2011]Timeismoney
BZOJ 分析 我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。 这个东西可以分三步求： 求出与 $x$ 轴和 $y$ 轴最近的点 这个还是很简单的。 把 $a_i$ 作为边权，求出的最小生成树...
洛谷3231 [HNOI2013]消毒
Luogu 分析 先考虑平面上的这种问题：平面上有一些方块，你每次可以覆盖长度为 $x$、宽度为 $y$ 的一个区域，代价是 $\min(x,y)$，求覆盖所有点的最小代价。 显然每次染一个 $1\times k$ 的区域是最优的。于是让每个方块的 $x$ 向 $y$ 连边，然后求二分图最小点覆盖即可。 现在把这个扩展到三维。 注意到一定有一维 $\leq\sqrt[3]{5000}$ 也...
洛谷4049 [JSOI2007]合金
Luogu 分析 将每种金属看做一个点 $(a_i, b_i)$，那么两点能配出的所有合金一定在两点构成的线段上。 问题转为给出 $m$ 个点，求一个以这 $m$ 个点为顶点的边数最少的多边形包含 $n$ 个关键点。 如果 $n$ 个点都在 $(x,y)$ 左侧，连一条从 $x$ 到 $y$ 的边权为 $1$ 的边，这样子满足条件的多边形就变成了图上的一个圈。 我们需要求最小圈， Floy...
洛谷3317 [SDOI2014]重建
Luogu 分析 显然答案为 我们知道矩阵树定理求的实际上是 $\sum_T \prod_{e \in T} w_e$，于是我们可以使用矩阵树定理算出后面东西。 但是有 $p_e = 1$ 的情况，我们只需要把 $p_e$ 设为 $1-\epsilon $ 即可。 代码 //It is made by M_sea #include <algorithm> #include &l...
洛谷3640 [APIO2013]出题人
Luogu 分析 前置工作 首先，神秘问题指的是染色问题。 观察代码，Floyd Warshall 是严格 $\mathcal{O}(V^3)$ 的 Floyd，Optimized Bellman Ford 是上界 $\mathcal{O}(QVM)$ 的奇怪的 Bellman Ford，Modified Dijkstra 就是堆优化的 Dijkstra。 Gamble1 一定不会 TLE，...
洛谷3206 [HNOI2010]城市建设
Luogu 分析 对修改时间分治，假设当前的时间区间是 $[L,R]$。 考虑以下两种操作： 把 $[L,R]$ 中要修改的所有边修改成 $-\infty$，然后求一遍最小生成树。 发现，如果一条非 $-\infty$ 边在最小生成树中，那它以后一定也在最小生成树中，所以可以把它先加进去。于是可以把所有这样的边形成的连通块缩成一个点。 把 $[L,R]$ 中要修改的所有边修改为$\i...
洛谷4581 [BJOI2014]想法
Luogu 分析 看到这个巨大的误差允许范围，可以考虑乱搞。 我们给所有入度为 $0$ 的点赋一个随机权值，然后将每个点的权值设为所有能到达这个点的点权的最小值。 经过一番推导后可以发现，这个权值的期望是 $\frac{\mathrm{RAND\_MAX}}{k}$，这里的 $k$ 是能到达这个点的入度为$0$的点的个数。那么这样子就能够估算出 $k$ 了。 代码 //It is made ...