洛谷3511 [POI2010]MOS-Bridges
Luogu LOJ 分析 考虑二分答案，则我们需要判定是否存在混合图欧拉回路。 首先混合图不连通的话一定不存在。 然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。 那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。 因此可以考虑网络流。对于 $in_ out_i$...
分类 题解 下的文章
- 首页
- 题解
LOJ6405 「ICPC World Finals 2018」征服世界
LOJ 分析 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠...
UOJ455 【UER #8】雪灾与外卖
UOJ 分析 这个东西相当于洞有容量上限和额外代价，因此可以考虑模拟费用流。 我们维护两个堆，分别代表洞和老鼠，然后从左往右扫 如果当前是老鼠，取出一个代价最小的洞，代价即为 $x+cost$；后面有可能反悔，即让右边的一个洞匹配这只老鼠，所以要向老鼠堆中加入 $-(x+cost)-x$。 如果当前是洞，取出一只代价最小的老鼠，代价即为 $y+cost+w$；后面有可能反悔，即让右边的一只...
CF917D Stranger Trees
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
CF156D Clues
Codeforces Luogu 分析 我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为 用并查集求出连通块个数及每个连通块的大小即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ============...
洛谷4606 [SDOI2018]战略游戏
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
洛谷4630 [APIO2018]Duathlon 铁人两项
Luogu LOJ 分析 可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。 那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。 考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$...
洛谷6558 [APIO2017]考拉的游戏
Luogu LOJ 分析 Subtask1 在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。 这样子只需要调用一次 playRound，可以得到 $4$ 分。 Subtask2 先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $50$ 大的物品。 那么可以...
洛谷6630 [ZJOI2020]传统艺能
Luogu LOJ 分析 因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。 考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。 转移需要再求...
CF908H New Year and Boolean Bridges
Codeforces Luogu 分析 显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。 显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。 因为点数 $...