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)$，然后解方程组解出系数即可...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷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$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。 因为点数 $...
ARC098F Donation
AtCoder Luogu 分析 设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。 然后可以发现两个结论： 每个点只会在最后一次访问时被捐赠。 $c_i$ 大的会优先捐赠。 那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$...
CF1067D Computer Game
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
CF1093F Vasya and Array
Codeforces Luogu 分析 设 $dp_{i,j}$ 表示前 $i$ 个数，第 $i$ 位填 $j$ 的方案数，$s_i$ 表示 $\sum_{j=1}^k dp_{i,j}$，$len_{i,j}$ 表示第 $i$ 位往前最多有多少位为 $j$。 转移时讨论一下。当 $len_{i,j}<l$ 时 $dp_{i,j}=s_{i-1}$；否则要减去超长的那一部分，即为 $d...
洛谷6280 [USACO20OPEN]Exercise G
Luogu 分析 显然一个置换的步数就是它所有环长的 $\operatorname{lcm}$。于是问题变为求有多少个数 $n$ 的某个拆分中所有数的 $\operatorname{lcm}$。 考虑 DP。设 $dp_{i,j}$ 表示 $i$ 拆成若干个最大质因子 $\leq p_j$ 且不为 $1$ 的数时的答案，不难得到转移 答案即为 $1+\sum_{i=1}^n dp_{n,|...
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)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
洛谷4565 [CTSC2018]暴力写挂
Luogu LOJ 分析 题目中的式子等价于 我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。 虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。 代码 // =======================...