LOJ6044 「雅礼集训 2017 Day8」共
LOJ 分析 树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。 首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点（$1$ 的深度一定为奇数）。 将深度为奇数的点作为左部点、深度为偶数的点作为右部点，两部分间两两连边，则问题变为求生成树个数。 考虑 Prufer 序列，则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次，故生成树个数为 $k...
分类 题解 下的文章
- 首页
- 题解
LOJ6045 「雅礼集训 2017 Day8」价
LOJ CF 原题 分析 感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式 源点向每种药连容量为 $+\infty+p_i$ 的边。 每种药向所需的药材连容量为 $+\infty$ 的边。 每种药材向汇点连容量为 $+\infty$ 的边。 拿最小割减去所有 $+\infty+p_i$ 的和即为答案（因为取了负）。 下面是正确性理解： 首先可以发现，第二种的边是不会割的...
洛谷3746 [六省联考2017]组合数问题
Luogu LOJ 分析 考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。 考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移 直接矩阵快速幂即可。 需要注意的是 $k=1$ 时转移矩阵是 $[2]$。 代码 // ====================...
CF814E An unavoidable detour for home
Codeforces Luogu 分析 显然对于合法的图，满足不在最短路树上边连接的点在同一层。 设 $f_{i,j}$ 表示前 $i$ 个点，$[i-j+1,i]$ 中的点在同一层时的方案数，$g_{i,j,k}$ 表示这一层有 $i$ 个点，上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。 $f$ 的转移不难得到：枚...
LOJ6068 「2017 山东一轮集训 Day4」棋盘
LOJ 分析 考虑二分图。对于每一行、列被 # 隔开的每一段拿出来当做一个点，然后对于每个点从其所属的行连通块向列连通块连边。 但是每个连通块内可以放多个棋子。假设一个连通块内放了 $x$ 个棋子，那么会产生 $\frac{x(x-1)}{2}$ 的费用，我们要最小化费用。 考虑费用递增。由于 $\frac{(x+1)x}{2}-\frac{x(x-1)}{2}=x$，所以我们只需要连若干条...
LOJ3080 「2019 集训队互测 Day 5」国际象棋
LOJ 分析 不难想到一个 $\mathcal{O}(n^3m^3)$ 的高斯消元做法，即将每个位置出发的期望步数作为变量，然后暴力高斯消元。 考虑将第一行、第二行、第一列的位置作为主元，并将其它元用主元线性表示。可以发现只有 $(x+2,y+1)$ 无法直接求出它的线性表示，但因为向八个方向走的概率之和为 $1$，所以可以用其它七个方向来求 $(x+2,y+1)$ 的线性表示。 当 $(x...
洛谷3750 [六省联考2017]分手是祝愿
Luogu LOJ 分析 首先可以发现，$i$ 只能被 $\geq i$ 的开关操作掉。从而我们只需要从大到小模拟一遍，如果 $i$ 亮着就操作 $i$ 开关，就可以算出最小需要操作的次数 $c$ 了。这样子就可以拿到 $50$ 分（实际上有 80 分）。 冷静分析一下可以发现，达到目标所需要按的开关组合是唯一确定的。我们把这些开关叫做正确的。 考虑一个 DP。设 $dp_i$ 表示从剩余 ...
洛谷3749 [六省联考2017]寿司餐厅
Luogu LOJ 分析 数组开小 -> 100->40 -> 身败名裂 先考虑没有费用的情况，显然是最大权闭合子图模型（选了 $[i,j]$ 就必须选它的所有子区间）。因此对于每个 $[i,j]$，如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边，否则从它向汇点连容量为 $-d_{i,j}$ 的边，然后对于每个 $[i,j]$ 向它的子区间连容...
CF487E Tourists
Codeforces Luogu 分析 可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。 从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的...
洛谷1173 [NOI2016]网格
Luogu LOJ 分析 首先发现答案只可能是 $-1,0,1,2$ 中的一个：当图本就不连通时答案为 $0$，当图存在割点时答案为 $1$，当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$，否则答案为 $2$。 然而把整张图都建出来显然是不现实的。不难想到只把每只蛐蛐周围一圈跳蚤拿出来建图，但这样会有问题： .** .*# .** 此时第二行第二列的 ...